mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Twin Prime Search

Reply
 
Thread Tools
Old 2006-12-02, 14:58   #45
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

Quote:
Originally Posted by gribozavr View Post
Looking at http://primes.utm.edu/primes/lists/all.txt I see that 17 primes have already been reported for n=333333.
Looks like Biwema already started searching for primes in that range, and that Daniel Heuer missed one

If you need help, I do have a pc available that can do some sieving.

Last fiddled with by smh on 2006-12-02 at 15:03
smh is offline   Reply With Quote
Old 2006-12-03, 17:23   #46
biwema
 
biwema's Avatar
 
Mar 2004

3×127 Posts
Default

Well observed.

I already performed some tests on that Range.

I assume that Daniel Heuer did not miss any Prime. He was earching for -1 Riesel Primes and did not sieving for twins.

I did Sieving for twins and then testing +1 first (I still like the fermat factor idea).
That's why I have fewer primes per Range even I have to confess that I was very lucky (5 primes in K = 2 - 7M); At the moment I expect 1 prime per 10M.
I searched the Range up to k=20M.

I agree that it is a good Idea to distribute sieving, if the twinprimesearch community agrees on this exponent. At the moment I am removing around 80 candidates per minute (even if my P4 3.4 GHz is not optimal for sieving) at 160T. One Primalty test takes 267 Seconds on the same machine.
We can expect a sieving depth of 55-60P (60 Million G) - maybe even more, depending on how much faster amd is. (On my P4 that depth needs 24 cpu years of sieving)

Last fiddled with by biwema on 2006-12-03 at 17:30 Reason: typos
biwema is offline   Reply With Quote
Old 2006-12-03, 17:38   #47
gribozavr
 
gribozavr's Avatar
 
Mar 2005
Internet; Ukraine, Kiev

11·37 Posts
Default

I have an athlon and a celeron doing sieving for k=195000. Will it slow down sieving if I merge both k?
gribozavr is offline   Reply With Quote
Old 2006-12-03, 18:12   #48
biwema
 
biwema's Avatar
 
Mar 2004

3·127 Posts
Default

If the program supports that I think it will not slow down. On the other hand, I don't know if the overall performance gets better.

The most important thing you may consider is the memory. My range is 4 times larger and NewPGen uses more than 300MBytes while running. Mybe there is a little slowdown because the 2 ranges (0-25G and 0-100G) are not matching.

Regarding the range of sieved p you can start at that point you arrived with N=195000, The the range between can be sieved by someone else at a leter time and merged after.
biwema is offline   Reply With Quote
Old 2006-12-15, 15:08   #49
gribozavr
 
gribozavr's Avatar
 
Mar 2005
Internet; Ukraine, Kiev

11·37 Posts
Default

Range [1700e6; 25e9] is at p=1033.9T, 8,171,379 k's left.
gribozavr is offline   Reply With Quote
Old 2006-12-27, 19:35   #50
biwema
 
biwema's Avatar
 
Mar 2004

3×127 Posts
Default

I normally use NewPGen for sieving. I don't know how much it is optimized to the new architectures. It is not maintained anymore since more than a year. If we compare the speed in vertical sieving to the tool used in sobsieve etc, we can assume that there is still some potential for improvement.
While implementing a tool that is specialised for horizontal sieving, specific optimizations are possible.

Siving constellations of more than one prime (twin, triplet, various chains...) has the problem that the initial range/number of candidates is very large and is dropping very quickly.
The first part is completed with an array, where the numbers are crossed out.
NewPGen uses a bitmap for sieving up to 1 billion. After that point, the number of candidates dropped so much that severly subranges can be grouped together.
The feature of reduced screen output below 1 G is a bit flawy with the opposite effect that every divisor below 1 G is printed. The extensive screen output is slowing down the whole process.

