mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Conjectures 'R Us

Reply
 
Thread Tools
Old 2008-11-23, 02:22   #1
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

27EB16 Posts
Default 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
gd_barnes is offline   Reply With Quote
Old 2008-12-12, 21:30   #2
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

31×67 Posts
Default

Quote:
Originally Posted by gd_barnes View Post
...
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
Flatlander is offline   Reply With Quote
Old 2008-12-14, 04:09   #3
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

31·67 Posts
Default

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
File Type: txt RB3start.txt (1.6 KB, 114 views)

Last fiddled with by Flatlander on 2008-12-14 at 04:21
Flatlander is offline   Reply With Quote
Old 2008-12-14, 15:56   #4
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

31×67 Posts
Default

Quote:
Originally Posted by Flatlander View Post
...

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
Flatlander is offline   Reply With Quote
Old 2008-12-14, 18:26   #5
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

237538 Posts
Default

Quote:
Originally Posted by Flatlander View Post
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
gd_barnes is offline   Reply With Quote
Old 2008-12-14, 21:39   #6
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

31×67 Posts
Default

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
Flatlander is offline   Reply With Quote
Old 2008-12-15, 04:11   #7
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

11×929 Posts
Default

Quote:
Originally Posted by Flatlander View Post
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
gd_barnes is offline   Reply With Quote
Old 2008-12-15, 06:13   #8
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

792 Posts
Default

Quote:
Originally Posted by gd_barnes View Post
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.
mdettweiler is offline   Reply With Quote
Old 2008-12-15, 13:28   #9
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

31×67 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
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
Flatlander is offline   Reply With Quote
Old 2008-12-17, 03:13   #10
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

11·929 Posts
Default

Quote:
Originally Posted by Flatlander View Post
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.
gd_barnes is offline   Reply With Quote
Old 2008-12-20, 00:19   #11
Flatlander
I quite division it
 
Flatlander's Avatar
 
"Chris"
Feb 2005
England

31×67 Posts
Default

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
Flatlander is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Riesel/Sierp base 2 even-k/even-n/odd-n testing gd_barnes Conjectures 'R Us 422 2020-08-05 05:56
Riesel base 2 discussion gd_barnes Conjectures 'R Us 84 2011-06-03 18:07
Base-6 speed for prime testing vs. base-2 jasong Conjectures 'R Us 36 2010-08-03 06:25
Riesel Base 5 LLR em99010pepe Sierpinski/Riesel Base 5 8 2010-06-08 21:21
Sierpinski / Riesel - Base 22 michaf Conjectures 'R Us 49 2007-12-17 05:03

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

Tue Oct 20 09:45:57 UTC 2020 up 40 days, 6:56, 0 users, load averages: 1.47, 1.56, 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.