[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