1: package de.luschny.math.factorial;
2:
3: import de.luschny.math.arithmetic.Xint;
4:
5: public class FactorialSwingDouble implements IFactorialFunction
6: {
7:
8: public FactorialSwingDouble()
9: {
10: }
11:
12: public String getName()
13: {
14: return "SwingDouble ";
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: return recFactorial(n / 2).square().multiply(swing(n));
34: }
35:
36: private Xint swing(int n)
37: {
38: boolean oddN = (n & 1) == 1;
39: boolean div = false;
40: long h = n / 2;
41:
42: switch ((n / 2) % 4)
43: {
44: case 0:
45: h = oddN ? h + 1 : 1;
46: break;
47: case 1:
48: h = oddN ? 2 * (h + 2) : 2;
49: break;
50: case 2:
51: h = oddN ? 2 * (h + 1) * (h + 3) : 2 * (h + 1);
52: div = n > 7;
53: break;
54: case 3:
55: h = oddN ? 4 * (h + 2) * (h + 4) : 4 * (h + 2);
56: div = n > 7;
57: break;
58: }
59:
60: Xint b = Xint.valueOf(h);
61:
62: long D = 1, N = oddN ? 2 * n : 2 * (n - 1);
63:
64: for (int i = n / 8; i > 0; --i)
65: {
66: long num = N * (N - 4), g = num;
67: long den = D * (D + 1), f = den;
68:
69: N -= 8;
70: D += 2;
71:
72: while (f != 0)
73: {
74: long t = g % f;
75: g = f;
76: f = t;
77: }
78:
79: b = b.multiply(num / g).divide(den / g);
80: }
81:
82: if (div)
83: {
84: b = b.divide(n / 4);
85: }
86:
87: return b;
88: }
89: } // endOfSwingDouble