mersenneforum.org Riesel base 3 new testing idea
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2008-11-23, 02:22 #1 gd_barnes     May 2007 Kansas; USA 1037210 Posts Riesel base 3 new testing idea I don't want to mess up the automated scripts that are already set up but......how would everyone like to only test 43% instead of 50% of all k's (at the current k-range); hence cutting 14% off of total testing time as well as relieving Kenneth of the burden of removing multiples of the base?!! Here's the deal: In the automated processing thread, Karsten and I and others were having a discussion about appropriatly removing k's that are multiples of the base. After much thinking on my part, I determined that such a thing was actually quite easy. Willem (Siemelink) confirmed my thinking. It goes like this: If a k that is divisible by the base (b) has a prime at n=0, then the k must remain otherwise it can be removed immediately. That's all! To make it a little easier, I came up with the following: k*b^0-1 = k*1-1 = k-1 So, all that one has to do with a k that is divisible by b is to test and see if k-1 is prime. If so, that k can be removed! What brought this to light here is that I thought I'd try a double-check on the k=500M-505M range due to the extremely few # of k's remaining. I only have 2 slow cores that I'm willing to put on it and I wanted as fast a way as possible to do it. With that explanation out of the way, here is my idea: Since only even k must be tested for base 3 and we want to separate out k's divisible by b, we have 3 different tests we need to run: 1. all k==(2 mod 6) 2. all k==(4 mod 6) 3. all k==(0 mod 6) but only where k-1 is prime Based on that, I came up with the following 3 PFGW scripts that need to be run: Script 1, test all k==(2 mod 6); (starting k-value must be == 2 mod 6]: ABC2 $b*3^$a-1 // {number_primes,$b,1} a: from 1 to 10000 b: from 500e6 to 505e6 step 6 Script 2, test all k==(4 mod 6); [starting k-value must be == 4 mod 6]: ABC2$b*3^$a-1 // {number_primes,$b,1} a: from 1 to 10000 b: from 500000002 to 505e6 step 6 Script 3, the coupe de grace : ABC2 ($b+1)*3^$a-1 // {number_primes,$b,1} a: from 1 to 10000 b: primes from 500e6 to 505e6 :surprised The kicker here is that script 3 is actually testing 2 TIMES as many k's as it needs to. When it's done, if there are any k's remaining without a prime, you have to remove any of them NOT divisible by 3. If there was a way to make PFGW only test k's where a prime+1 was divisible by 3, it would test exactly the k's needed and we could save ~30% of our total testing time. As you can see, I like to test by k-value instead of n-value when doing many k's over a relatively small n-range. That allows me to stop it at any point since PFGW has the bad habit of not remembering the k's that it has found a prime for when you restart it. Although I only have 2 cores for it, each core just runs 1/3rd slower. I based my % savings on the fact that at this k-range, approximately 1 out of 20 numbers is prime. So instead of testing all even k-values or half of them, you end up testing: 1/6 + 1/6 + 1/20*2 = 5/30 + 5/30 + 3/30 = 13/30 = 43%. So percentage of time saved = 1 - 43/50 = .14 or 14%. Gary P.S. I'm still trying to think of a way to make PFGW not test the primes where prime+1 is divisible by 3 and still stop after finding a prime for each one. It can be done but it either wouldn't stop after a prime or it would skip some k's. Last fiddled with by gd_barnes on 2008-11-23 at 02:24 2008-12-12, 21:30 #2 Flatlander I quite division it "Chris" Feb 2005 England 40358 Posts Quote:  Originally Posted by gd_barnes ... P.S. I'm still trying to think of a way to make PFGW not test the primes where prime+1 is divisible by 3 and still stop after finding a prime for each one. It can be done but it either wouldn't stop after a prime or it would skip some k's. Any success with that? Quote:  If a k that is divisible by the base (b) has a prime at n=0, then the k must remain otherwise it can be removed immediately. Quote:  So, all that one has to do with a k that is divisible by b is to test and see if k-1 is prime. If so, that k can be removed! Is it me or you? Before I start the range I have just reserved maybe you could tell me what you think is the optimum/fastest way of testing a range. edit: Quote:  a: from 1 to 10000 Why did you choose 10000? Last fiddled with by Flatlander on 2008-12-12 at 22:19 2008-12-14, 04:09 #3 Flatlander I quite division it "Chris" Feb 2005 England 31·67 Posts I've adapted Willem's script from the 'Starting your own base 101' thread. I think it does what Gary suggested above. Quote:  1. all k==(2 mod 6) 2. all k==(4 mod 6) 3. all k==(0 mod 6) but only where k-1 is prime Chris edit: Aaargh! It's 4:10 a.m. I should be in bed. It might have to be run with -tp because we need primes not PRPs for k-1. Attached Files  RB3start.txt (1.6 KB, 180 views) Last fiddled with by Flatlander on 2008-12-14 at 04:21 2008-12-14, 15:56 #4 Flatlander I quite division it "Chris" Feb 2005 England 31·67 Posts Quote:  Originally Posted by Flatlander ... It might have to be run with -tp because we need primes not PRPs for k-1. It would seem this is not necessary. If have run this: Code: ABC2$a
a: from 660000005 to 700000000 step 6
with and without -tp, and the two files are identical. (I will test higher soon.)
I will now start my reserved range using the script above. If someone spots something wrong I will restart.

