1: using Xint = System.Numerics.BigInteger;
2:
3:
4: namespace Luschny.Math.Factorial
5: {
6: public class FactorialAdditiveSwing : IFactorialFunction
7: {
8: public FactorialAdditiveSwing() { }
9:
10: public string Name
11: {
12: get { return "AdditiveSwing "; }
13: }
14:
15: public Xint Factorial(int n)
16: {
17: if (n < 0)
18: {
19: throw new System.ArgumentOutOfRangeException("n",
20: Name + ": n >= 0 required, but was " + n);
21: }
22:
23: return RecFactorial(n);
24: }
25:
26: private Xint RecFactorial(int n)
27: {
28: if (n < 2) return Xint.One;
29:
30: return Xint.Pow(RecFactorial(n / 2),2) * Swing(n);
31: }
32:
33: private static Xint Swing(int n)
34: {
35: Xint w = Xint.One;
36:
37: if (n > 1)
38: {
39: n = n + 2;
40: Xint[] s = new Xint[n + 1];
41:
42: s[0] = s[1] = Xint.Zero;
43: s[2] = w;
44:
45: for (int m = 3; m <= n; m++)
46: {
47: s[m] = s[m - 2];
48: for (int k = m; k >= 2; k--)
49: {
50: s[k] += s[k - 2];
51: if ((k & 1) == 1) // if k is odd
52: {
53: s[k] += s[k - 1];
54: }
55: }
56: }
57: w = s[n];
58: }
59: return w;
60: }
61: }
62:
63: } // endOfFactorialAdditiveSwing