Optimizations below 1 G:
- Adapt the bitmap to the characteristic of the constellation: k must be divisible by 3 (that +/-1 can be prime), so it needs only to contain these candidates. Hence the same amount of memory can hold a 3 times larger range.
- Instead of splitting the range in pieces of (0..2G, 2..4G, 4..6G), one can split modulo groups. (1 mod 35, 2 mod 35, 3 mod 35, 4 mod 35, 6 mod 35, 8 mod 35 ...) that needs just 24 instead of 35 groups and the slow sieving 5 an 7 can be avoided.
- define the bitmap siza as product of small primes (11*13*17*19*23*29*31=955049953). These primes can be sieved out once. After that every time the presieved range can be copied and continued sieving 37. Maybe this step is not necessary, if the second point is implemented.
- While sieving small primes, it is not necessary to count the sieved candidates. Just delete the appropriate bit without checking if that candidate was alread sieved earlier. The number of candidates can be counted when they are saved.

When I sieved a 100G range of N=333333, i was quite lucky, that the merged file after 1G was less than 2GByte.

Optimizations beyond 1 G:
- Use a hash table (NewPGen does that already) It is faster than a list or tree.
- finding candidate divisors: they don't need to be prime. If they are composite they simply don't sieve out a candidate. So the candidate divisors can be sieved (some of the optimizations above can be applied here, too) up to maybe 1000 (the optimal threshold has to be found), then run a quick fermat test (or similar) on these number and trial divide the ramaining divisors. Test dividing some pseudoprimes is faster than prove the primalty of the candidates. (Prime95 uses that strategy already - here a fermat is too slow that this part is omitted)

Multithreading (architecture specific)
- Splitting up the divisor generator and siever into different threads (maybe also a thread each for -1 sieving and +1 sieving). To go further: Is one thread for 6n-1 divisors and one thread for 6n+1 divisors even faster or could it be that they drift off each other?

Any Ideas?
biwema is offline   Reply With Quote
Old 2006-12-27, 21:23   #51
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

11×127 Posts
Default

See, biwema:

By hashtable the sieve wouldn't be faster. In Newpgen everything is in the memory.

Newpgen is using Erathosthenes or Atkin's fast method to find all prime numbers in an interval, and this is much faster than checking if p is a divisor of some k*2^n+-1 or not, if n is large and in this project n is large. So Newpgen isn't sieving by composite numbers, as I know.

Sobsieve is using a complicated multiple k-sieve, twinsieve isn't a such problem.

The math of the twin prime sieving is very easy, I think this is the method:

By powmod determine A=((p+1)/2)^333333 mod p (here p is prime), it is require 18 modulare squarings and 7 multiplies by (p+1)/2 which is really fast, because that is only a bitshift or add+bitshift. If for A or (-A) mod p is in your range then you can cancel that k value, because k*2^333333+-1 will be divisible by p, and if p is small then by sieve you can cancel also k+p,k+2*p,k+3*p and so on. There is also another method: compute B=2^333333 mod p by the same powmod but then do A=modinv(B,p), I think this is faster, because it is require only about 13 modular square+4 bitshifts but also one modular inverse operation, which isn't so cheap, but the total cost will be less and I think Newpgen using this method.
Therefor your multithreading idea is wrong, newpgen has got almost the same speed for single k*2^n+1 sieve and for twins k*2^n+-1 sieve.

About memory: it is possible to write a sieve that is using say less than 1M of memory: store the remaining k numbers in a sievefile and do another say 210000 files: for example c_129589.txt will contain the k numbers where k*2^n+-1 has got a prime divisor, what sieve has found (here 129589*10^6<=k<129590*10^6). If you've done some work, say you've sieved from 1000G to 1001G then you can open the sievefiles and merge the k factors. After this delete all 210000 files and continue sieving. In theory it wouldn't be slow, it is very rare that you've to merge the lists.

Last fiddled with by R. Gerbicz on 2006-12-27 at 21:27 Reason: adding some notes
R. Gerbicz is offline   Reply With Quote
Old 2006-12-28, 01:34   #52
biwema
 
biwema's Avatar
 
Mar 2004

3·127 Posts
Default

I think there are a few misunderstandings...

Quote:
Originally Posted by R. Gerbicz View Post
By hashtable the sieve wouldn't be faster. In Newpgen everything is in the memory.
I am thinking about a hashtable in the memory that a p can be found in O(1). Assuming our list has millions of candidates (p) left. A sorted list or a tree is O(log n).
On the other hand: If we are sieving a 100G range at 1 P, only every 10000th p divides a k in [0..100G] that lookups are quite rare (a few 1000 per second).
Maybe the offline sieving could be an option when we are working on really large candidates (300000 k or 1 M digits).

