mersenneforum.org Even faster integer multiplication
 Register FAQ Search Today's Posts Mark Forums Read

2019-04-18, 22:38   #12
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

EFD16 Posts

Quote:
 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.
(That's http://mpir.org/, for anyone unfamiliar)
http://mpir.org/news.html shows no content since early 2017.

2019-04-18, 23:06   #13
Mysticial

Sep 2016

32910 Posts

Quote:
 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.

2019-11-19, 02:52   #14
paulunderwood

Sep 2002
Database er0rr

2·1,607 Posts
Faster Integer Multiplication Using Preprocessing

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

Quote:
 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.

Last fiddled with by paulunderwood on 2019-11-19 at 03:00

2019-11-20, 14:01   #15
R.D. Silverman

Nov 2003

2×3,709 Posts

Quote:
 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.

 2020-05-21, 09:26 #16 dabler     "David Barina" Jul 2016 Brno 25 Posts 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. Last fiddled with by retina on 2020-05-21 at 10:23 Reason: Rewrite URL to remove tracking tokens, and avoid the URL tracker
2020-05-21, 12:44   #17
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

17·79 Posts

Quote:
 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".

 2020-05-21, 19:51 #18 dabler     "David Barina" Jul 2016 Brno 25 Posts Yes, the algorithm is efficient only for a specific class of numbers, as explained in the paper. The long multiplication is better on average.

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong Miscellaneous Math 5 2016-04-24 03:40 MattcAnderson Puzzles 8 2014-12-05 15:09 ewmayer Computer Science & Computational Number Theory 6 2014-05-14 21:03 __HRB__ Software 188 2010-08-09 11:13 dave_dm Math 2 2004-12-24 11:00

All times are UTC. The time now is 09:53.

Thu Jun 4 09:53:43 UTC 2020 up 71 days, 7:26, 0 users, load averages: 1.42, 1.38, 1.30

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.