1: package de.luschny.math.factorial;
2:
3: import java.util.ArrayList;
4: import java.util.concurrent.Callable;
5: import java.util.concurrent.ExecutorService;
6: import java.util.concurrent.Executors;
7: import java.util.concurrent.Future;
8:
9: import de.luschny.math.arithmetic.Xint;
10:
11: public class FactorialParallelSwing implements IFactorialFunction
12: {
13: private static int SMALLSWING = 33;
14: private static int SMALLFACT = 17;
15:
16: private ExecutorService exe;
17: private Xint oddFactNdiv4, oddFactNdiv2;
18: private ArrayList<Future<Xint>> tasks;
19: private int taskCounter;
20:
21: public FactorialParallelSwing()
22: {
23: int proc = Runtime.getRuntime().availableProcessors();
24: exe = Executors.newFixedThreadPool(proc);
25: }
26:
27: public final String getName()
28: {
29: return "ParallelSwing ";
30: }
31:
32: public Xint factorial(int n)
33: {
34: if (n < 0)
35: {
36: throw new ArithmeticException("Factorial: n has to be >= 0, but was " + n);
37: }
38:
39: if (n < SMALLFACT)
40: {
41: return Xint.valueOf(smallOddFactorial[n]).shiftLeft(n - Integer.bitCount(n));
42: }
43:
44: oddFactNdiv4 = Xint.ONE;
45: oddFactNdiv2 = Xint.ONE;
46:
47: // -- log2n = floor(log2(n));
48: int log2n = 31 - Integer.numberOfLeadingZeros(n);
49: tasks = new ArrayList<Future<Xint>>(log2n);
50:
51: for(int swn = n; swn >= SMALLSWING; swn >>= 1)
52: {
53: tasks.add(runNewOddSwingTask(swn));
54: taskCounter++;
55: }
56:
57: return oddFactorial(n).shiftLeft(n - Integer.bitCount(n));
58: }
59:
60: private Xint oddFactorial(int n)
61: {
62: Xint oddFact, oddSwing;
63:
64: if (n < SMALLFACT)
65: {
66: return Xint.valueOf(smallOddFactorial[n]);
67: }
68:
69: Xint sqrOddFact = oddFactorial(n / 2).square();
70:
71: if (n < SMALLSWING)
72: {
73: oddSwing = Xint.valueOf(smallOddSwing[n]);
74: }
75: else
76: {
77: int ndiv4 = n / 4;
78: Xint oddFactNd4 = ndiv4 >= SMALLFACT ? oddFactNdiv4 : Xint.valueOf(smallOddFactorial[ndiv4]);
79: oddSwing = getTaskResult(--taskCounter).divide(oddFactNd4);
80: }
81:
82: oddFact = sqrOddFact.multiply(oddSwing);
83:
84: oddFactNdiv4 = oddFactNdiv2;
85: oddFactNdiv2 = oddFact;
86: return oddFact;
87: }
88:
89: private final Future<Xint> runNewOddSwingTask(final int n)
90: {
91: return exe.submit(new Callable<Xint>()
92: {
93: private Xint product(int m, int len)
94: {
95: if (len == 1)
96: {
97: return Xint.valueOf(m);
98: }
99: if (len == 2)
100: {
101: return Xint.valueOf((long) m * (m - 2));
102: }
103:
104: return product(m - (len >> 1) * 2, len - (len >> 1)).
105: multiply(product(m, len >> 1));
106: }
107:
108: public Xint call()
109: {
110: int len = (n - 1) / 4;
111: if ((n % 4) != 2) { len++; }
112:
113: // -- if type(n,odd) then high=n; else high=n-1;
114: int high = n - ((n + 1) & 1);
115:
116: return product(high, len);
117: }
118: });
119: }
120:
121: private Xint getTaskResult(final int n)
122: {
123: try
124: {
125: return (tasks.get(n)).get();
126: }
127: catch (Exception ex)
128: {
129: return Xint.ZERO;
130: }
131: }
132:
133: private static int[] smallOddSwing =
134: { 1, 1, 1, 3, 3, 15, 5, 35, 35, 315, 63, 693, 231, 3003, 429, 6435,
135: 6435, 109395, 12155, 230945, 46189, 969969, 88179, 2028117, 676039,
136: 16900975, 1300075, 35102025, 5014575, 145422675, 9694845, 300540195,
137: 300540195 };
138:
139: private static int[] smallOddFactorial =
140: { 1, 1, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, 155925, 467775, 6081075,
141: 42567525, 638512875, 638512875 };
142:
143: } // endOfFactorialParallelSwing