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