I am reading this in a Lisp textbook:
Lisp can perform some amazing feats with numbers, especially when compared with most other languages. For instance, here we’re using the function
expt
to calculate the fifty-third power of 53:
CL> (expt 53 53)
24356848165022712132477606520104725518533453128685640844505130879576720609150223301256150373
Most languages would choke on a calculation involving such a large number.
Yes, that's cool, but the author fails to explain why Lisp can do this more easily and more quickly than other languages.
Surely there is a simple reason, can anyone explain?
This is a good example that "worse is not always better".
The "traditional" languages, like C/C++/Java, have limited range integer arithmetics based on the hardware capabilities, e.g., int32_t
- signed 32-bit numbers which silently overflow when the result does not fit into 32 bits. This is very fast and often seems good enough for practical purposes, but causes subtle hard to find bugs.
Lisp took a different approach.
It has a "small" unboxed integer type fixnum
, and when the result of fixnum arithmetics does not fit into a fixnum
, it is automatically and transparently promoted to an arbitrary size bignum
, so you always get mathematically correct results. This means that, unless the compiler can prove that the result is a fixnum
, it has to add code which will check whether a bignum
has to be allocated. This, actually, should have a 0 cost on modern architecture, but was a non-trivial decision when it was made 4+ decades ago.
The "traditional" languages, when they offer bignum arithmetics, do that in a "library" way, i.e.,
BigInteger.add(a,b)
instead of a+b
;Note that the Lisp approach is quite in line with the Lisp tradition of doing the right thing at a possible cost of some extra complexity. It is also manifested in the automated memory management, which is now mainstream, but was viciously attacked in the past. The lisp approach to integer arithmetics has now been used in some other languages (e.g., python), so the progress is happening!
To add to what wvxvw wrote, it's easier in Lisp because bignums are built into the language. You can juggle large numbers around just as, say, ints in C or Java.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With