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: public class FactorialPrimeSwing implements IFactorialFunction
9: {
10:
11: private PrimeSieve sieve;
12: private int[] primeList;
13:
14: public FactorialPrimeSwing()
15: {
16: }
17:
18: public String getName()
19: {
20: return "PrimeSwing ";
21: }
22:
23: public Xint factorial(int n)
24: {
25: // For very small n the 'NaiveFactorial' is OK.
26: if (n < 20) { return Xmath.Factorial(n); }
27:
28: sieve = new PrimeSieve(n);
29: int pLen = (int)sieve.getIteration().getNumberOfPrimes();
30: primeList = new int[pLen];
31:
32: return recFactorial(n).shiftLeft(n - Integer.bitCount(n));
33: }
34:
35: private Xint recFactorial(int n)
36: {
37: if (n < 2)
38: {
39: return Xint.ONE;
40: }
41: return recFactorial(n / 2).square().multiply(swing(n));
42: }
43:
44: private Xint swing(int n)
45: {
46: if (n < 33)
47: {
48: return Xint.valueOf(smallOddSwing[n]);
49: }
50:
51: int sqrtN = (int) Math.floor(Math.sqrt(n));
52: IPrimeIteration pIter0 = sieve.getIteration(3, sqrtN);
53: IPrimeIteration pIter1 = sieve.getIteration(sqrtN + 1, n / 3);
54:
55: int count = 0;
56:
57: for (int prime : pIter0)
58: {
59: int q = n, p = 1;
60:
61: while ((q /= prime) > 0)
62: {
63: if ((q & 1) == 1)
64: {
65: p *= prime;
66: }
67: }
68:
69: if (p > 1)
70: {
71: primeList[count++] = p;
72: }
73: }
74:
75: for (int prime : pIter1)
76: {
77: if (((n / prime) & 1) == 1)
78: {
79: primeList[count++] = prime;
80: }
81: }
82:
83: Xint prod = sieve.getPrimorial(n / 2 + 1, n);
84: return prod.multiply(primeList, count);
85: }
86:
87: private static int[] smallOddSwing =
88: { 1, 1, 1, 3, 3, 15, 5, 35, 35, 315, 63, 693, 231, 3003, 429,
89: 6435, 6435, 109395, 12155, 230945, 46189, 969969, 88179,
90: 2028117, 676039, 16900975, 1300075, 35102025, 5014575,
91: 145422675, 9694845, 300540195, 300540195 };
92:
93: } // endOfFactorialPrimeSwingLuschny