Quote:
Newpgen is using Erathosthenes or Atkin's fast method to find all prime numbers in an interval, and this is much faster than checking if p is a divisor of some k*2^n+-1 or not, if n is large and in this project n is large. So Newpgen isn't sieving by composite numbers, as I know.
Yes, but I assume that they are not sieving up to Sqrt(p) because that is too slow. There are too few p removed after sieving beyond 100000, that it makes more sense to accept composite p. (Confusing, I know: There are two
cascaded sieves, The outer sieved just the sieve divisors of the inner sieve.)

Quote:
Sobsieve is using a complicated multiple k-sieve, twinsieve isn't a such problem.
I agree. Actually I wanted to say. If there are improvements in the vertical sieve (sobsieve), then there might be also some in the horizontal sieve. The algorithmns are different, of course.

Quote:
Therefor your multithreading idea is wrong, newpgen has got almost the same speed for single k*2^n+1 sieve and for twins k*2^n+-1 sieve.
Ok. You're right. So this part of multithreading makes no sense.

How about the other way? Which part of the twinsieving takes more time?
- The generation of p, which are used for sieving.
- Testing if a p divides a twin candidate.

If the first part takes much more time, generating more (but also composite) p in much less time could make sense.
Maybe setting the thershhold of the part 1 sieve

Quote:
About memory: it is possible to write a sieve that is using say less than 1M of memory: store the remaining k numbers in a sievefile and do another say 210000 files: for example c_129589.txt will contain the k numbers where k*2^n+-1 has got a prime divisor, what sieve has found (here 129589*10^6<=k<129590*10^6). If you've done some work, say you've sieved from 1000G to 1001G then you can open the sievefiles and merge the k factors. After this delete all 210000 files and continue sieving. In theory it wouldn't be slow, it is very rare that you've to merge the lists.
That could work, but depends on the speed of the disks.

New Idea (Adapted from R.Gerbicz approach):
Don't hold the list of still remaining twin candidates in the memory. Just sieve and keep all removed p in the sieve range (here 0..100G) in the memory. They appear randomly in the range. Therefore build up a tree, where you can read all p in a sorted way.
After the memory, that is reserved for the sieving application is used up, merge the p with the twincandidate file on the disk (That process replaces the intermediate save).
The whole thing is only effecient after reaching an adequate level of sieving (some T).

Last fiddled with by biwema on 2006-12-28 at 01:35 Reason: a 'quote' tag was not correct
biwema is offline   Reply With Quote
Old 2006-12-28, 22:09   #53
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default

I run newpgen on Linux and I have a question.

While I'm always well informed by the program what the the sieving value is at, I only seem to see updates of how many k are left, or the rate, when a k is removed. This could be a problem if a siever wants to sieve until the rate is more than about 2 minutes, but wants to stop the sieve manually.

Am I just not patient enough, or is this a problem that hasn't been considered?
jasong is offline   Reply With Quote
Old 2006-12-29, 10:49   #54
thommy
 
thommy's Avatar
 
Dec 2006

3×11 Posts
Default

Where is the problem? just wait 2 minutes. you are not watching the programm 24/4, are you? So it's no big deal, even if one sieves a day longer.
thommy is offline   Reply With Quote
Old 2006-12-30, 23:20   #55
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default

Question: If you set it to log factors, will it log factors as soon as it gets them, or go by the update interval? The reason I ask is that I set the update interval to 10,000 minutes, thinking that only applied to the main file. I'm hoping the factors will update more frequently, and if there's a power outage I can simply update the starting point with vi.

Is this the correct way to do things?
jasong is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
S9 and general sieving discussion Lennart Conjectures 'R Us 31 2014-09-14 15:14
Sieving discussion thread philmoore Five or Bust - The Dual Sierpinski Problem 66 2010-02-10 14:34
Combined sieving discussion ltd Prime Sierpinski Project 76 2008-07-25 11:44
Sieving Discussion ltd Prime Sierpinski Project 26 2005-11-01 07:45
Sieving Discussion R.D. Silverman Factoring 7 2005-09-30 12:57

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

Sat Sep 26 08:38:01 UTC 2020 up 16 days, 5:48, 0 users, load averages: 1.21, 1.26, 1.29

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