1: package de.luschny.math.factorial;
2:
3: import de.luschny.math.Xmath;
4: import de.luschny.math.arithmetic.Xint;
5: import de.luschny.math.primes.IPrimeIteration;
6: import de.luschny.math.primes.PrimeSieve;
7:
8: import java.util.HashMap;
9:
10: public class FactorialPrimeSwingCache implements IFactorialFunction
11: {
12:
13: private PrimeSieve sieve;
14: private int[] primeList;
15: private HashMap<Integer, CachedPrimorial> cache;
16:
17: public FactorialPrimeSwingCache()
18: {
19: }
20:
21: public String getName()
22: {
23: return "PrimeSwingCache ";
24: }
25:
26: public Xint factorial(int n)
27: {
28: // For very small n the 'NaiveFactorial' is OK.
29: if (n < 20) { return Xmath.Factorial(n); }
30:
31: cache = new HashMap<Integer, CachedPrimorial>();
32: sieve = new PrimeSieve(n);
33: int piN = sieve.getIteration().getNumberOfPrimes();
34: primeList = new int[piN];
35:
36: return recFactorial(n).shiftLeft(n - Integer.bitCount(n));
37: }
38:
39: private Xint recFactorial(int n)
40: {
41: if (n < 2)
42: {
43: return Xint.ONE;
44: }
45: return swing(n).multiply(recFactorial(n / 2).square());
46: }
47:
48: private Xint swing(int n)
49: {
50: if (n < 33)
51: {
52: return Xint.valueOf(smallOddSwing[n]);
53: }
54:
55: int rootN = (int) Math.floor(Math.sqrt(n));
56: int count = 0, j = 1, low, high;
57:
58: Xint prod = Xint.ONE;
59:
60: while (true)
61: {
62: high = n / j++;
63: low = n / j++;
64:
65: if (low < rootN)
66: {
67: low = rootN;
68: }
69: if (high - low < 32)
70: {
71: break;
72: }
73:
74: Xint primorial = getPrimorial(low + 1, high);
75:
76: if (!primorial.isONE())
77: {
78: prod = prod.multiply(primorial);
79: }
80: }
81:
82: IPrimeIteration pIter = sieve.getIteration(3, high);
83:
84: for (int prime : pIter)
85: {
86: int q = n, p = 1;
87:
88: while ((q /= prime) > 0)
89: {
90: if ((q & 1) == 1)
91: {
92: p *= prime;
93: }
94: }
95:
96: if (p > 1)
97: {
98: primeList[count++] = p;
99: }
100: }
101:
102: return prod.multiply(primeList, count);
103: }
104:
105: Xint getPrimorial(int low, int high)
106: {
107: // System.out.print("Primorial [" + low + "," + high + "] " );
108: Xint primorial;
109: CachedPrimorial cachedPrimorial = cache.get(low);
110:
111: if (null != cachedPrimorial)
112: {
113: // System.out.println(" <- from Cache");
114: int low1 = cachedPrimorial.high + 1;
115: Xint p = sieve.getPrimorial(low1, high);
116: primorial = p.multiply(cachedPrimorial.value);
117: }
118: else
119: {
120: // System.out.println(" <- from Sieve");
121: primorial = sieve.getPrimorial(low, high);
122: }
123:
124: cache.put(low, new CachedPrimorial(high, primorial));
125:
126: return primorial;
127: }
128:
129: private static int[] smallOddSwing =
130: { 1, 1, 1, 3, 3, 15, 5, 35, 35, 315, 63, 693, 231, 3003, 429, 6435,
131: 6435, 109395, 12155, 230945, 46189, 969969, 88179, 2028117, 676039,
132: 16900975, 1300075, 35102025, 5014575, 145422675, 9694845,
133: 300540195, 300540195 };
134: }
135:
136: class CachedPrimorial
137: {
138: public int high;
139: public Xint value;
140:
141: CachedPrimorial(int highBound, Xint val)
142: {
143: high = highBound;
144: value = val;
145: }
146: }
147: // endOfFactorialPrimeSwingCache