Fwd: Fwd: Mlucas + GMP
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