1: package de.luschny.math.factorial;
2:
3: import de.luschny.math.arithmetic.Xint;
4:
5: public class FactorialSplit implements IFactorialFunction
6: {
7:
8: public FactorialSplit()
9: {
10: }
11:
12: public String getName()
13: {
14: return "Split ";
15: }
16:
17: private long N;
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: if (n < 2)
27: {
28: return Xint.ONE;
29: }
30:
31: Xint p = Xint.ONE;
32: Xint r = Xint.ONE;
33: N = 1;
34:
35: // log2n = floor(log2(n));
36: int log2n = 31 - Integer.numberOfLeadingZeros(n);
37: int h = 0, shift = 0, high = 1;
38:
39: while (h != n)
40: {
41: shift += h;
42: h = n >>> log2n--;
43: int len = high;
44: high = (h & 1) == 1 ? h : h - 1;
45: len = (high - len) / 2;
46:
47: if (len > 0)
48: {
49: p = p.multiply(product(len));
50: r = r.multiply(p);
51: }
52: }
53: return r.shiftLeft(shift);
54: }
55:
56: private Xint product(int n)
57: {
58: int m = n / 2;
59: if (m == 0)
60: {
61: return Xint.valueOf(N += 2);
62: }
63: if (n == 2)
64: {
65: return Xint.valueOf((N += 2) * (N += 2));
66: }
67: return product(n - m).multiply(product(m));
68: }
69: } // endOfFactorialSplitRecursive