Why is the calculation of 1000 factorial so fast in Lisp (and shows correct result)?

Question

I have tried to implement naive calculation of the factorial in Lisp.

(defun factorial (n)
  (if (equal n 1)
    1
    (* n (factorial (- n 1)))))

The code works for small numbers (< 10) as one would expect. However, I have been very surprised it also works for much higher numbers (e.g 1000) and the result is calculated almost instantly.

On the other hand, in C++ the following code retrieves 0 for factorial(1000).

long long unsigned factorial(int n)
{
    if(n == 1) return 1;
    return n * factorial(n-1);
}

Why is the calculation in Lisp so fast and how is the number stored in memory?

Answer 1

Common Lisp has bignums and tries to use them when necessary (and unless told otherwise) so that results are mathematically useful for most users: non-computing people usually do not expect modulo arithmetics over powers of 2.

You could have a look at how bignums are implemented (e.g. sbcl) to better understand how they work, how memory is allocated, and why they are fast. There is a lot of work behind bignums to make them fast in practice (the only problem I ever had with bignums is printing them (especially in Emacs)).

The long long unsigned type should be at least 64bits wide (in C++ the width is always a power of 2, but I am not sure the standard requires it), and unsigned integers are defined to have a wrap-around semantics. You obtain 0 because the factorial is a multiple of 2⁶⁴

(mod (factorial 1000) (expt 2 64))
0

In fact, Legendre's formula can be used to determine the highest exponent v such that 2^v divides 1000!:

CL-USER> (loop
            with p = 2
            with n = 1000
            for i from 1
            for v = (floor n (expt p i))
            while (plusp v)
              sum v)
994

We can confirm that (expt 2 994) does divides that big number:

CL-USER> (mod (factorial 1000) (expt 2 994))
0

But (expt 2 995) does not:

CL-USER> (mod (factorial 1000) (expt 2 995))
167423219872854268898191413915625282900219501828989626163085998182867351738271269139562246689952477832436667643367679191435491450889424069312259024604665231311477621481628609147204290704099549091843034096141351171618467832303105743111961624157454108040174944963852221369694216119572256044331338563584