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