mersenneforum.org Prime number software.
 Register FAQ Search Today's Posts Mark Forums Read

 2018-12-27, 07:47 #1 Zach010     Dec 2018 2×3 Posts 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
 2018-12-27, 10:43 #2 LaurV Romulan Interpreter     Jun 2011 Thailand 230608 Posts It seems to be just trial division/SoE.
2018-12-27, 12:36   #3
paulunderwood

Sep 2002
Database er0rr

385310 Posts

Quote:
 Originally Posted by Zach010 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.

2018-12-30, 04:03   #4
Zach010

Dec 2018

1102 Posts

Quote:
 Originally Posted by LaurV 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

2018-12-30, 05:12   #5
paulunderwood

Sep 2002
Database er0rr

3,853 Posts

Quote:
 Originally Posted by paulunderwood Prime95 is written in C and assembly, and I guess some C++ for the GUI.
A better guess for the GUI is Visual Basic.

 2018-12-30, 05:50 #6 CRGreathouse     Aug 2006 3·1,993 Posts 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; }
 2018-12-30, 05:54 #7 CRGreathouse     Aug 2006 3·1,993 Posts 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%).
2018-12-30, 06:05   #8
Zach010

Dec 2018

1102 Posts

Quote:
 Originally Posted by CRGreathouse 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

2018-12-30, 06:19   #9
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by Zach010 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?

2018-12-30, 06:32   #10
paulunderwood

Sep 2002
Database er0rr

3,853 Posts

Quote:
 Originally Posted by CRGreathouse 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

2018-12-30, 06:38   #11
Zach010

Dec 2018

68 Posts

Quote:
 Originally Posted by CRGreathouse 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

 Similar Threads Thread Thread Starter Forum Replies Last Post skan Programming 14 2013-03-24 00:32 ishkibibble Conjectures 'R Us 15 2013-03-14 08:41 pacionet Programming 3 2008-02-12 12:36 Matt_G Hardware 13 2004-02-01 04:16 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