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

user_9723204 0
Viewed 323

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?

factorial common-lisp lisp c++ performance
2 Answers

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
user_1243190

Common Lisp imposes (theoretically) no bounds to integers (like Python for example). The storage of an integer is automatically allocated as necessary to represent large integers. On the other side, C++ native integers (eg. int types) are stored in a fixed-size amount of memory. The size is usually between 1 and 8 bytes on most today platforms.

The benefit of the C++ approach is that integer computations can be very quickly since they can be directly compiled to very fast processor instructions (unlike Common Lisp). However, the downside is that when a computed value is too big to fit in a C++ native integer-typed variable, an overflow occurs. The resulting value is not mathematically correct anymore.

Since factorial(1000) is a very big number, it generally does not fit in a native integer. Overflows are the reason why get 0. You can get mathematically correct results using a (non-standard) high-level variable-sized C++ integer type such as the one proposed in the Boost multi-precision library. Using this, the computation of factorial(1000) can also be done very quickly in C++ (and still be mathematically correct).

user_129395570
Related