mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2018-12-27, 07:47   #1
Zach010
 
Zach010's Avatar
 
Dec 2018

2×3 Posts
Lightbulb Prime number software.

I don't really know how good this program is. I wrote it over the past few months and was wondering if anyone wanted to try it and let me know. I posted it on Git hub for anyone to see. It is written in Python and requires the scientific mpmath module to run. It uses the multiprocessing module and does calculations in parallel. Here is the link: Github Tell me what you think. I can turn this code into a network cluster with multiprocessing server managers pretty easily. Also, what language is Prime95 written in? Tell me how I can help.

Last fiddled with by Zach010 on 2018-12-27 at 08:23
Zach010 is offline   Reply With Quote
Old 2018-12-27, 10:43   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

230608 Posts
Default

It seems to be just trial division/SoE.
LaurV is offline   Reply With Quote
Old 2018-12-27, 12:36   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

385310 Posts
Default

Quote:
Originally Posted by Zach010 View Post
Also, what language is Prime95 written in? Tell me how I can help.
Prime95 is written in C and assembly, and I guess some C++ for the GUI.
paulunderwood is offline   Reply With Quote
Old 2018-12-30, 04:03   #4
Zach010
 
Zach010's Avatar
 
Dec 2018

1102 Posts
Default

Quote:
Originally Posted by LaurV View Post
It seems to be just trial division/SoE.
It seems to "just" be trial division? Okay. I guess that means its crap.

Last fiddled with by Zach010 on 2018-12-30 at 04:03
Zach010 is offline   Reply With Quote
Old 2018-12-30, 05:12   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,853 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Prime95 is written in C and assembly, and I guess some C++ for the GUI.
A better guess for the GUI is Visual Basic.
paulunderwood is offline   Reply With Quote
Old 2018-12-30, 05:50   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Trial division is a slow general-purpose algorithm, while Lucas-Lehmer is a fast special-purpose algorithm. Your program took 70.2 seconds to verify the primality of 2^61-1, while my GP script (essentially the same as the one I uploaded to Rosetta Code) takes 36 microseconds to do the same. Prime95 uses a lot of specialized techniques and tricks that make it substantially faster than my simple-minded script.

Code:
LL(p)=
{
  my(m=Mod(4,2^p-1));
  for(i=3,p, m=m^2-2);
  m==0;
}
CRGreathouse is offline   Reply With Quote
Old 2018-12-30, 05:54   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Of course for non-Mersenne numbers there still algorithms much faster than trial division. Below 2^64 BPSW works, above that a prp test and ECPP is good (and you can do less if you only need near-certainty, like 99.999999%).
CRGreathouse is offline   Reply With Quote
Old 2018-12-30, 06:05   #8
Zach010
 
Zach010's Avatar
 
Dec 2018

1102 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Of course for non-Mersenne numbers there still algorithms much faster than trial division. Below 2^64 BPSW works, above that a prp test and ECPP is good (and you can do less if you only need near-certainty, like 99.999999%).
Yes, I was about to say that. My script is for any prime. An algorithm that works 100.0% of the time and is fast? I have done many trials and tests with different methods and this modular trial division is the only method that always returns 100% correct. Sieves such as the Sieve of Eratosthenes are fast, but can take a while to initialize sieve data into memory. Sieves can also be ram expensive and only work up to a certain number before you reach your memory limit. Read the description of my code. If the program is taking too long, then terminate the process. If you enter a huge number that is 300 thousand digits long, if it is not prime, the program will be able to realize it in under a few seconds 99% of the time. If it runs....and keeps running, it has a much higher chance of prime-ness especially if you have a system with a high core-count because it takes evenly spaced samples of the whole number at once. This gives it a higher chance to find an odd divisor by sampling calculations of the number from multiple vantage points simultaneously. The script also accepts pythonic syntax such as 2^61-1 as 2**61-1 for a Mersenne Prime around 2.3 quintillion. On my 8 core 16 thread i9 it does this in around 20 seconds at 4.7 ghz.

