1: /// -------- ToujoursEnBeta
2: /// Author & Copyright : Peter Luschny
3: /// License: LGPL version 3.0 or (at your option)
4: /// Creative Commons Attribution-ShareAlike 3.0
5: /// Comments mail to: peter(at)luschny.de
6: /// Created: 2010-03-01
7:
8: namespace Sharith.Math.Factorial
9: {
10: using XInt = Sharith.Arithmetic.XInt;
11: using XMath = Sharith.Math.MathUtils.XMath;
12:
13: public class Split : IFactorialFunction
14: {
15: public Split() { }
16:
17: public string Name
18: {
19: get { return "Split "; }
20: }
21:
22: private XInt currentN;
23:
24: public XInt Factorial(int n)
25: {
26: if (n < 0)
27: {
28: throw new System.ArgumentOutOfRangeException("n",
29: Name + ": n >= 0 required, but was " + n);
30: }
31:
32: if (n < 2) return XInt.One;
33:
34: XInt p = XInt.One;
35: XInt r = XInt.One;
36: currentN = XInt.One;
37:
38: int h = 0, shift = 0, high = 1;
39: int log2n = XMath.FloorLog2(n);
40:
41: while (h != n)
42: {
43: shift += h;
44: h = n >> log2n--;
45: int len = high;
46: high = (h - 1) | 1;
47: len = (high - len) / 2;
48:
49: if (len > 0)
50: {
51: p *= Product(len);
52: r *= p;
53: }
54: }
55:
56: return r << shift;
57: }
58:
59: private XInt Product(int n)
60: {
61: int m = n / 2;
62: if (m == 0) return currentN += 2;
63: if (n == 2) return (currentN += 2) * (currentN += 2);
64: return Product(n - m) * Product(m);
65: }
66: }
67: } // endOfFactorialBinSplit