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