mersenneforum.org  

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

Reply
 
Thread Tools
Old 2012-02-09, 14:41   #1
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

1E0B16 Posts
Default P-1 formula (help wanted)

For those that do a lot of P-1, the Test/Status menu choice and sending expected completion dates are rather time consuming. This is because prime95 computes the optimal bounds every time.

My idea is to replace the optimal bounds calculation with a simple formula that's accurate within 10% or so for the most common cases.

Would someone like to do a little research and if possible come up with a formula that takes in exponent, TF, and available mem and generates a reasonably accurate guess of B1 and B2?

Thanks!
Prime95 is offline   Reply With Quote
Old 2012-02-09, 14:51   #2
NBtarheel_33
 
NBtarheel_33's Avatar
 
"Nathan"
Jul 2008
Maryland, USA

100010110112 Posts
Talking

Quote:
Originally Posted by Prime95 View Post
For those that do a lot of P-1, the Test/Status menu choice and sending expected completion dates are rather time consuming. This is because prime95 computes the optimal bounds every time.

My idea is to replace the optimal bounds calculation with a simple formula that's accurate within 10% or so for the most common cases.

Would someone like to do a little research and if possible come up with a formula that takes in exponent, TF, and available mem and generates a reasonably accurate guess of B1 and B2?

Thanks!
What if these bounds were calculated and stored (say as part of the worktodo line) the first time an ETA is requested? There could then be an option added to the Status menu, say "Recalculate P-1 Bounds" that a user could activate in the event of significant changes to system uptime, RAM, or CPU. Until a recalc is requested, simply use the previously calculated bounds in all ETA calculations.
NBtarheel_33 is offline   Reply With Quote
Old 2012-02-09, 15:03   #3
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

7,691 Posts
Default

Quote:
Originally Posted by NBtarheel_33 View Post
What if these bounds were calculated and stored (say as part of the worktodo line) the first time an ETA is requested?
That is my alternative approach if a formula is not feasible.
Prime95 is offline   Reply With Quote
Old 2012-02-09, 15:59   #4
axn
 
axn's Avatar
 
Jun 2003

22·1,301 Posts
Default

Sort the expos (well, find min/max expo per FFT). Calculate the bounds for the first and last expo for each FFT length. Interpolate linearly for the others. Should be very accurate at the expense of 2-4 bound calculations.

Last fiddled with by axn on 2012-02-09 at 16:00
axn is online now   Reply With Quote
Old 2012-02-09, 22:48   #5
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10AE16 Posts
Default

If we were to see a table of the results of the current optimal bounds calculations, a best-fit formula would likely be easy to extrapolate.

Quote:
Originally Posted by Prime95 View Post
Quote:
Originally Posted by NBtarheel_33 View Post
What if these bounds were calculated and stored (say as part of the worktodo line) the first time an ETA is requested? There could then be an option added to the Status menu, say "Recalculate P-1 Bounds" that a user could activate in the event of significant changes to system uptime, RAM, or CPU. Until a recalc is requested, simply use the previously calculated bounds in all ETA calculations.
That is my alternative approach if a formula is not feasible.
If you go this way, I'd suggest you could also store the significant machine info (or a hash of it) in the worktodo, so Prime95 can automatically know when it needs to recalculate, rather than it be user-triggered.
Mini-Geek is offline   Reply With Quote
Old 2012-02-09, 22:59   #6
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

11100001101012 Posts
Default

Perhaps after calculating the bounds, just auto-convert a PFactor line to a Pminus1 line, except with the AID.


(And is there anything wrong with the way it is? Sure, it takes a few seconds, but so what?)

Last fiddled with by Dubslow on 2012-02-09 at 23:04
Dubslow is offline   Reply With Quote
Old 2012-02-10, 02:26   #7
KingKurly
 
KingKurly's Avatar
 
Sep 2010
Annapolis, MD, USA

33·7 Posts
Default

Quote:
Originally Posted by Dubslow View Post
(And is there anything wrong with the way it is? Sure, it takes a few seconds, but so what?)
Yes, if I have dozens of assignments, that's a quite a long time.
KingKurly is offline   Reply With Quote
Old 2012-02-10, 02:37   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by Prime95 View Post
For those that do a lot of P-1, the Test/Status menu choice and sending expected completion dates are rather time consuming. This is because prime95 computes the optimal bounds every time.

My idea is to replace the optimal bounds calculation with a simple formula that's accurate within 10% or so for the most common cases.

Would someone like to do a little research and if possible come up with a formula that takes in exponent, TF, and available mem and generates a reasonably accurate guess of B1 and B2?

Thanks!
This is poorly posed. What is the objective function that you are
optimizing??

