1: package de.luschny.math.factorial;
2:
3: import de.luschny.math.arithmetic.Xint;
4:
5: import java.util.ArrayList;
6: import java.util.List;
7: import java.util.concurrent.Callable;
8: import java.util.concurrent.ExecutorService;
9: import java.util.concurrent.Executors;
10: import java.util.concurrent.Future;
11:
12: public class FactorialParallelSplit implements IFactorialFunction
13: {
14: // Same algorithm as Split
15: // but computing products concurrently.
16:
17: public FactorialParallelSplit()
18: {
19: }
20:
21: public String getName()
22: {
23: return "ParallelSplit ";
24: }
25:
26: public Xint factorial(int n)
27: {
28: if (n < 0)
29: {
30: throw new ArithmeticException("Factorial: n has to be >= 0, but was " + n);
31: }
32:
33: if (n < 2)
34: {
35: return Xint.ONE;
36: }
37:
38: // -- log2n = floor(log2(n));
39: int log2n = 31 - Integer.numberOfLeadingZeros(n);
40: int proc = Runtime.getRuntime().availableProcessors();
41:
42: ExecutorService exe = Executors.newFixedThreadPool(proc);
43: ArrayList<Callable<Xint>> tasks = new ArrayList<Callable<Xint>>(log2n);
44:
45: int high = n, low = n >>> 1, shift = low, taskCounter = 0;
46:
47: // -- It is more efficient to add the big intervals
48: // -- first and the small ones later!
49: while ((low + 1) < high)
50: {
51: tasks.add(new Product(low + 1, high));
52: high = low;
53: low >>= 1;
54: shift += low;
55: taskCounter++;
56: }
57:
58: Xint p = Xint.ONE, r = Xint.ZERO;
59:
60: try
61: {
62: List<Future<Xint>> products = exe.invokeAll(tasks);
63:
64: Future<Xint> R = exe.submit(new Callable<Xint>()
65: {
66: public Xint call()
67: {
68: return Xint.ONE;
69: }
70: });
71:
72: while (--taskCounter >= 0)
73: {
74: p = p.multiply(products.get(taskCounter).get());
75: R = exe.submit(new Multiply(R.get(), p));
76: }
77:
78: r = R.get();
79: }
80: catch (Throwable e)
81: {
82: e.printStackTrace();
83: }
84:
85: exe.shutdownNow();
86: return r.shiftLeft(shift);
87: }
88:
89: final class Multiply implements Callable<Xint>
90: {
91: private final Xint a, b;
92:
93: public Multiply(Xint a, Xint b)
94: {
95: this.a = a;
96: this.b = b;
97: }
98:
99: public Xint call()
100: {
101: return a.multiply(b);
102: }
103: }
104:
105: } // endOfFactorialSplitRecursive
106:
107: final class Product implements Callable<Xint>
108: {
109: private final int n, m;
110:
111: public Product(int n, int m)
112: {
113: this.n = n;
114: this.m = m;
115: }
116:
117: public Xint call()
118: {
119: return product(n, m);
120: }
121:
122: public static Xint product(int n, int m)
123: {
124: n = n | 1; // Round n up to the next odd number
125: m = (m - 1) | 1; // Round m down to the next odd number
126:
127: if (m == n)
128: {
129: return Xint.valueOf(m);
130: }
131: if (m == (n + 2))
132: {
133: return Xint.valueOf((long) n * m);
134: }
135:
136: int k = (n + m) >>> 1;
137: return product(n, k).multiply(product(k + 1, m));
138: }
139: }