mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2019-04-18, 22:38   #12
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

3·1,279 Posts
Default

Quote:
Originally Posted by Mysticial View Post
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.
kriesel is offline   Reply With Quote
Old 2019-04-18, 23:06   #13
Mysticial
 
Mysticial's Avatar
 
Sep 2016

5118 Posts
Default

Quote:
Originally Posted by kriesel View Post
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.
Mysticial is offline   Reply With Quote
Old 2019-11-19, 02:52   #14
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1100100011112 Posts
Default 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
paulunderwood is online now   Reply With Quote
Old 2019-11-20, 14:01   #15
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

2·3,709 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2020-05-21, 09:26   #16
dabler
 
dabler's Avatar
 
"David Barina"
Jul 2016
Brno

2016 Posts
Default

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
dabler is offline   Reply With Quote
Old 2020-05-21, 12:44   #17
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

53F16 Posts
Default

Quote:
Originally Posted by dabler View Post
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".
R. Gerbicz is offline   Reply With Quote
Old 2020-05-21, 19:51   #18
dabler
 
dabler's Avatar
 
"David Barina"
Jul 2016
Brno

3210 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
k*b^n+/-c where b is an integer greater than 2 and c is an integer from 1 to b-1 jasong Miscellaneous Math 5 2016-04-24 03:40
5 digit multiplication MattcAnderson Puzzles 8 2014-12-05 15:09
Mixed floating/integer transform for faster LL testing ewmayer Computer Science & Computational Number Theory 6 2014-05-14 21:03
Faster Lucas-Lehmer test using integer arithmetic? __HRB__ Software 188 2010-08-09 11:13
Montgomery Multiplication dave_dm Math 2 2004-12-24 11:00

All times are UTC. The time now is 11:39.

Thu Jun 4 11:39:29 UTC 2020 up 71 days, 9:12, 0 users, load averages: 1.23, 1.24, 1.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

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.