mersenneforum.org A Twin Prime Search Method
 Register FAQ Search Today's Posts Mark Forums Read

 2014-07-22, 19:00 #1 jzakiya   Jul 2014 22×3×5 Posts A Twin Prime Search Method I have developed a fast and efficient method to find primes. In June 2014 I released my paper on a segmented version for the algorithm. http://www.scribd.com/doc/228155369/...of-Zakiya-SSoZ In the paper I describe how to modify the method to just find Twin Primes. I believe this is the fastest and most efficient method to do this. By "efficient" I mean you can limit the percentage of number space to consider by choosing the appropriate "prime generator (pg)" expression. For example, a pg of form 1) Pn = 30*k + {1,7,11,13,17,19,23,29] can be modified to have the form 2) Pn = 30*k + {11,13,17,19,29,31} to just find Twin Primes. For case 1) we can find all primes up to some N by only needing to consider 8/30 = 4/15 = 26.67% of the number space up to N. For case 2) we can find all the twin primes up to some N by only considering 6/30 = 1/5 = 20% of the number space up to N. In each case the results are completely deterministic. The number space can be reduced more by picking a more "efficient" pg. I haven't currently written the version to just find twin primes, because at the time I released my paper that wasn't my specific focus (I will now to create a reference version). I present this because I am interested in: 1) People being aware of this method. 2) Seeing other people's implementations. 3) Seeing better parallel implementations. 4) Learning what current methods are used to find twin primes. 5) Receiving feedback on empirical comparisons of code and benchmarks. Please feel free to contact me offline at the email in the paper if you want. :D
 2014-07-24, 16:15 #2 jzakiya   Jul 2014 22×3×5 Posts Here is a reference Twin Prime Generator using a modified Segmented Sieve of Zakiya (SSoZ) for P5 SP generator. This is a single threaded implementation. A true parallel implementation would be significantly faster. twinprimesssozp5cpp.cpp https://gist.github.com/jzakiya/ea78e9c9a38ca0c46c5c It's actually waaaaay faster than the ssozp5 generator to find all primes because it only need to consider 20% of the number space, instead of 26.67% for the full ssozp5 algorithm. Below are some times it produces on my system. Lenovo latptop, I5-2410M, 2.3 GHz, 256MB L2 cache g++ 4.7.2 compiled as: > g++ -O xxx.cpp -o xxx All times in seconds. For N = 10^6 and 10^7 times were below timer resolution. N | Time | # Twin Primes | Last Twin Prime | -------------------------------------------------------- 10^6 | NA | 8,169 | 999,960+/-1 | -------------------------------------------------------- 10^7 | NA | 58,980 | 9,999,972+/-1 | -------------------------------------------------------- 10^8 | 0.09 | 440,312 | 99,999,588+/-1 | -------------------------------------------------------- 10^9 | 0.92 | 3,424,506 | 999,999,192+/-1 | -------------------------------------------------------- 10^10 | 9.96 | 27,412,679 | 9,999.999.702+/-1 | -------------------------------------------------------- 10^11 | 110.85 | 224,376,048 | 99,999,999,762+/-1 | -------------------------------------------------------- 10^12 | 1376.35 | 1,870,585,220 | 999,999,999,960+/-1 | --------------------------------------------------------
 2014-07-24, 18:09 #3 CRGreathouse     Aug 2006 176316 Posts Interesting. I wonder how this compares to the methods of Tomás Oliveira e Silva (who I believe is the current record-holder at 10^18 as of 2008).
 2014-07-25, 06:04 #4 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 10,273 Posts Which method? This guy just discovered wheel sieves... It is just a wheel sieve with increased primorial, I assume the guys who really searched for twin primes (Silva, etc) would have a much better/faster method, like using a larger wheel (11#, or 13# with 30030 clases?) and... sieving? I mean normal sieving... To go to 10^18 with the method shown here, one would need... let's see... increasing the power of 10 with 1 slows the time with a factor of 12, that is because you have 10 times more numbers to test, and they are bigger (more operations to do), and this 12 is not constant, it will go higher for multiprecision numbers (below 10^18 there are still 64 bits, so single-precision on a 64 bit CPU), but assume it will stay at 12. We need to add 6 zeroes to that table, so 1376*12^6 seconds, which is 1.14 million hours, or 130 years, using the same resources as the OP did.
 2014-07-25, 14:41 #5 CRGreathouse     Aug 2006 5,987 Posts I guess that goes to show how low the current state of the art is, since I'm sure Oliveira e Silva spent over a year on it. That's just two orders of magnitude off!
 2014-07-25, 17:11 #6 jzakiya   Jul 2014 22×3×5 Posts Hi LauRv, Did you read my paper? http://www.scribd.com/doc/228155369/...of-Zakiya-SSoZ Do you understand all the work presented in the paper? Did you see the references in the paper? Did you obtain the source code to my programs? http://www.4shared.com/folder/TcMrUvTB/_online.html Did you run and benchmark them on your system? If so, can you give your system's specs and results? Have you done anything to test and compare what I have presented to other available programs doing the same things? It would aide you to understand the totality of the math, algorithms, and implementations benefits my approaches provide, especially for producing actual software (and hardware) systems. Here just a few benefits of my work: 1) Simplicity of math and algorithms The math involved is extremely simply, using mostly just arithmetic. This also allows for very simple software (hardware) implementations. Compare my software implementations to others, such as TOS's SSoE (Segmented Sieve of Eratothenes) you can see here: http://sweet.ua.pt/tos/software/prime_sieve.tgz Which is shorter, simpler, and more comprehensible (mine is commented)? Look at his implementation, compile and run it, alongside mine, and then tell me which one you think is "better" (real times would be nice). 2) Flexibility As I've shown, the basic approach I've presented is easily adaptable to find primes of different forms and for different purposes. For example: find primes <= N find twin primes <= N in both cases, can find primes within specified ranges nthprime finder, to find the nth prime primality tester, determine if an N is prime 3) Simplicity and Conciseness of code Less than 250 loc (lines of code) of actual C++ code statements. 4) Simple and very efficient memory model The segmented sieve works on just bytes of data. It can thus run without architectural limitations on any byte addressable cpu. Optimized to fit into a cpus L1|L2|L3 cache (which ever gives fastest results). No need to do explicit memory management with malloc, et al, instructions. 5) Inherently parallelizable The various (simple) components can be micro-parallelized, and the whole algorithm can be done in a parallel distributed network (like GIMPS) to take advantage of using larger Prime Generators (like P7, P11, P13, etc). Can (has) easily been (partially) parallelized using OpenMP. 6) Speed No one has presented any data to show another method, run on their system with mine, compiled in the same manner (optimization, etc, flags), that is faster. A real apples-to-apples comparison. Finally, please note the times I presented were produced on a laptop using a 2.3Ghz I5-2410M cpu using its 256KB L2 cache. I got this laptop in 2011. Currently there are at least 2 generations better Intel chipsets, operating natively at > 3Ghz, with 500KB L2 caches, with more cores, and other faster platforms too, XEON, AMD, ARM, PowerPC, etc. It should be obvious, if my pedestrian system achieves these single threaded results a newer system will achieve even faster results, and a parallel or distributed system would even be X times faster. I would appreciate people actually running the code on their systems and providing their results. I thought people here were programmers?
