mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2012-04-27, 18:33   #67
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22×132 Posts
Default

Quote:
Originally Posted by biwema View Post
Im am sorry that i did not yet answer about my calculations. I just was busy. I try to do my best and give a detailed answer this weekend.
I simply calculate d^k where d=number of decimal digits and k=length of tuple. I miss your numbers by a factor of ~4-5. Do you aim for a certain probability of the range containing a tuple, say 90%?
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-27, 20:01   #68
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·3·7·137 Posts
Default

Quote:
Originally Posted by Puzzle-Peter View Post
This is very interesting.

If I understood Robert correctly, you need a very large search range for bound_small_primes=19 to be efficient.

I'm really curious what sieve_len will do to performance and memory usage.
sieve_len made very little difference to timings. Doubling it slowed it down a small amount and halfing is didn't make a noticable difference. Memory wise it should hardly make a diffference. 8192*8 is only 64k which is the size of the L1 cache of a lot of AMD cpus. Intel cpus have 32k cache so decreasing to 4096 should have more of an effect speed wise. The real memory hog in this program is when you use a lot of primes. Sieving upto 10M only uses 30MB each core.

I changed hash_bits to 20 which took me down to 20 minutes per 100T. I am now doing 4 lots of 5P overnight. This will take me upto 22P. 730P is the estimate.
henryzz is offline   Reply With Quote
Old 2012-04-28, 05:49   #69
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

67610 Posts
Default

20 minutes per 100T? Now that's what I call impressive! Using NewPGen we would be talking about weeks...

Last fiddled with by Puzzle-Peter on 2012-04-28 at 05:50
Puzzle-Peter is offline   Reply With Quote
Old 2012-04-30, 12:21   #70
biwema
 
biwema's Avatar
 
Mar 2004

17D16 Posts
Default

Quote:
Originally Posted by Puzzle-Peter View Post
EDIT: By the way, how do you calculate your "Range per one tuple" figures? I get much higher numbers when I try to estimate the k range needed per tuple.
I am sorry that I did not answer that question for such a long time.
Yesterday I took time to do that, but lost everything after I accidently hit the ‘page back’ key. Trying again…

After sieving to deep limits, the primes in a tuple are independent. It is possible to multiply the probabilities of being prime.

