GMP 4.4 remaining tasks

[Torbjorn Granlund]

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
operations...

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.

-- 
Torbjörn