Fwd: Fwd: Fwd: Mlucas + GMP

[Win C]

This is not based on theoratical caluclations, rather on experimental try and error. I ran both on ubuntu on an Intel i5, and did 750000 squares. At last mlucas did it in 10 min while gmp did it in 25 min.


-------- Original message --------
From: Torbjörn Granlund <tg at gmplib.org>
Date: 07/02/2018 18:17 (GMT+08:00)
To: Win C <winsto003 at hotmail.com>
Cc: gmp-discuss at gmplib.org
Subject: Re: Fwd: Fwd: Mlucas + GMP


  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