1: using System;
2: using System.Threading.Tasks;
3: using Xint = System.Numerics.BigInteger;
4: using Xmath = Luschny.Math.MathUtils.Xmath;
5:
6: namespace Luschny.Math.Factorial
7: {
8: public class FactorialParallelSplit : IFactorialFunction
9: {
10: // Same algorithm as FactorialSplit
11: // but computing products using tasks.
12:
13: public FactorialParallelSplit() { }
14:
15: public string Name
16: {
17: get { return "ParallelSplit "; }
18: }
19:
20: private delegate Xint ProductDelegate(int from, int to);
21:
22: public Xint Factorial(int n)
23: {
24: if (n < 0)
25: {
26: throw new System.ArgumentOutOfRangeException(
27: "n", Name + ": n >= 0 required, but was " + n);
28: }
29:
30: if (n < 2) return Xint.One;
31:
32: int log2n = Xmath.FloorLog2(n);
33: ProductDelegate prodDelegate = Product;
34: IAsyncResult[] result = new IAsyncResult[log2n];
35:
36: int high = n, low = n >> 1, shift = low, taskCounter = 0;
37:
38: // -- It is more efficient to add the big intervals
39: // -- first and the small ones later!
40: while ((low + 1) < high)
41: {
42: result[taskCounter++] = prodDelegate.BeginInvoke(low + 1, high, null, null);
43: high = low;
44: low >>= 1;
45: shift += low;
46: }
47:
48: Xint p = Xint.One, r = Xint.One;
49: while (--taskCounter >= 0)
50: {
51: var R = Task.Factory.StartNew<Xint>(() => { return r * p; });
52: var t = p * prodDelegate.EndInvoke(result[taskCounter]);
53: r = R.Result;
54: p = t;
55: }
56:
57: return (r * p) << shift;
58: }
59:
60: private static Xint Product(int n, int m)
61: {
62: const int SEQUENTIAL_THRESHOLD = 7;
63:
64: n = n | 1; // Round n up to the next odd number
65: m = (m - 1) | 1; // Round m down to the next odd number
66:
67: if (m == n)
68: {
69: return new Xint(m);
70: }
71: if (m == (n + 2))
72: {
73: return new Xint((long)n * m);
74: }
75:
76: int k = (n + m) >> 1;
77:
78: if ((m - n) < SEQUENTIAL_THRESHOLD)
79: {
80: return Product(n, k) * Product(k + 1, m);
81: }
82:
83: var left = Task.Factory.StartNew<Xint>(() => Product(n, k));
84: var right = Product(k + 1, m);
85:
86: return left.Result * right;
87: }
88: }
89: }