1: package de.luschny.math.factorial;
2:
3: import de.luschny.math.arithmetic.Xint;
4:
5: public class FactorialAdditiveSwing implements IFactorialFunction
6: {
7:
8: public FactorialAdditiveSwing()
9: {
10: }
11:
12: public String getName()
13: {
14: return "AdditiveSwing ";
15: }
16:
17: public Xint factorial(int n)
18: {
19: if (n < 0)
20: {
21: throw new ArithmeticException("Factorial: n has to be >= 0, but was " + n);
22: }
23:
24: return recFactorial(n);
25: }
26:
27: private Xint recFactorial(int n)
28: {
29: if (n < 2)
30: {
31: return Xint.ONE;
32: }
33:
34: return recFactorial(n / 2).square().multiply(swing(n));
35: }
36:
37: public Xint swing(int n)
38: {
39: Xint w = Xint.ONE;
40:
41: if (n > 1)
42: {
43: n = n + 2;
44: Xint[] s = new Xint[n + 1];
45:
46: s[0] = s[1] = Xint.ZERO;
47: s[2] = w;
48:
49: for (int m = 3; m <= n; m++)
50: {
51: s[m] = s[m - 2];
52: for (int k = m; k >= 2; k--)
53: {
54: s[k] = s[k].add(s[k - 2]);
55: if ((k & 1) == 1) // if k is odd
56: {
57: s[k] = s[k].add(s[k - 1]);
58: }
59: }
60: }
61: w = s[n];
62: }
63: return w;
64: }
65: } // endOfFactorialAdditiveSwing