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.

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