1: using Xint = System.Numerics.BigInteger;
2: using Xmath = Luschny.Math.MathUtils.Xmath;
3:
4: namespace Luschny.Math.Factorial
5: {
6: public class FactorialSplit : IFactorialFunction
7: {
8: public FactorialSplit() { }
9:
10: public string Name
11: {
12: get { return "Split "; }
13: }
14:
15: private long currentN;
16:
17: public Xint Factorial(int n)
18: {
19: if (n < 0)
20: {
21: throw new System.ArgumentOutOfRangeException("n",
22: Name + ": n >= 0 required, but was " + n);
23: }
24:
25: if (n < 2) return Xint.One;
26:
27: Xint p = Xint.One;
28: Xint r = Xint.One;
29: currentN = 1;
30:
31: int h = 0, shift = 0, high = 1;
32: int log2n = Xmath.FloorLog2(n);
33:
34: while (h != n)
35: {
36: shift += h;
37: h = n >> log2n--;
38: int len = high;
39: high = (h - 1) | 1;
40: len = (high - len) / 2;
41:
42: if (len > 0)
43: {
44: p *= Product(len);
45: r *= p;
46: }
47: }
48:
49: return r << shift;
50: }
51:
52: private Xint Product(int n)
53: {
54: int m = n / 2;
55: if (m == 0) return (Xint)(currentN += 2);
56: if (n == 2) return (Xint)((currentN += 2) * (currentN += 2));
57: return Product(n - m) * Product(m);
58: }
59: }
60:
61: } // endOfFactorialBinSplit