[plt-scheme] Bignums in Scheme

From: Chongkai Zhu (mathematica at citiz.net)
Date: Wed Jun 22 01:52:38 EDT 2005

  
======= At 2005-06-22, 11:01:57 Marco Morazan wrote: =======
>
>I am writing to inquire if you are aware of any articles/documents
>that describe how bignums (arbitrarily large integers) are implemented
>in Scheme. I am particularly interested in how bignums are represented
>and the algorithms used for bignum arithmetic. I am also looking for
>performance studies (speed and memory) that may exist. Both
>descriptions of native implementations and use of foreign libraries
>are of interest to me.
>
>On a related note, are you aware of any garbage collection algorithms
>for bignums?
>
>I look forward to hearing from you. 
>
>Best wishes, 
>
>Marco


For Scheme, bignum is easy. The computation rule is similar to people
doing decimal computation. We have only ten numbers, 0-9, in a decimal
system. How can we work with arbitrary big numbers? A bignum is 
represented as an array of fixnum. GC regards the ARRAY as a whole.

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.

-
Chongkai Zhu




Posted on the users mailing list.