mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-05-13, 11:24   #1
axn
 
axn's Avatar
 
Jun 2003

144616 Posts
Exclamation P-1 bounds calculation for Wagstaff numbers

I would've thought that the bounds calculation for P-1 would be same for same-sized Mersennes and Wagstaff numbers considering that they have the same properties for their potential factors (i.e. 2kp+1). But, alas no!
Quote:
Originally Posted by ecm.c
if (k == 1.0 && b == 2 && c == -1) kk = kk / 2.0 / n;
Only mersennes get the adjustment. This should be extended to Wagstaffs also.

Thoughts?
axn is online now   Reply With Quote
Old 2011-05-14, 18:23   #2
chris2be8
 
chris2be8's Avatar
 
Sep 2009

42268 Posts
Default

It sounds a good idea. Are there any other classes of number with potentially useful properties for their factors?

Chris K
chris2be8 is offline   Reply With Quote
Old 2011-05-14, 21:20   #3
diep
 
diep's Avatar
 
Sep 2006
The Netherlands

11·71 Posts
Default

Quote:
Originally Posted by axn View Post
I would've thought that the bounds calculation for P-1 would be same for same-sized Mersennes and Wagstaff numbers considering that they have the same properties for their potential factors (i.e. 2kp+1). But, alas no!

Only mersennes get the adjustment. This should be extended to Wagstaffs also.

Thoughts?
Would be great if adjustment happens as well for Wagstaff!

diep is offline   Reply With Quote
Old 2011-05-14, 21:26   #4
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by axn View Post
I would've thought that the bounds calculation for P-1 would be same for same-sized Mersennes and Wagstaff numbers considering that they have the same properties for their potential factors (i.e. 2kp+1). But, alas no!

Only mersennes get the adjustment. This should be extended to Wagstaffs also.

Thoughts?
In each case, check whether the P-1 (or whatever) software actually takes useful account of those properties of potential factors!

For instance, with Mersennes the P-1 routine automatically throws the Mersenne exponent (p, or "n" in the quoted ecm.c code) into the computation wherever appropriate, regardless of B1/B2.

If the same were not done for Wagstaffs (or chris2be8's "any other classes of number"), it would be inappropriate to adjust the bounds calculation as if it were.

Last fiddled with by cheesehead on 2011-05-14 at 21:30
cheesehead is offline   Reply With Quote
Old 2011-05-15, 02:16   #5
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

3×13×197 Posts
Default

If someone posts the list of numbers that have the "2kp+1" property I'd be happy to add it to prime95.
Prime95 is offline   Reply With Quote
Old 2011-05-15, 06:09   #6
axn
 
axn's Avatar
 
Jun 2003

2·3·5·173 Posts
Default

Quote:
Originally Posted by Prime95 View Post
If someone posts the list of numbers that have the "2kp+1" property I'd be happy to add it to prime95.
IIUC, b^n+/-1 ==> k=1, |c|=1 should cover all of them. I'd really appreciate it if someone could confirm this.

Quote:
Originally Posted by cheesehead View Post
In each case, check whether the P-1 (or whatever) software actually takes useful account of those properties of potential factors!

For instance, with Mersennes the P-1 routine automatically throws the Mersenne exponent (p, or "n" in the quoted ecm.c code) into the computation wherever appropriate, regardless of B1/B2.

If the same were not done for Wagstaffs (or chris2be8's "any other classes of number"), it would be inappropriate to adjust the bounds calculation as if it were.
Good point. A quick test using P95 indicates that this is the case for Wagstaff. I will check the code to see if I can confirm. At any rate, if it is not the case, it doesn't really hurt to throw in the exponent there just for the heck of it _regardless_ of the form of the number
axn is online now   Reply With Quote
Old 2011-05-15, 07:01   #7
axn
 
axn's Avatar
 
Jun 2003

144616 Posts
Default

From ecm.c
Code:
/* For Mersenne numbers, 2^n-1, make sure we include 2n in the calculated */
/* exponent (since factors are of the form 2kn+1).  For Fermat numbers, */
/* 2^n+1 (n is a power of 2), make sure the exponent is included in the */
/* calculated exponent as factors are of the form kn+1.  Otherwise, do */
/* nothing special -- start with one. */

	if (lower == 0 && k == 1.0 && b == 2 && c == -1) itog (2*n, g);
	else if (lower == 0 && k == 1.0 && b == 2 && c == 1) itog (n, g);
	else setone (g);
So, it appears that Wagstaff numbers benefit from the Fermat logic. But, it is probably simpler to get rid of the condition and always use 2*n.
axn is online now   Reply With Quote
Old 2011-05-15, 21:25   #8
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

3·13·197 Posts
Default

Quote:
Originally Posted by axn View Post
So, it appears that Wagstaff numbers benefit from the Fermat logic. But, it is probably simpler to get rid of the condition and always use 2*n.
But does it use this info in calculating the optimal P-1 bounds?
Prime95 is offline   Reply With Quote
Old 2011-05-16, 03:30   #9
axn
 
axn's Avatar
 
Jun 2003

2·3·5·173 Posts
Default

Quote:
Originally Posted by Prime95 View Post
But does it use this info in calculating the optimal P-1 bounds?
Nope. The relevant piece of code is posted in the OP. Only the mersennes get this (not even Fermats).
axn is online now   Reply With Quote
Old 2011-12-13, 10:26   #10
axn
 
axn's Avatar
 
Jun 2003

144616 Posts
Default

*BUMP*

I have made some modifications to ecm.c. If you can verify and incorporate it into next release of P95, that'll be great.

Changes include:
1. Changing the check criteria for the 2*p extra factor to k=1, abs(c)=1. [Updated both the probability calculation, as well as where the factor is introduced during P-1 exponentiation.]
2. Introduced a base conversion factor to calculate the total number of squarings during an LL (prp) test for bases other than 2. This will fix up the cost calculation for P-1.

Note:- I have not made any changes to any comments. I haven't compiled, let alone tested, any of these changes.
Attached Files
File Type: txt ecm.txt (187.9 KB, 830 views)
axn is online now   Reply With Quote
Old 2018-07-24, 06:27   #11
GP2
 
GP2's Avatar
 
Sep 2003

5×11×47 Posts
Default

I took a look at the source code for version 29.4 b7 and it seems the original code mentioned in the first post in this thread is still there (in guess_pminus1_bounds and guess_pminus1_probability).

Was there ever any consensus reached about whether it should be changed?

Empirically, Wagstaff factors do seem to follow the same 2kp + 1 pattern.
GP2 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
PRIMALITY PROOF for Wagstaff numbers! AntonVrba Math 96 2009-02-25 10:37
Bernoulli and Euler numbers (Sam Wagstaff project) fivemack Factoring 4 2008-02-24 00:39
Carmichael Numbers-Upper bounds devarajkandadai Math 1 2007-03-19 04:53
Lower bounds for odd multiperfect numbers. jchein1 Math 7 2006-11-26 13:29
P-1 bounds calculation question axn Software 2 2006-03-04 16:49

All times are UTC. The time now is 18:53.


Fri Dec 3 18:53:16 UTC 2021 up 133 days, 13:22, 0 users, load averages: 0.95, 0.92, 1.00

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.