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:
7: package de.luschny.math.factorial;
8:
9: public class FactorialPoorMans
10: {
11:
12: public FactorialPoorMans()
13: {
14: }
15:
16: private long N;
17:
18: public String factorial(int n)
19: {
20: if (n < 0)
21: {
22: throw new ArithmeticException("Factorial: n has to be >= 0, but was " + n);
23: }
24:
25: if (n < 2)
26: {
27: return "1";
28: }
29:
30: DecInteger p = new DecInteger(1);
31: DecInteger r = new DecInteger(1);
32:
33: N = 1;
34: int h = 0, shift = 0, high = 1;
35: int log2n = (int) Math.floor(Math.log(n) / Math.log(2));
36:
37: while (h != n)
38: {
39: shift += h;
40: h = n >> log2n--;
41: int len = high;
42: high = (h & 1) == 1 ? h : h - 1;
43: len = (high - len) / 2;
44:
45: if (len > 0)
46: {
47: p = p.multiply(product(len));
48: r = r.multiply(p);
49: }
50: }
51:
52: r = r.multiply(DecInteger.pow2(shift));
53: return r.toString();
54: }
55:
56: private DecInteger product(int n)
57: {
58: int m = n / 2;
59: if (m == 0)
60: {
61: return new DecInteger(N += 2);
62: }
63: if (n == 2)
64: {
65: return new DecInteger((N += 2) * (N += 2));
66: }
67: return product(n - m).multiply(product(m));
68: }
69: } // endOfPoorMansFactorial
70:
71: class DecInteger
72: {
73:
74: private final long mod = 100000000L;
75: private int[] digits;
76: private int digitsLength;
77:
78: public DecInteger(long value)
79: {
80: digits = new int[]
81: { (int) value, (int) (value >>> 32) };
82: digitsLength = 2;
83: }
84:
85: private DecInteger(int[] digits, int length)
86: {
87: this.digits = digits;
88: digitsLength = length;
89: }
90:
91: static public DecInteger pow2(int e)
92: {
93: if (e < 31)
94: {
95: return new DecInteger((int) Math.pow(2, e));
96: }
97: return pow2(e / 2).multiply(pow2(e - e / 2));
98: }
99:
100: public DecInteger multiply(DecInteger b)
101: {
102: int alen = this.digitsLength, blen = b.digitsLength;
103: int clen = alen + blen;
104: int[] digit = new int[clen];
105:
106: for (int i = 0; i < alen; i++)
107: {
108: long temp = 0;
109: for (int j = 0; j < blen; j++)
110: {
111: temp = temp + ((long) this.digits[i]) * ((long) b.digits[j]) + digit[i + j];
112: digit[i + j] = (int) (temp % mod);
113: temp = temp / mod;
114: }
115: digit[i + blen] = (int) temp;
116: }
117:
118: int k = clen - 1;
119: while (digit[k] == 0)
120: {
121: k--;
122: }
123:
124: return new DecInteger(digit, k + 1);
125: }
126:
127: @Override
128: public String toString()
129: {
130: StringBuilder sb = new StringBuilder(digitsLength * 10);
131: sb = sb.append(digits[digitsLength - 1]);
132: for (int j = digitsLength - 2; j >= 0; j--)
133: {
134: sb = sb.append(Integer.toString(digits[j] + (int) mod).substring(1));
135: }
136: return sb.toString();
137: }
138: }
139:
140: // public static void main (String[] arguments)
141: // {
142: // int n = 1000;
143: // if (arguments.length == 0)
144: // {
145: // System.out.println(
146: // "Please enter next time an argument. Computing 1000! now.");
147: // }
148: // else
149: // {
150: // n = Integer.parseInt(arguments[0]);
151: // }
152: //
153: // FactorialPoorMans f = new FactorialPoorMans();
154: // System.out.println(n + "! = " + f.factorial(n));
155: // }