Fwd: Fwd: Mlucas + GMP

Torbjörn Granlund tg at gmplib.org
Wed Feb 7 10:17:27 UTC 2018

  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

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

Please encrypt, key id 0xC8601622

More information about the gmp-discuss mailing list