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.ArrayList;
9: import java.util.List;
10: import java.util.concurrent.*;
11:
12: public class FactorialParallelPrimeSplit implements IFactorialFunction
13: {
14:
15: public FactorialParallelPrimeSplit()
16: {
17: }
18:
19: public String getName()
20: {
21: return "ParallelPrimeSplit";
22: }
23:
24: public Xint factorial(int n)
25: {
26: // For very small n the 'NaiveFactorial' is OK.
27: if (n < 20) { return Xmath.Factorial(n); }
28:
29: PrimeSieve sieve = new PrimeSieve(n);
30:
31: int proc = Runtime.getRuntime().availableProcessors();
32: int log2n = 31 - Integer.numberOfLeadingZeros(n);
33:
34: ExecutorService exe = Executors.newFixedThreadPool(proc);
35: ArrayList<Callable<Xint>> swingTasks = new ArrayList<Callable<Xint>>(log2n);
36:
37: Xint r = Xint.ONE, p = Xint.ONE;
38: Xint rl = Xint.ONE, t;
39:
40: int h = 0, shift = 0;
41:
42: while (h != n)
43: {
44: shift += h;
45: h = n >> log2n--;
46: if (h > 2)
47: {
48: swingTasks.add(new Swing(sieve, h));
49: }
50: }
51:
52: try
53: {
54: List<Future<Xint>> swings = exe.invokeAll(swingTasks);
55: int taskCounter = swings.size();
56:
57: for (int i = 0; i < taskCounter; i++)
58: {
59: t = rl.multiply(swings.get(i).get());
60: p = p.multiply(t);
61: rl = r;
62: r = r.multiply(p);
63: }
64: }
65: catch (Throwable e)
66: {
67: e.printStackTrace();
68: }
69:
70: exe.shutdownNow();
71: return r.shiftLeft(shift);
72: }
73:
74: private static int[] smallOddSwing =
75: { 1, 1, 1, 3, 3, 15, 5, 35, 35, 315, 63, 693, 231, 3003, 429,
76: 6435, 6435, 109395, 12155, 230945, 46189, 969969, 88179, 2028117,
77: 676039, 16900975, 1300075, 35102025, 5014575, 145422675, 9694845,
78: 300540195, 300540195 };
79:
80: // -- Concurrent execution of this Class should not fail.
81: final class Swing implements Callable<Xint>
82: {
83:
84: private final PrimeSieve Sieve;
85: private final int N;
86:
87: public Swing(PrimeSieve sieve, int n)
88: {
89: Sieve = sieve;
90: N = n;
91: }
92:
93: // -- Returns swing(n)
94: public Xint call() throws Exception
95: {
96: if (N < 33)
97: {
98: return Xint.valueOf(smallOddSwing[N]);
99: }
100:
101: FutureTask<Xint> Primorial = new FutureTask<Xint>(new Callable<Xint>()
102: {
103: public Xint call()
104: {
105: return Sieve.getPrimorial(N / 2 + 1, N);
106: }
107: });
108:
109: new Thread(Primorial).start();
110: Xint primeProduct = lowSwing();
111: return primeProduct.multiply(Primorial.get());
112: }
113:
114: private Xint lowSwing()
115: {
116: int sqrtN = (int) Math.floor(Math.sqrt(N));
117: IPrimeIteration pIter0 = Sieve.getIteration(3, sqrtN);
118: IPrimeIteration pIter1 = Sieve.getIteration(sqrtN + 1, N / 3);
119:
120: int piN = pIter0.getNumberOfPrimes() + pIter1.getNumberOfPrimes();
121: final int[] primeList = new int[piN];
122: int count = 0;
123:
124: for (int prime : pIter0)
125: {
126: int q = N, p = 1;
127:
128: while ((q /= prime) > 0)
129: {
130: if ((q & 1) == 1)
131: {
132: p *= prime;
133: }
134: }
135:
136: if (p > 1)
137: {
138: primeList[count++] = p;
139: }
140: }
141:
142: for (int prime : pIter1)
143: {
144: if (((N / prime) & 1) == 1)
145: {
146: primeList[count++] = prime;
147: }
148: }
149:
150: return Xint.product(primeList, 0, count);
151:
152: } // endOfLowSwing
153: } // endOfSwing
154: } // endOfFactorial