c++performancelispcommon-lispfactorial

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?


Solution

  • 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 264

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

    In fact, Legendre's formula can be used to determine the highest exponent v such that 2v 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