GMP 4.4 remaining tasks
tg at gmplib.org
Tue Dec 8 13:06:26 CET 2009
bodrato at mail.dm.unipi.it writes:
I did some test with a Karatsuba_mod_bnp1. IIRC one saves half an addition
(wrt toom22 that already saves the other half :-) and I was not able to
measure any saving...
[I couldn't keep quiet for very long...]
One should really do this using FFT over complex numbers. As Paul
pointed out, there are now good error bounds for limited-length
transforms, so there is no accuracy gambling involved. Of course, such
an FFT would need assembly code to make best use of SIMD floating-point
I suspect a well-written FFT over C could have a threshold over plain
basecase code of just a few dozen limbs. Of course, that code could
also help the present FFT code, for its point-wise multiplies.
More information about the gmp-devel