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