2014-07-25, 17:18   #7
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by jzakiya No one has presented any data to show another method, run on their system with mine, compiled in the same manner (optimization, etc, flags), that is faster. A real apples-to-apples comparison.
Traditionally that would be your job, as the one presenting a new algorithm.

2014-07-25, 19:01   #8
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100111010000112 Posts

Quote:
 Originally Posted by jzakiya Did you read my paper? Do you understand all the work presented in the paper? Did you see the references in the paper? Did you obtain the source code to my programs?
Yes, and we want two hours of our life back.

You described an ordinary segmented sieve and attached your last name to every time you mention it. Normally, people stop reading at this point.

Here is a reference for you:
http://primes.utm.edu/notes/crackpot.html
Can you calculate your paper's score?

Pay close attention to items (and these are just the first that jump out):
Quote:
 4. 10 points for not knowing (or not using) standard mathematical notation. ... 16. 20 points for naming something after yourself. 17. 10 points for expecting others to disprove your result(s) rather than providing the proof yourself.
Be careful not to get extra points for the last section (#23-28); you already started down that road by lashing out on one person. Now all you need is to blame the conspiracy of moderators. Well?

 2014-07-25, 19:21 #9 CRGreathouse     Aug 2006 5,987 Posts Look, I'm perfectly happy to consider jzakiya's work seriously. I think it's relatively well-known here that some of the more complicated sieves (Atkin-Bernstein, I'm looking at you) are outperformed by simple Eratosthenes variants. "Real-world" factors like cache performance are a big deal, even if they don't fit into the Big-O world very well. But I need more than bluster. I've read through Tomas' code and it's a masterpiece -- really squeezing out performance by taking all these real-world factors into consideration and using subtle tricks to get high performance. It's fine to claim that your code is better but I'd like to see some numbers or at least some particular aspect that your code considers that other code omits. Of course this is just one piece of code, you don't have to use it as your benchmark -- many of us here know (or have written our own) code to do prime sieving efficiently.
 2014-07-25, 21:20 #10 jzakiya   Jul 2014 6010 Posts I would actually be happy to have people make constructive critiques on my methods or code, if they were objective, and if they showed "better" methods or techniques. Unfortunately, I have yet to see any such response. Again, I ask people to: 1) please read my paper and actually try to understand what I am doing, 2) read my source code, 3) compile and run my code, and 4) present their results obtained on their systems. When I say my code is "simpler" more "adaptable" and "faster" these are objective statements based on my research and analysis of the methods and code I have been able to identify, read and evaluate, and run and/or assess performance of. I would learn more by people posting links to better code/methods, or faster implementations, than to hear ad hominen statements from people who don't seem to understand my work and/or never run my code.

 Similar Threads Thread Thread Starter Forum Replies Last Post hydeer Lone Mersenne Hunters 9 2018-04-03 22:54 cuBerBruce Puzzles 3 2014-12-01 18:15 MooooMoo Twin Prime Search 115 2010-08-29 17:38 jasong Software 20 2007-11-28 03:48 jasong Twin Prime Search 14 2006-12-14 23:16

All times are UTC. The time now is 02:52.

Sun Jan 29 02:52:19 UTC 2023 up 164 days, 20 mins, 0 users, load averages: 1.11, 1.04, 1.07