20140722, 19:00  #1 
Jul 2014
111000_{2} 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/...ofZakiyaSSoZ 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 
20140724, 16:15  #2 
Jul 2014
2^{3}·7 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, I52410M, 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   
20140724, 18:09  #3 
Aug 2006
5,987 Posts 
Interesting. I wonder how this compares to the methods of Tomás Oliveira e Silva (who I believe is the current recordholder at 10^18 as of 2008).

20140725, 06:04  #4 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3×5×683 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 singleprecision 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. 
20140725, 14:41  #5 
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!

20140725, 17:11  #6 
Jul 2014
56_{10} Posts 
Hi LauRv,
Did you read my paper? http://www.scribd.com/doc/228155369/...ofZakiyaSSoZ 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 L1L2L3 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 microparallelized, 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 applestoapples comparison. Finally, please note the times I presented were produced on a laptop using a 2.3Ghz I52410M 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? 
20140725, 17:18  #7 
Aug 2006
5987_{10} Posts 
Traditionally that would be your job, as the one presenting a new algorithm.

20140725, 19:01  #8  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
5·1,997 Posts 
Quote:
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:


20140725, 19:21  #9 
Aug 2006
1763_{16} Posts 
Look, I'm perfectly happy to consider jzakiya's work seriously. I think it's relatively wellknown here that some of the more complicated sieves (AtkinBernstein, I'm looking at you) are outperformed by simple Eratosthenes variants. "Realworld" factors like cache performance are a big deal, even if they don't fit into the BigO 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 realworld 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. 
20140725, 21:20  #10 
Jul 2014
70_{8} 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. 
20140726, 01:39  #11 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
23401_{8} Posts 
Apparently you don't know what ad hominem is, because it was your work that was discussed  and none of your personal characteristics.
A short search of internet shows that you already dragged your drivel over a dozen forums (and even wikipedia) and your threads were invariably closed. Let's not break with this tradition and close this thread before it gets ugly. Contrary to your wishful "I would learn more by people posting links to better code/methods", you appear to haven't learned anything over the last six years. Other than hopping from one forum to another in search of attention. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Highest Prime is also a twin prime... NOT  hydeer  Lone Mersenne Hunters  9  20180403 22:54 
Twin Prime Days, Prime Day Clusters  cuBerBruce  Puzzles  3  20141201 18:15 
Twin prime search?  MooooMoo  Twin Prime Search  115  20100829 17:38 
twin prime, but sieving n instead of k. Possible?  jasong  Software  20  20071128 03:48 
Questions about twin prime search  jasong  Twin Prime Search  14  20061214 23:16 