GMP 4.4 remaining tasks

Torbjorn Granlund tg at
Tue Dec 8 13:06:26 CET 2009

bodrato at 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 mailing list