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

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?

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