On 06/13/2013 03:12 PM, Bakul Shah wrote:
On Thu, 13 Jun 2013 10:09:09 +0300 Mikael mikael.rcv@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...
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))