Even faster integer multiplication

[kriesel]

Originally Posted by Mysticial

Or to bluntly summarize: GMP hasn't really kept up-to-date in the area in many years. So at this point, GIMPS is miles ahead of GMP. y-cruncher is somewhere in the middle, but a lot closer to GIMPS than GMP.

To what extent do your GMP comments also apply to MPIR?
(That's http://mpir.org/, for anyone unfamiliar)
http://mpir.org/news.html shows no content since early 2017.

[Mysticial]

Originally Posted by kriesel

To what extent do your GMP comments also apply to MPIR?
(That's http://mpir.org/, for anyone unfamiliar)
http://mpir.org/news.html shows no content since early 2017.

As far as I can tell, they're the same. MPIR might be slightly ahead since I remember they mention switching to FLINT's SSA or something like that. But that doesn't really change anything.

The main difference is that the MPIR devs actually considered doing parallelization. But IIRC, they quickly realized it's not that simple with the whole API and framework and everything.

The MPIR devs have also mentioned not having any man-power to continue the project beyond basic maintenance.

[paulunderwood]

I am no FFT expert, but I wonder if this paper leads to any speed ups for finding primes.

https://arxiv.org/abs/1911.07124

A New Number Theoretic Transform(NTT), which is a form of FFT, is introduced, that is faster than FFTs. Also, a multiplication algorithm is introduced that uses this to perform integer multiplication faster than O(n log n). It uses preprocessing to achieve an upper bounds of (n log n/(log log n/ log log log n).
Also, we explore the possibility of O(n) time multiplication via NTTs that require only O(n) operations, using preprocessing.

Skimming through the paper I see that a prime "P" must be as bigger than "N"

FYI.

[R.D. Silverman]

Originally Posted by paulunderwood

I am no FFT expert, but I wonder if this paper leads to any speed ups for finding primes.

https://arxiv.org/abs/1911.07124



Skimming through the paper I see that a prime "P" must be as bigger than "N"

FYI.

The paper is very badly written. It also ignores the cost of building the required tables
(and their size). It fails to discuss any kind of implementation or give benchmarks.
There is no discussion of how large the numbers need to be for practicality.

It VERY frequently introduces variables and notation without definition. It is
sloppy with notation. e.g. k log n log log n/k fails to parenthesize (n/k). etc. etc.

There are so many errors of this type that I did not bother to try to check it for
correctness. If I were asked to referee this paper, I would reject it. There are too many
flaws to even suggest a partial re-write.

[dabler]

Just for fun, here is another algorithm for fast multiplication of large integers, which is most likely only of theoretical interest. The time complexity of multiplying two numbers is \(O(kn)\), where the \(k\) is the number of odd steps in the Collatz trajectory of the first multiplicand.

[R. Gerbicz]

Originally Posted by dabler

Just for fun, here is another algorithm for fast multiplication of large integers, which is most likely only of theoretical interest. The time complexity of multiplying two numbers is \(O(kn)\), where the \(k\) is the number of odd steps in the Collatz trajectory of the first multiplicand.

If the running time is correct then it is not even better than the trivial O(n^2) method, because for random numbers on average k>=const*n. Maybe a variant of the trivial https://mathworld.wolfram.com/Russia...plication.html , I don't have the full "paper".

[dabler]

Yes, the algorithm is efficient only for a specific class of numbers, as explained in the paper. The long multiplication is better on average.