Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What gives Lisp its excellent math performance?

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?

like image 461
johnbakers Avatar asked Oct 30 '13 09:10

johnbakers


2 Answers

This is a good example that "worse is not always better".

The New Jersey approach

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.

The MIT/Stanford style

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

  • it has to be explicitly requested by the user;
  • the bignums are operated upon in a clumsy way: BigInteger.add(a,b) instead of a+b;
  • the cost is incurred even when the actual number is small and would fit into a machine int.

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!

like image 151
sds Avatar answered Nov 15 '22 20:11

sds


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.

like image 2
Lars Brinkhoff Avatar answered Nov 15 '22 19:11

Lars Brinkhoff