mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > jzakiya

Closed Thread
 
Thread Tools
Old 2014-07-22, 19:00   #1
jzakiya
 
Jul 2014

1110002 Posts
Default 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
jzakiya is offline  
Old 2014-07-24, 16:15   #2
jzakiya
 
Jul 2014

23·7 Posts
Default

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 |
--------------------------------------------------------
jzakiya is offline  
Old 2014-07-24, 18:09   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

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).
CRGreathouse is offline  
Old 2014-07-25, 06:04   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

3×5×683 Posts
Default

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.
LaurV is offline  
Old 2014-07-25, 14:41   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

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!
CRGreathouse is offline  
Old 2014-07-25, 17:11   #6
jzakiya
 
Jul 2014

5610 Posts
Default

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?
jzakiya is offline  
Old 2014-07-25, 17:18   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

598710 Posts
Default

Quote:
Originally Posted by jzakiya View Post
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.
CRGreathouse is offline  
Old 2014-07-25, 19:01   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5·1,997 Posts
Default

Quote:
Originally Posted by jzakiya View Post
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?
Batalov is offline  
Old 2014-07-25, 19:21   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

176316 Posts
Default

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.
CRGreathouse is offline  
Old 2014-07-25, 21:20   #10
jzakiya
 
Jul 2014

708 Posts
Default

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.
jzakiya is offline  
Old 2014-07-26, 01:39   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

234018 Posts
Default

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.
Batalov is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Highest Prime is also a twin prime... NOT hydeer Lone Mersenne Hunters 9 2018-04-03 22:54
Twin Prime Days, Prime Day Clusters cuBerBruce Puzzles 3 2014-12-01 18:15
Twin prime search? MooooMoo Twin Prime Search 115 2010-08-29 17:38
twin prime, but sieving n instead of k. Possible? jasong Software 20 2007-11-28 03:48
Questions about twin prime search jasong Twin Prime Search 14 2006-12-14 23:16

All times are UTC. The time now is 09:08.


Sun Nov 27 09:08:27 UTC 2022 up 101 days, 6:37, 0 users, load averages: 0.97, 0.91, 0.90

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