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