What gives Lisp its excellent math performance?
Asked Answered
M

2

5

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?

Maccarthy answered 30/10, 2013 at 9:41 Comment(1)
Many languages of the day didn't try to abstract arithmetics from hardware-dependant modulo arithmetics. Many popular languages still don't do it (Java or C++). However many have "bignum" or "biginteger" libraries. Being second-rate citizens, these libraries often incur an overhead, such as boxing in Java.Transceiver
F
12

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!

Fountain answered 30/10, 2013 at 13:43 Comment(0)
M
2

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.

Molality answered 30/10, 2013 at 10:35 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.