Last fiddled with by Zach010 on 2018-12-30 at 06:31
Zach010 is offline   Reply With Quote
Old 2018-12-30, 06:19   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by Zach010 View Post
An algorithm that works 100.0% of the time and is fast?
Yes. For example, the next prime after the Mersenne prime tested above is 2^61 + 15. PARI/GP proves its primality in 500 nanoseconds.

Moving to somewhat larger numbers, PARI/GP takes 150 ms to prove that 10^100 + 267 is prime. How long do you project that would take your program, assuming you networked all the computers in the world for the task?
CRGreathouse is offline   Reply With Quote
Old 2018-12-30, 06:32   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,853 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Yes. For example, the next prime after the Mersenne prime tested above is 2^61 + 15. PARI/GP proves its primality in 500 nanoseconds.

Moving to somewhat larger numbers, PARI/GP takes 150 ms to prove that 10^100 + 267 is prime. How long do you project that would take your program, assuming you networked all the computers in the world for the task?
Or the 2-year 16-core proof of 2^116224-15905? Note the 1 core test Fermat+Lucas test that took 37.00 seconds.

Last fiddled with by paulunderwood on 2018-12-30 at 06:33
paulunderwood is offline   Reply With Quote
Old 2018-12-30, 06:38   #11
Zach010
 
Zach010's Avatar
 
Dec 2018

68 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Yes. For example, the next prime after the Mersenne prime tested above is 2^61 + 15. PARI/GP proves its primality in 500 nanoseconds.

Moving to somewhat larger numbers, PARI/GP takes 150 ms to prove that 10^100 + 267 is prime. How long do you project that would take your program, assuming you networked all the computers in the world for the task?
Good question. Assuming I could get a core count, it would obviously be a linear increase in speed per 'x' number of cores and would have noticeable speed limits. I really wanted to try to code a cuda version with the same idea. I don't know much about PARI/GP. I did a search and found that its a "computer algebra system". Have to learn more.

Let me be clear. This script is not meant for calculations of huge numbers without a comparable system to handle the time. It is really meant for "fishing" for probable primes and it works well. On a quad core processor if one enters 10**100 - 266, it returns false immediately or 10**100 - 268 it returns false immediately. But 10**100 - 267 will continue because its prime and won't find a divisor to terminate the program. So it will continue to calculate to the end unless you terminate it. I could easily implement an add-on to the code where it has a time limit of a 1 minute calculation per number where it will store the probable prime in a list if it doesn't return true or false and map them to known primes to see how probable the probability is.

Prime95 is not 100% accurate:

To perform the Mersenne prime search, the program implements two algorithms:

Lucas–Lehmer (LL) test – proves any specific number is either a Mersenne prime, or a composite (in practice it has reliability of about 96%)
Probable prime (PRP) test – proves a number to be composite (but in practice has very low chance of reporting a false positive); this method is preferred for large numbers because of better error correction

It also implements a few algorithms which try to factor the numbers:

Trial factoring – this method is primarily used before applying the aforementioned algorithms
Pollard's factorization algorithm (P-1)
Elliptic-curve factorization method (ECM)

Last fiddled with by Zach010 on 2018-12-30 at 07:37
Zach010 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
software advise? big number with GUI skan Programming 14 2013-03-24 00:32
Prime testing software suggestions please. ishkibibble Conjectures 'R Us 15 2013-03-14 08:41
[SunOS 5.10] Software for prime search pacionet Programming 3 2008-02-12 12:36
Prime 95 and Software OC'ing Matt_G Hardware 13 2004-02-01 04:16
Network Administration software for Prime ? fuzzfuzz Software 6 2002-09-10 08:46

All times are UTC. The time now is 07:36.


Mon Oct 18 07:36:04 UTC 2021 up 87 days, 2:05, 0 users, load averages: 0.80, 0.96, 1.06

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.