1: package de.luschny.math.factorial;
2:
3: import de.luschny.math.arithmetic.Xint;
4:
5: public class FactorialSwing implements IFactorialFunction
6: {
7:
8: public FactorialSwing()
9: {
10: }
11:
12: public String getName()
13: {
14: return "Swing ";
15: }
16:
17: private Xint ndiv4OddFact, ndiv2OddFact;
18:
19: public Xint factorial(int n)
20: {
21: if (n < 0)
22: {
23: throw new ArithmeticException("Factorial: n has to be >= 0, but was " + n);
24: }
25:
26: ndiv4OddFact = ndiv2OddFact = Xint.ONE;
27:
28: return oddFactorial(n).shiftLeft(n - Integer.bitCount(n));
29: }
30:
31: private Xint oddFactorial(int n)
32: {
33: Xint oddFact;
34: if (n < 17)
35: {
36: oddFact = Xint.valueOf(smallOddFactorial[n]);
37: }
38: else
39: {
40: oddFact = oddFactorial(n / 2).square().multiply(oddSwing(n));
41: }
42:
43: ndiv4OddFact = ndiv2OddFact;
44: ndiv2OddFact = oddFact;
45: return oddFact;
46: }
47:
48: private Xint oddSwing(int n)
49: {
50: if (n < 33)
51: {
52: return Xint.valueOf(smallOddSwing[n]);
53: }
54:
55: int len = (n - 1) / 4;
56: if ((n % 4) != 2)
57: {
58: len++;
59: }
60: int high = n - ((n + 1) & 1);
61:
62: int ndiv4 = n / 4;
63: Xint oddFact = ndiv4 < 17 ? Xint.valueOf(smallOddFactorial[ndiv4]) : ndiv4OddFact;
64:
65: return product(high, len).divide(oddFact);
66: }
67:
68: private static Xint product(int m, int len)
69: {
70: if (len == 1)
71: {
72: return Xint.valueOf(m);
73: }
74: if (len == 2)
75: {
76: return Xint.valueOf((long) m * (m - 2));
77: }
78:
79: int hlen = len >>> 1;
80: return product(m - hlen * 2, len - hlen).multiply(product(m, hlen));
81: }
82:
83: private static int[] smallOddSwing =
84: { 1, 1, 1, 3, 3, 15, 5, 35, 35, 315, 63, 693, 231, 3003, 429, 6435, 6435, 109395, 12155, 230945, 46189, 969969,
85: 88179, 2028117, 676039, 16900975, 1300075, 35102025, 5014575, 145422675, 9694845, 300540195, 300540195 };
86:
87: private static int[] smallOddFactorial =
88: { 1, 1, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, 155925, 467775, 6081075, 42567525, 638512875, 638512875 };
89:
90: } // endOfFactorialSwing