# 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