FactorialPoorMans
1: // The Poor Man's Implementation of the factorial.
2: // All math is on board, no additional libraries
3: // are needed. Good enough to compute the factorial
4: // up to n=10000 in a few seconds.
5:
6: namespace Luschny.Math.Factorial
7: {
8: public class FactorialPoorMans
9: {
10: public FactorialPoorMans() { }
11:
12: private long N;
13:
14: public string Factorial(int n)
15: {
16: if (n < 0)
17: {
18: throw new System.ArgumentException(
19: ": n >= 0 required, but was " + n);
20: }
21:
22: if (n < 2) return "1";
23:
24: var p = new DecInteger(1);
25: var r = new DecInteger(1);
26:
27: N = 1;
28:
29: int h = 0, shift = 0, high = 1;
30: int log2n = (int)System.Math.Floor(System.Math.Log(n) * 1.4426950408889634);
31:
32: while (h != n)
33: {
34: shift += h;
35: h = n >> log2n--;
36: int len = high;
37: high = (h - 1) | 1;
38: len = (high - len) / 2;
39:
40: if (len > 0)
41: {
42: p = p * Product(len);
43: r = r * p;
44: }
45: }
46:
47: r = r * DecInteger.Pow2(shift);
48: return r.ToString();
49: }
50:
51: private DecInteger Product(int n)
52: {
53: int m = n / 2;
54: if (m == 0) return new DecInteger(N += 2);
55: if (n == 2) return new DecInteger((N += 2) * (N += 2));
56: return Product(n - m) * Product(m);
57: }
58: } // endOfFactorialPoorMans
59:
60: internal class DecInteger
61: {
62: private const long mod = 100000000L;
63: private int[] digits;
64: private int digitsLength;
65:
66: public DecInteger(long value)
67: {
68: digits = new int[] { (int)value, (int)(value >> 32) };
69: digitsLength = 2;
70: }
71:
72: private DecInteger(int[] digits, int length)
73: {
74: this.digits = digits;
75: digitsLength = length;
76: }
77:
78: public static DecInteger Pow2(int e)
79: {
80: if (e < 31) return new DecInteger((int)System.Math.Pow(2, e));
81: return Pow2(e / 2) * Pow2(e - e / 2);
82: }
83:
84: public static DecInteger operator *(DecInteger a, DecInteger b)
85: {
86: int alen = a.digitsLength, blen = b.digitsLength;
87: int clen = alen + blen + 1;
88: int[] digits = new int[clen];
89:
90: for (int i = 0; i < alen; i++)
91: {
92: long temp = 0;
93: for (int j = 0; j < blen; j++)
94: {
95: temp = temp + ((long)a.digits[i] * (long)b.digits[j]) + digits[i + j];
96: digits[i + j] = (int)(temp % mod);
97: temp = temp / mod;
98: }
99: digits[i + blen] = (int)temp;
100: }
101:
102: int k = clen - 1;
103: while (digits[k] == 0) k--;
104:
105: return new DecInteger(digits, k + 1);
106: }
107:
108: public override string ToString()
109: {
110: var sb = new System.Text.StringBuilder(digitsLength * 10);
111: sb = sb.Append(digits[digitsLength - 1]);
112: for (int j = digitsLength - 2; j >= 0; j--)
113: {
114: sb = sb.Append((digits[j] + (int)mod).ToString().Substring(1));
115: }
116: return sb.ToString();
117: }
118: }
119: }
120:
121: // public static void Main (string[] arguments)
122: // {
123: // int n = 1000;
124: // if (arguments.Length != 0)
125: // {
126: // n = System.Convert.ToInt32(arguments[0]);
127: // }
128: // else
129: // {
130: // System.Console.WriteLine("Please give an argument!");
131: // }
132: // FactorialPoorMans f = new FactorialPoorMans();
133: // System.Console.WriteLine(n + "! = " + f.Factorial(n));
134: // System.Console.ReadLine();
135: // }
~bye