100! The factorial of 100

published: 18 December 2021 / updated 18 December 2021

Lire cette page en français

The factorial function

The factorial function n! on integers consists in carrying out the multiplication of all integers between 1 and n. Example, for n=10:
10!
is equivalent to:
1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10

Calculation of 100! by google

Let's see what Google answers when asked for the factorial of 100:

Yes. A number with 164 digits! Just that...

No calculator can replace all the digits of 100! nor elsewhere no factorial on integers that are too large.

Coding in FORTH language

The most trivial way to program the factorial function in FORTH language uses recursion:

\ leave FACT n on the stack
: fact ( n -- n!)
    recursive
    dup 1 > 
    if
        dup 1 - fact *
    else
        drop 1
    endif 
;

So, how many 10! ?

10 fact . display 3628800

Factor reduction

Well! The result ends with 3628800!

In fact, nothing surprising. There are 10 in the list of factors:
1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10

The second factor 10 is hidden but easy to find:
1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10

We can therefore rewrite our factorization like this:
1 x 3 x 4 x 6 x 7 x 8 x 9 x 100

Let's see the operation:
1 x 3 x 4 x 6 x 7 x 8 x 9 is equal to 36288.

This 36288 value is the result of reducing factors by 10! but removing all the factors equal to 10 or products of factors equal to 10.

10 is itself the result of factors 2 and 5.

Comptage des facteurs 2 et 5

Revenons d'abord sur notre mot fact. Voyons ses limites avec la version compilée par gForth. gForth a une pile de données sur 64 bits:

10 fact . 3628800  ok
20 fact . 2432902008176640000  ok
21 fact . -4249290049419214848  ok

Le résultat de 21! devient négatif. C'est le signe que le résultat déborde la précision de 64 bits d'un élément de la pile de données.

Le résultat de 20! est 2432902008176640000 qui peut se réécrire 243290200817664 x 10⁴

Si on compte et supprime tous les facteurs 2 et 5 par paires, on pourrait réduire le nombre de facteurs et voir jusqu'à quelle valeur on peut calculer une factorielle sur ces facteurs réduits.

\ leave FACT n on the stack
: fact ( n -- n!)
    recursive
    dup 1 > 
    if
        dup 5 =
        if 
            drop
        else
            dup .
            dup 1 - fact *
        then
    else
        drop 1
    endif 
;