edit:
983,552 primes were produced for the 6.67m tests in the above giving a density of 14.75%.

Last fiddled with by Flatlander on 2008-12-14 at 16:51

2008-12-14, 18:26   #5
gd_barnes

May 2007
Kansas; USA

22×2,593 Posts

Quote:
 Originally Posted by Flatlander It would seem this is not necessary. If have run this: Code: ABC2 $a a: from 660000005 to 700000000 step 6 with and without -tp, and the two files are identical. (I will test higher soon.) I will now start my reserved range using the script above. If someone spots something wrong I will restart. edit: 983,552 primes were produced for the 6.67m tests in the above giving a density of 14.75%. They were only identical because you did not happen to encounter any composite 3-PRP's in the particular range that you tested. They are very rare, even at the low range that you are testing but they will be there eventually. You definitely need to test with the -tp option at some point. You can run an initial test without it to get the 3-PRP's and then run another test using the -tp switch only on the 3-PRP's to verify primality. Gary 2008-12-14, 21:39 #6 Flatlander I quite division it "Chris" Feb 2005 England 31·67 Posts Here's what I'll do : 1) Run RB3start.txt with -f. (Delete pfgw.log and pfgw-prime.log.) 2) Run this: Quote:  ABC2$a a: from 500000005 to 510000000 step 6
First with -f, then with -tp.
Compare the two files. (fc pfgw.log pfgw-prime.log >differences.txt)
Any composite PRPs (false positives) can be deleted from the file generated in step 1.
Any primes that weren't found as PRPs (false negatives) must be tested individually.
(Delete or rename pfgw.log and pfgw-prime.log before next step.)

3) Check the PRPs found in step 1 with -tp. (Check for composite PRPs and find the first real prime for those ks.)

4) Sieve/test the remaining ks from step 1, to n=25000.

Though, in fact, I have already tested ks from 660m to 1bn (step 2) and there were no false positives or false negatives. So step 2 can be skipped for now.

Last fiddled with by Flatlander on 2008-12-14 at 21:40

2008-12-15, 04:11   #7
gd_barnes

May 2007
Kansas; USA

22×2,593 Posts

Quote:
 Originally Posted by Flatlander Here's what I'll do : 1) Run RB3start.txt with -f. (Delete pfgw.log and pfgw-prime.log.) 2) Run this: First with -f, then with -tp. Compare the two files. (fc pfgw.log pfgw-prime.log >differences.txt) Any composite PRPs (false positives) can be deleted from the file generated in step 1. Any primes that weren't found as PRPs (false negatives) must be tested individually. (Delete or rename pfgw.log and pfgw-prime.log before next step.) 3) Check the PRPs found in step 1 with -tp. (Check for composite PRPs and find the first real prime for those ks.) 4) Sieve/test the remaining ks from step 1, to n=25000. Though, in fact, I have already tested ks from 660m to 1bn (step 2) and there were no false positives or false negatives. So step 2 can be skipped for now.

