20181227, 07:47  #1 
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 20181227 at 08:23 
20181227, 10:43  #2 
Romulan Interpreter
Jun 2011
Thailand
13×23×31 Posts 
It seems to be just trial division/SoE.

20181227, 12:36  #3 
Sep 2002
Database er0rr
2×5×359 Posts 

20181230, 04:03  #4 
Dec 2018
2·3 Posts 
It seems to "just" be trial division? Okay. I guess that means its crap.
Last fiddled with by Zach010 on 20181230 at 04:03 
20181230, 05:12  #5 
Sep 2002
Database er0rr
2·5·359 Posts 

20181230, 05:50  #6 
Aug 2006
2^{2}·1,493 Posts 
Trial division is a slow generalpurpose algorithm, while LucasLehmer is a fast specialpurpose algorithm. Your program took 70.2 seconds to verify the primality of 2^611, 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 simpleminded script.
Code:
LL(p)= { my(m=Mod(4,2^p1)); for(i=3,p, m=m^22); m==0; } 
20181230, 05:54  #7 
Aug 2006
2^{2}·1,493 Posts 
Of course for nonMersenne 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 nearcertainty, like 99.999999%).

20181230, 06:05  #8 
Dec 2018
6_{8} Posts 
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 primeness especially if you have a system with a high corecount 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^611 as 2**611 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 20181230 at 06:31 
20181230, 06:19  #9 
Aug 2006
2^{2}×1,493 Posts 
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? 
20181230, 06:32  #10  
Sep 2002
Database er0rr
2×5×359 Posts 
Quote:
Last fiddled with by paulunderwood on 20181230 at 06:33 

20181230, 06:38  #11  
Dec 2018
110_{2} Posts 
Quote:
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 addon 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 (P1) Ellipticcurve factorization method (ECM) Last fiddled with by Zach010 on 20181230 at 07:37 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
software advise? big number with GUI  skan  Programming  14  20130324 00:32 
Prime testing software suggestions please.  ishkibibble  Conjectures 'R Us  15  20130314 08:41 
[SunOS 5.10] Software for prime search  pacionet  Programming  3  20080212 12:36 
Prime 95 and Software OC'ing  Matt_G  Hardware  13  20040201 04:16 
Network Administration software for Prime ?  fuzzfuzz  Software  6  20020910 08:46 