[gambit-list] Gambit positively spotted on slashdot
Bradley Lucier
lucier at math.purdue.edu
Fri May 29 01:14:23 EDT 2009
On May 29, 2009, at 12:41 AM, James Long wrote:
>
> Cool. This is a naïve question, but how come "gmp does better than
> Gambit-C on bigint multiply, using FFTs."?
Well ... Both GMP and Gambit use FFT-based multiplication to do very
large bignum multiplications. GMP uses "number-theoretic" FFTs (FFTs
in finite fields, modulo primes < 2^{32}, using the Chinese Remainder
Theorem to deal with larger numbers [I believe this is what they do,
am not completely sure]) written in C and assembler and Gambit uses a
floating-point FFT written in ... Scheme. Also, Gambit's FFT has to
be fairly straightforward to ensure that certain error bounds are
satisfied.
Anyway, it turns out that, in the end, GMP's approach is about twice
as fast as Gambit's approach for large bignum multiplication.
Perhaps Gambit's approach would turn out to be faster if it were
written in C and assembler. Gambit's approach is many times faster
than GMP's approach for very large bignum GCD, but GMP 5 will use a
modified version of Gambit's approach and will again probably turn
out to be faster.
Brad
More information about the Gambit-list
mailing list