Factorial by Binary Splitting

Here are some notes from my program XICalc - Extra Precision Integer Calculator http://www.oocities.org/hjsmithh/download.html#XICalc :

Factorial by binary splitting:

The factorial of n = n! = Fac(n) = 1 * 2 * 3 * ... * n. The old slow method
computes Fac(n) by

      x1 = 1, x2 = 2*x1, x3 = 3*x2, ... x(n) = n*x(n-1), Fac(n) = x(n).

For the binary splitting method, define the product

      Pr(a, b) = (b+1)*(b+2)* ... * (a-1)*a = Fac(a) / Fac(b).

This is computed by

      Pr(a, b) = Pr(a, (a+b)/2) * Pr((a+b)/2, b),

where the two terms in the product are computed recursively in the same way
until a-b is small:

      d = a-b; m = (a+b)/2 // integer divide
      If (d) > 3, Pr(a, b) = Pr(a, m) * Pr(m, b);
      Else if (d) == 0, Pr(a, b) = 1;
      Else if (d) == 1, Pr(a, b) = a;
      Else if (d) == 2, Pr(a, b) = a*(a-1);
      Else if (d) == 3, Pr(a, b) = a*(a-1)*(a-2);
      Else Pr(a, b) = 0.

For the factorial

      Fac(n) = Pr(n, 0).

For large n, this method is much faster than the old slow method.

See: http://numbers.computation.free.fr/Constants/Algorithms/splitting.html

Return to Number Theory, Algorithms, and Real Functions
Return to Harry's Home Page

---

This page accessed times since April 04, 2006.
Page created by: hjsmithh@sbcglobal.net
Changes last made on Monday, 06-Aug-07 20:51:27 PDT

---