The binary-split formula
of the factorial of n.

  bigint Factorial(int n)
  {
      bigint p = 1, r = 1;
      loop(n, p, r);
      return r << nminusnumofbits(n);
  }

  loop(int n, reference bigint p, reference bigint r)
  {
      if (n <= 2) return;
      loop(n / 2, p, r);
      p = p * partProduct(n / 2 + 1 + ((n / 2) & 1), n - 1 + (n & 1));
      r = r * p;
  }

  bigint partProduct(int n, int m)
  {
      if (m <= (n + 1)) return (bigint) n;
      if (m == (n + 2)) return (bigint) n * m; 
      int k =  (n + m) / 2;
      if ((k & 1) != 1) k = k - 1;
      return partProduct(n, k) * partProduct(k + 2, m);
  }

  int nminusnumofbits(int v)
  {
      long w = (long)v;
      w -= (0xaaaaaaaa & w) >> 1;
      w = (w & 0x33333333) + ((w >> 2) & 0x33333333);
      w = w + (w >> 4) & 0x0f0f0f0f;
      w += w >> 8;
      w += w >> 16;
      return v - (int)(w & 0xff);
  }

   For example let's trace the computation of 30!.

   init: p = 1, r = 1, then loop:

   p_1          = 3
   p = p * p_1  = 3
   r = r * p    = 3

   p_2          = 5 * 7
   p = p * p_2  = 105
   r = r * p    = 315

   p_3          = 9 * 11 * 13 * 15
   p = p * p_3  = 2027025
   r = r * p    = 638512875

   p_4          = 17 * 19 * 21 * 23 * 25 * 27 * 29
   p = p * p_4  = 6190283353629375
   r = r * p    = 3952575621190533915703125

   return r * 2^26 = 265252859812191058636308480000000
   
   ------
   
   The partial products p_n in turn are computed via the standard
   recursive product, i.e. evaluated (almost) like binary trees:
   
          |                    |                3053876175
          |        19305       |        156009              19575
     35   |    99       195    |     323       483       675     29
   5 * 7  |  9 * 11 * 13 * 15  |   17 * 19 * 21 * 23 * 25 * 27 * 29
   
   -----
   
   Depending on your temperament you now can start to fiddle with the
   implementation, in dependency on your favorite computer language.
   
   Let us suppose that you have four kinds of 'integers', like, for example,
   in Java: The types 'short', 'int', 'long' and 'BigInteger'. And say that
   you are willing to restrict the input value n to something <= 2^15-1 = 32767. 
   Then you might come up with a layered organization of the multiplication 
   tree to enhance the efficiency of the computation.     
                              
   level 3: 'BigInteger' ::                3053876175
   level 2: 'long'       ::        156009              19575
   level 1: 'int'        ::     323       483       675      29
   level 0: 'short'      ::   17 * 19 * 21 * 23 *  25 * 27 * 29
   
   Or choose the Scottish way, asking every time: does a*b fit in an 'short'? 
   yes: put it in one, no: does a*b fit in a 'int'? yes: put it in one, 
   no: put it in a 'long'? yes: put it in one, no: put it in a 'BigInteger'.

Implementations in Java and in C# can be found in the index of the algorithms under the name 'Split Recursive'. They differ from the above pseudo code by incorporating the recursive function 'loop' as a 'while' loop into the factorial function.

Back to the Homepage of Factorial Algorithms.