[plt-scheme] Bignums in Scheme

From: karczma at info.unicaen.fr (karczma at info.unicaen.fr)
Date: Wed Jun 22 03:42:01 EDT 2005

Chongkai Zhu writes: 

>>I am writing to inquire if you are aware of any articles/documents
>>that describe how bignums (arbitrarily large integers) are implemented
>>in Scheme. 
>>On a related note, are you aware of any garbage collection algorithms
>>for bignums?

> For Scheme, bignum is easy. The computation rule is similar to people
> doing decimal computation. ... 
> There does exist totally different implemention, implemention with better
> performance (better in speed and same in memory). The idea is based on 
> Chinese Remainder algorithm. If you are interested, plrease refer to 
> books about Computer Algebra, which will tell you both these two approach
> in detail. Or you can contact me again.

Do you claim that there is really somewhere a Scheme implementation
based on the modular representation??
Never heard about.
We are NOT speaking about theory, this is well known, but about practical
realisations, with some experience concerning the efficiency. 

As far as I know, the sources bignum.c of MzScheme are based on GMP.
They implement Karatsuba, but no modular stuff (nor Schönhage-Strassen,
nor other exotics...) 

For practical purposes the modular, "Chines" method has some inconveniences,
the conversions are clumsy, the (<,>) relations are costly, etc. So, it
lost somehow a good part of its sex appeal... 

Jerzy Karczmarczuk 

Posted on the users mailing list.