1:  // The Poor Man's Implementation of the factorial.
   2:  // All math is on board, no additional libraries
   3:  // are needed. Good enough to compute the factorial
   4:  // up to n=10000 in a few seconds.
   5:   
   6:  namespace Luschny.Math.Factorial
   7:  {
   8:      public class FactorialPoorMans
   9:      {
  10:          public FactorialPoorMans() { }
  11:   
  12:          private long N;
  13:   
  14:          public string Factorial(int n)
  15:          {
  16:              if (n < 0)
  17:              {
  18:                  throw new System.ArgumentException(
  19:                  ": n >= 0 required, but was " + n);
  20:              }
  21:   
  22:              if (n < 2) return "1";
  23:   
  24:              var p = new DecInteger(1);
  25:              var r = new DecInteger(1);
  26:   
  27:              N = 1;
  28:   
  29:              int h = 0, shift = 0, high = 1;
  30:              int log2n = (int)System.Math.Floor(System.Math.Log(n) * 1.4426950408889634);
  31:   
  32:              while (h != n)
  33:              {
  34:                  shift += h;
  35:                  h = n >> log2n--;
  36:                  int len = high;
  37:                  high = (h - 1) | 1; 
  38:                  len = (high - len) / 2;
  39:   
  40:                  if (len > 0)
  41:                  {
  42:                      p = p * Product(len);
  43:                      r = r * p;
  44:                  }
  45:              }
  46:   
  47:              r = r * DecInteger.Pow2(shift);
  48:              return r.ToString();
  49:          }
  50:   
  51:          private DecInteger Product(int n)
  52:          {
  53:              int m = n / 2;
  54:              if (m == 0) return new DecInteger(N += 2);
  55:              if (n == 2) return new DecInteger((N += 2) * (N += 2));
  56:              return Product(n - m) * Product(m);
  57:          }
  58:      } // endOfFactorialPoorMans
  59:   
  60:      internal class DecInteger
  61:      {
  62:          private const long mod = 100000000L;
  63:          private int[] digits;
  64:          private int digitsLength;
  65:   
  66:          public DecInteger(long value)
  67:          {
  68:              digits = new int[] { (int)value, (int)(value >> 32) };
  69:              digitsLength = 2;
  70:          }
  71:   
  72:          private DecInteger(int[] digits, int length)
  73:          {
  74:              this.digits = digits;
  75:              digitsLength = length;
  76:          }
  77:   
  78:          public static DecInteger Pow2(int e)
  79:          {
  80:              if (e < 31) return new DecInteger((int)System.Math.Pow(2, e));
  81:              return Pow2(e / 2) * Pow2(e - e / 2);
  82:          }
  83:   
  84:          public static DecInteger operator *(DecInteger a, DecInteger b)
  85:          {
  86:              int alen = a.digitsLength, blen = b.digitsLength;
  87:              int clen = alen + blen + 1;
  88:              int[] digits = new int[clen];
  89:   
  90:              for (int i = 0; i < alen; i++)
  91:              {
  92:                  long temp = 0;
  93:                  for (int j = 0; j < blen; j++)
  94:                  {
  95:                      temp = temp + ((long)a.digits[i] * (long)b.digits[j]) + digits[i + j];
  96:                      digits[i + j] = (int)(temp % mod);
  97:                      temp = temp / mod;
  98:                  }
  99:                  digits[i + blen] = (int)temp;
 100:              }
 101:   
 102:              int k = clen - 1;
 103:              while (digits[k] == 0) k--;
 104:   
 105:              return new DecInteger(digits, k + 1);
 106:          }
 107:   
 108:          public override string ToString()
 109:          {
 110:              var sb = new System.Text.StringBuilder(digitsLength * 10);
 111:              sb = sb.Append(digits[digitsLength - 1]);
 112:              for (int j = digitsLength - 2; j >= 0; j--)
 113:              {
 114:                  sb = sb.Append((digits[j] + (int)mod).ToString().Substring(1));
 115:              }
 116:              return sb.ToString();
 117:          }
 118:      }
 119:  }
 120:   
 121:  // public static void Main (string[] arguments)
 122:  // {
 123:  //    int n = 1000;
 124:  //    if (arguments.Length != 0)
 125:  //    {
 126:  //        n = System.Convert.ToInt32(arguments[0]);
 127:  //    }
 128:  //    else
 129:  //    {
 130:  //        System.Console.WriteLine("Please give an argument!");
 131:  //    }
 132:  //    FactorialPoorMans f = new FactorialPoorMans();
 133:  //    System.Console.WriteLine(n + "! = " + f.Factorial(n));
 134:  //    System.Console.ReadLine();
 135:  // }