Fwd: Fwd: Mlucas + GMP

Win C winsto003 at hotmail.com
Wed Feb 7 09:43:50 UTC 2018

-------- Original message --------
From: Win C <winsto003 at hotmail.com>
Date: 07/02/2018 17:08 (GMT+08:00)
To: Torbjörn Granlund <tg at gmplib.org>
Subject: Re: 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.

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.

Therefore, for small numbers GMP does better, but when it comes to large numbers, mlucas wins. And the developer might be willing to co-operate with us. So I think this may be a feasible idea to optimize.

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

Win C <winsto003 at hotmail.com> writes:

  I have tested this FFT program for doing large multiplications, and it
  turns out that it is much faster starting from numbers like
  2^400000. Should we consider integrating it into the GMP? That would
  definitely give us a boost. :D

Much time has been spent on improved FFT multiplication (and squaring)
for GMP; in fact we have developed much faster code ourselves based on
FFTs in multiple small-order prime fields.  (Some of that code is in the
GMP repo area.)

I am not familiar with the packages you mention, nor do I know their
relative performance.

I suppose the main issue with improving GMPs huge operand multiplication
performance is that somebody will need to spend an awful lot of time on
integrating, testing, and tuning the new code.

Please encrypt, key id 0xC8601622

More information about the gmp-discuss mailing list