Example: henrzz, 6 Tuple with 1000 Bits (I don’t know the exact number) and 40 bit Mantissa. Sieving to 27 bit (131M);
Probability of a prime is [Bits Sieving depth] / ([Size of Candidate]/2).
Probability (prime): 27 / 520 = 1 in 19.25 or 5.2%.
Twin: 1 in 371
3-Tuple: 1 in 7143
4-Tuple: 1 in 137580
5-Tuple: 1 in 2.65 Million
6-Tuple: 1 in 51 Million
According to the Number of candidates in the sieved array it is possible to extrapolate the array, which is needed.
Of course it is just a probability: After searching that range the probability of success is 1-1/e. (If the range is twice as big, the probability is 1-1/e².

When sieving to low limits, the candidates are not independent:
Having a NewPGen array of k*2^x for 6 Tuple, k odd. One out of 105 candidates is remaining after sieving 3, 5 and 7. Optimized sieves use an array which just use these numbers.
When sieving p for N-Tuple, (p-N)/p candidates are remaining.
6-tuple: sieving 11, 13, 17, 19, 23 removes
5/11 * 7*13 * 11/17 * 13/19 * 17/23 = 8% remaining.
After sieving up to 1023 less than 0.1% of the candidates are remaining. (<0.025% for 7-tuple; sieving to 1048000 : 6-tuple 0.0014%, 7-tuple: 0.000175%)
The reducing number of candidates makes it difficult to keep the sieve efficient.

Up to 4-Tuple, proth (k*2^n) numbers are more efficient than primordial (k*p#).
6 – 10(?) tuple, primorial numbers are faster.
About 5-tuple it depends on the tools used, which is faster.
15+ tuple need completely different algorithms.
biwema is offline   Reply With Quote
Old 2012-04-30, 20:01   #71
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×3×7×137 Posts
Default

I am not sure your formulas are right. I got 1/23 per candidate instead of 1/25 from your formula for the numbers I am testing currently. The odds of a number of the form k*b^n+c being prime(c small) is 1 in (n*ln(b)+ln(k))
The odds of a random candidate surviving sieving upto s is 1 in (1.781*ln(s)).
Thus the odds of each candidate surviving sieving is (1.781*ln(s))/(n*ln(b)+ln(k)).
1.781 is an approximation of exp(gamma) http://www.wolframalpha.com/input/?i...7s+constant%29

I have attached a spreadsheet including these formulas. It closely matches the results I have been getting so far in my search for 7-tuples.


I discovered just after sieving upto 46P that once k reaches a certain level pfgw is forced to resort to more general methods of fft which slows it down by a factor of 2.5. I need to sieve deeper in future.
Attached Files
File Type: zip odds of prime3.zip (10.0 KB, 76 views)

Last fiddled with by henryzz on 2012-04-30 at 20:12 Reason: explanation of 1.781
henryzz is offline   Reply With Quote
Old 2012-04-30, 20:50   #72
biwema
 
biwema's Avatar
 
Mar 2004

3×127 Posts
Default

Our Approaches are just different. I did not use a constant, because i just use the quotient between lieve Limit and candidate. So even the base of the log has no influence anymore.

I see one main difference:
I use P(prime) = log(Sievedepth)/(log(Candidate)/2)
You use P(prime) = log(Sievedepth)/log(Candidate)

I am careful with low sieving levels because tuplets are not independant. After sieving to some limit, I think my approximation are more or less accurate.

About the probabilities of 6 and 7 Tuple: Here we should maybe take care about rounding errors: 1-(1-3*10^-10))^150000000
Here there are just a few significant digits raised to a huge power.

Could you tell me some information about your search?
How do you count 150000000 candidates?
k*2^1000+c or ((210*k)+q)*2^1000+c ?
How many candidates were left after sieving how deep (6 tuple and 7 tuple)?
biwema is offline   Reply With Quote
Old 2012-04-30, 23:01   #73
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×3×7×137 Posts
Default

I sieved upto only 10M for most of the range using gsieve. 150M is the number of candidates remaining after the sieving for the range 0-46P. The sieving only took a couple of days on a single quad. My n is exactly 1000.
Each candidate is a k*2^n-1 that needs to be tested(and if prime pfgw will test +1 +5 etc).

It seems that you effectively use 2 instead of 1.781 as your constant. This isn't bad but it does build up when you get to 7-tuples.
2^7=128 while 1.781^7=~57
henryzz is offline   Reply With Quote
Old 2012-05-03, 06:13   #74
Cybertronic
 
Cybertronic's Avatar
 
Jan 2007
DEUTSCHLAND !

3×89 Posts
Default

Hello members !

Can everybody of you writing a sieve like APSIEVE (without PRPing) with features:
- sparse sieve like NewPGen
- k-tuplets up to k=10
- sieving up to 10^13...?
- form k*p#+a1,a2,...

?

best,
Norman

Last fiddled with by Cybertronic on 2012-05-03 at 06:15
Cybertronic is offline   Reply With Quote
Old 2012-05-05, 12:22   #75
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

575410 Posts
Default

I believe it should be possible to modify gsieve to do that. It should pretty much just need the function initprimes modifying. Unfortunately I don't understand that function so I can't do it.
henryzz is offline   Reply With Quote
Old 2012-07-21, 21:07   #76
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×3×7×137 Posts
Default

I have tested n=1000 for 7-tuples upto 34P.
I have found 324 quads and 15 quins so far.
I have sieved until 81P so testing should go fast for a bit. I hope to have found a run or two of six primes by then. Note this isn't a 6-tuple as a 6-tuple isn't contained within a 7-tuple.
henryzz is offline   Reply With Quote
Old 2013-06-22, 19:32   #77
Puzzle-Peter
 
Puzzle-Peter's Avatar
 
Jun 2009

22×132 Posts
Default

It's me again...

I'm trying to adapt the codes in this thread to a new brain-fart of mine, but it seems to be beyond my capabilities.

I'd like to search for triplets of the form k*x -1, +1, +5 with x being a precomputed constant of several thousands of digits.

I know k has to be a multiple of 6. I also know that for the x I'm using to test this, a must end in 2 or 8. That leaves a = 12, 18, 42, 48, 72, 78 etc. which makes two strings of numbers
a=30*n+12
a=30*n+18
with n = [0...chosenlimit]

I thought about doing two runs, one for the 30*n+12 version and one for 30*n+18. I have a PFGW script to precompute a table (text file) which contains lines of
p, x MOD p
for all primes p below a chosen sieve limit, then use this information to go through an array of booleans and set those to 0 where (a*(x MOD p)) equals +1, p-1 or p-5.
And this is where the fun starts. I seem to be unable to determine which a values to cancel out. I can find them by hand by simply trying from the low end upwards to the first hit, then go up by steps of the size p, but I don't seem to be able to create the formula for finding the first one. Plus this would probably be much more efficient on a bit array rather than booleans.

I know the codes here in this thread contain all the stuff I need. I keep looking at the init_indexes function from Sex_2.pas in post #34, but what is happening there is beyond my grasp. So any hints or help would be greatly appreciated.

In case you're wondering about my motivation for this: I'd like to try and go for a triple too large to prove with PRIMO. So I use a number x that makes a N+1 or N-1 proof possible for all three members of the triple. I tried this for a small example (a few dozen digits) to make sure it works by using PFGW and brute force. For larger numbers I need a good sieve though. I have a working PFGW "sieve" script, but it's based on the FACTORIZE function which makes it too slow for large numbers.
Puzzle-Peter is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How/Where to get Jens Kruse Andersen's prime constellation sieve? Stargate38 And now for something completely different 2 2017-04-28 00:08
Efficiently finding a linear progression in data fivemack Math 27 2015-12-12 18:42
GPU Prime Sieve tapion64 GPU Computing 7 2014-04-10 06:15
Sieve depth vs. prime probability Unregistered Information & Answers 2 2010-05-25 20:51
Prime in Riesel Sieve Project Sloth Prime Sierpinski Project 1 2006-05-10 02:02

All times are UTC. The time now is 03:03.

Sat Dec 5 03:03:19 UTC 2020 up 1 day, 23:14, 0 users, load averages: 1.44, 1.50, 1.49

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.