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:  }