This looks OK but I'll have to trust you on some of it because:

1. I'm not familiar enough with the code in RB3start.txt that you posted to properly review it.

2. I don't know what you mean by false negatives. I've never known a prime that was not a PRP. Is that possible? Assuming not, the statement about the 'false negatives' is a moot point and doesn't really matter.

Gary

2008-12-15, 06:13   #8
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

3·2,083 Posts

Quote:
 Originally Posted by gd_barnes 2. I don't know what you mean by false negatives. I've never known a prime that was not a PRP. Is that possible? Assuming not, the statement about the 'false negatives' is a moot point and doesn't really matter.
No, "false negatives" are not possible. Assuming that the machine used is reasonably stable, if a PRP test says a number is composite, it is *definitely* composite. The only doubt that PRP tests leave is in regard to the probable primes themselves.

2008-12-15, 13:28   #9
Flatlander
I quite division it

"Chris"
Feb 2005
England

31·67 Posts

Quote:
 Originally Posted by mdettweiler No, "false negatives" are not possible. Assuming that the machine used is reasonably stable, if a PRP test says a number is composite, it is *definitely* composite. The only doubt that PRP tests leave is in regard to the probable primes themselves.
By' false negative' I meant a prime for which no PRP had been found. Any differences between the PRP file and the prime file will be easily detected.

edit:
I wasn't sure if they were possible; apparently not then.

Quote:
 1. I'm not familiar enough with the code in RB3start.txt that you posted to properly review it.
Basically, it's just:
Code:
Psuedocode:
FOR k = mink TO maxk STEP 2
IF  k mod 6 == 0 THEN only test this k if k-1 is prime
ELSE
Test this k
NEXT k
(My granny would turn in her grave if she saw all the GOTOs in the real code. I have programmed (mostly BASIC) on and off since 1982 but, iirc, this is the first time I have used GOTO.)

Last fiddled with by Flatlander on 2008-12-15 at 14:26

2008-12-17, 03:13   #10
gd_barnes

May 2007
Kansas; USA

242048 Posts

Quote:
 Originally Posted by Flatlander By' false negative' I meant a prime for which no PRP had been found. Any differences between the PRP file and the prime file will be easily detected. edit: I wasn't sure if they were possible; apparently not then. Basically, it's just: Code: Psuedocode: FOR k = mink TO maxk STEP 2 IF k mod 6 == 0 THEN only test this k if k-1 is prime ELSE Test this k NEXT k (My granny would turn in her grave if she saw all the GOTOs in the real code. I have programmed (mostly BASIC) on and off since 1982 but, iirc, this is the first time I have used GOTO.)

Thanks for the pseudocode. It looks correct.

 2008-12-20, 00:19 #11 Flatlander I quite division it     "Chris" Feb 2005 England 31·67 Posts This: Code: ABC2 \$a a: from 3 to 20000001 step 2 produces identical results with -f and -tp, so now I know it's safe to automatically remove m.o.b. and trivial ks for other conjectures with k up to 2000001. Last fiddled with by Flatlander on 2008-12-20 at 00:19

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post gd_barnes Conjectures 'R Us 428 2021-05-15 15:43 gd_barnes Conjectures 'R Us 84 2011-06-03 18:07 jasong Conjectures 'R Us 36 2010-08-03 06:25 em99010pepe Sierpinski/Riesel Base 5 8 2010-06-08 21:21 michaf Conjectures 'R Us 49 2007-12-17 05:03

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

Tue May 18 08:03:40 UTC 2021 up 40 days, 2:44, 0 users, load averages: 1.77, 2.04, 1.94

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