"Guess B1 and B2". Guess their values to achieve what goal?
If you answer "maximize the probability of success", it is not a
realistic goal, since you can always increase that probability up to
1 simply by taking B1 and B2 large enough.....

If you want to (say) maximize the probability of success per unit
time spent, you can get that data from my "Practical Analysis of ECM"
paper. Running P-1 is equivalent to running ECM with just one curve.

If you want to select B1 and B2 to maximize the probability of success
given a FIXED RUN TIME, then my paper shows how to do that as well.

If the factor you seek is (say) 1 mod q for some value q, then simply
adjust the size of factor being sought by the size of q.
R.D. Silverman is offline   Reply With Quote
Old 2012-02-10, 02:53   #9
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
This is poorly posed. What is the objective function that you are
optimizing??

"Guess B1 and B2". Guess their values to achieve what goal?
If you answer "maximize the probability of success", it is not a
realistic goal, since you can always increase that probability up to
1 simply by taking B1 and B2 large enough.....

If you want to (say) maximize the probability of success per unit
time spent, you can get that data from my "Practical Analysis of ECM"
paper. Running P-1 is equivalent to running ECM with just one curve.

If you want to select B1 and B2 to maximize the probability of success
given a FIXED RUN TIME, then my paper shows how to do that as well.

If the factor you seek is (say) 1 mod q for some value q, then simply
adjust the size of factor being sought by the size of q.
I think you missed what he's getting at. Prime95 already has an excellent bounds optimizer, which optimizes for maximum success for lowest running time*. The problem is, running the optimizer on many many assignments at once can take a while, which is what happens whenever someone does the "Get ETAs for all assignments" function in Prime95. So he's looking for a way to shortcut it, for the ETA purpose. Linear interpolations have been suggested, as have just doing the regular algorithm once and saving the results. The optimization algorithm itself is just fine.

Personally, I don't see why the results would be different depending on when I run the algorithm. Why not just use the bounds in the save files (or put them in worktodo as MG and I have suggested), whenever they're requested?

Quote:
Originally Posted by KingKurly View Post
Yes, if I have dozens of assignments, that's a quite a long time.
I have 29 P-1 assignments currently, and it took 7 seconds to run (yes I did time it). That's just fine in my book. If I have 50 and it takes 10 seconds, it's still not that big a deal, IMO. (I'd rather George work on AVX/mem-bandwidth than the ETA function, for they'll have greater long term impact on GIMPS, but then, it's his program and time.)

Last fiddled with by Dubslow on 2012-02-10 at 02:57
Dubslow is offline   Reply With Quote
Old 2012-02-10, 03:13   #10
bcp19
 
bcp19's Avatar
 
Oct 2011

7×97 Posts
Default

Quote:
Originally Posted by Dubslow View Post
I think you missed what he's getting at. Prime95 already has an excellent bounds optimizer, which optimizes for maximum success for lowest running time*. The problem is, running the optimizer on many many assignments at once can take a while, which is what happens whenever someone does the "Get ETAs for all assignments" function in Prime95. So he's looking for a way to shortcut it, for the ETA purpose. Linear interpolations have been suggested, as have just doing the regular algorithm once and saving the results. The optimization algorithm itself is just fine.

Personally, I don't see why the results would be different depending on when I run the algorithm. Why not just use the bounds in the save files (or put them in worktodo as MG and I have suggested), whenever they're requested?



I have 29 P-1 assignments currently, and it took 7 seconds to run (yes I did time it). That's just fine in my book. If I have 50 and it takes 10 seconds, it's still not that big a deal, IMO. (I'd rather George work on AVX/mem-bandwidth than the ETA function, for they'll have greater long term impact on GIMPS, but then, it's his program and time.)
I think it is for people like James who are rerunning poorly done P-1's on low level exp's. I have an old AMD Turion that is running 8M exp's and his site gave me 1700 in the range I picked up, so if I click status on that machine, I have to walk away and come back around 20 min later. Part of why I set it to report once a week, as that also takes quite a bit of time.
bcp19 is offline   Reply With Quote
Old 2012-02-10, 03:38   #11
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Ah. 1700>>50. Point taken.
Dubslow is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Most Wanted rogue FermatSearch 35 2021-03-15 14:06
Fibonacci Formula MattcAnderson Math 7 2013-01-14 23:29
Most wanted kar_bon Riesel Prime Data Collecting (k*2^n-1) 15 2011-08-09 16:50
New LLT formula hoca Math 7 2007-03-05 17:41
100 Most Wanted Citrix Factoring 24 2004-02-22 01:05

All times are UTC. The time now is 05:01.


Thu Dec 9 05:01:21 UTC 2021 up 138 days, 23:30, 0 users, load averages: 2.38, 1.90, 1.68

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.