[gambit-list] Computing a billion decimal digits of pi

Bradley Lucier lucier at math.purdue.edu
Thu Jun 13 17:34:54 EDT 2013


On 06/13/2013 03:12 PM, Bakul Shah wrote:
> On Thu, 13 Jun 2013 10:09:09 +0300 Mikael <mikael.rcv at gmail.com> wrote:
>>> gambit
>>> uses double the space due to portable C code.  Right there you
>>> lose a factor of two!
>> Wait, double space for what, and by what reason?
> You break up a  bignum in "digits" & that you store one digit
> per word. I was told that in gambit the digit size is 32bits
> on a 64bit machine and 16its on a 32bit machine so you are
> fetching/storing at least 2N bits for an N bit bignum.
>
> As to why, you have to ask Gambit's bignum implementor. My
> guess is it makes certain operations easier in a higher level
> language that doesn't have operators for add-with-carry,
> returning double width results etc.

The bits of a bignum are contiguous, there is no empty space in a 
bignum.  Bignums are stored in a twos-complement representation.

Just as for Larceny, the Gambit bignum implementation was inspired by 
the paper

      Jon L White, Reconfigurable, Retargetable Bignums: A Case Study in 
Efficient, Portable Lisp System Building, Proceedings of the ACM 
conference on Lisp & FP, 1986.

The string of bits in a bignum are conceptually divided into unsigned 
specialized "digits" of different sizes depending on their use.

In Gambit, there are "adigits", used for addition, subtraction, 
shifting, and the bitwise-* operations.  These are the largest available 
C numeric type, so if 64-bit "long long" is available, then that's the 
width of an "adigit" even if Scheme words are 32 bits.  (I think one can 
configure Gambit to use 32-bit "adigits" on a 64-bit machine, but I 
don't see any reason to do so.)

There are also "mdigits", used in the naive multiplication and division 
algorithms.  For algorithmic reasons, an mdigit must be representable as 
a fixnum, so they're 16 bits on a 32-bit machine and 32 bits on a 64-bit 
machine.  There are lots of other routines that use mdigits precisely 
because they do fit into a fixnum.

Finally, there are "fdigits" used in the FFT-based multiplication 
routines.  Right now, these are always 8 bits wide.

The primitive operations, which are implemented as C macros in gambit.h, 
are taken from _num.scm and listed after the signature.

I sent a patch to the Gambit mail list in 2009 that documents a bit more 
of this in _num.scm, but it was never applied:

https://mercure.iro.umontreal.ca/pipermail/gambit-list/2009-September/004020.html

Brad

(define-prim (##bignum.negative? x))
(define-prim (##bignum.adigit-length x))
(define-prim (##bignum.adigit-inc! x i))
(define-prim (##bignum.adigit-dec! x i))
(define-prim (##bignum.adigit-add! x i y j carry))
(define-prim (##bignum.adigit-sub! x i y j borrow))
(define-prim (##bignum.mdigit-length x))
(define-prim (##bignum.mdigit-ref x i))
(define-prim (##bignum.mdigit-set! x i mdigit))
(define-prim (##bignum.mdigit-mul! x i y j multiplier carry))
(define-prim (##bignum.mdigit-div! x i y j quotient borrow))
(define-prim (##bignum.mdigit-quotient u j v_n-1))
(define-prim (##bignum.mdigit-remainder u j v_n-1 q-hat))
(define-prim (##bignum.mdigit-test? q-hat v_n-2 r-hat u_j-2))

(define-prim (##bignum.adigit-ones? x i))
(define-prim (##bignum.adigit-zero? x i))
(define-prim (##bignum.adigit-negative? x i))
(define-prim (##bignum.adigit-= x y i))
(define-prim (##bignum.adigit-< x y i))
(define-prim (##bignum.->fixnum x))
(define-prim (##bignum.<-fixnum x))
(define-prim (##bignum.adigit-shrink! x n))
(define-prim (##bignum.adigit-copy! x i y j))
(define-prim (##bignum.adigit-cat! x i hi j lo k divider))
(define-prim (##bignum.adigit-bitwise-and! x i y j))
(define-prim (##bignum.adigit-bitwise-ior! x i y j))
(define-prim (##bignum.adigit-bitwise-xor! x i y j))
(define-prim (##bignum.adigit-bitwise-not! x i))

(define-prim (##bignum.fdigit-length x))
(define-prim (##bignum.fdigit-ref x i))
(define-prim (##bignum.fdigit-set! x i fdigit))




More information about the Gambit-list mailing list