Fwd: Fwd: Mlucas + GMP

[Torbjörn Granlund]

  I have cloned the repo and tested it myself already. There is a 3%
  speed increase when compared to GMP 6.1.2.
  
How did you measure the 3% improvement?  For one operand size pair, or
for a range?

A 3% speed increase will hardly defend a code replacement.  Niels' small
primes code beats GMP's multiplication code by a large factor for huge
operands.

  However, the main problem is that the FFT multiplication time
  increases exponentially with size, while in the mlucas ( check here:
  http://www.mersenneforum.org/mayer/README.html ), the time increases
  linearly.
  
This seems to be wrong.

1. FFT does not run on exponential time, it in fact runs in near-linear
   time.  It needs O(m log m) coefficient operations, where m <= n, the
   input operand size.

2. I believe mlucas uses FFT for its multiplication.

3. Nobody has published a multiplication algorithm which runs in time
   O(n).


-- 
Torbjörn
Please encrypt, key id 0xC8601622