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:  namespace Sharith.Math.Factorial 
   9:  {
  10:      using XInt = Sharith.Arithmetic.XInt;
  11:      using XMath = Sharith.Math.MathUtils.XMath;
  12:   
  13:      public class Split : IFactorialFunction 
  14:      {
  15:          public Split() { }
  16:   
  17:          public string Name
  18:          {
  19:              get { return "Split               "; }
  20:          }
  21:   
  22:          private XInt currentN;
  23:   
  24:          public XInt Factorial(int n)
  25:          {
  26:              if (n < 0)
  27:              {
  28:                  throw new System.ArgumentOutOfRangeException("n",
  29:                  Name + ": n >= 0 required, but was " + n);
  30:              }
  31:   
  32:              if (n < 2) return XInt.One;
  33:   
  34:              XInt p = XInt.One;
  35:              XInt r = XInt.One;
  36:              currentN = XInt.One;
  37:   
  38:              int h = 0, shift = 0, high = 1;
  39:              int log2n = XMath.FloorLog2(n);
  40:   
  41:              while (h != n)
  42:              {
  43:                  shift += h;
  44:                  h = n >> log2n--;
  45:                  int len = high;
  46:                  high = (h - 1) | 1;
  47:                  len = (high - len) / 2;
  48:   
  49:                  if (len > 0)
  50:                  {
  51:                      p *= Product(len);
  52:                      r *= p;
  53:                  }
  54:              }
  55:   
  56:              return r << shift;
  57:          }
  58:   
  59:          private XInt Product(int n)
  60:          {
  61:              int m = n / 2;
  62:              if (m == 0) return currentN += 2;
  63:              if (n == 2) return (currentN += 2) * (currentN += 2);
  64:              return Product(n - m) * Product(m);
  65:          }
  66:      }
  67:  } // endOfFactorialBinSplit