[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