Curve Counts

Prime95 · 2005-03-09, 19:43

According to http://www.loria.fr/~zimmerma/records/ecm/params.html the curve counts listed for the 2- and 2+ pages is too high. The values I use came from ECMNet's pages several years ago.

I suspect I should convert my pages to use these new values. Opinions anyone?

akruppa · 2005-03-09, 19:56

I wanted to post something about curve counts for a while but I'm still running tests on how often gmp-ecm finds factors vs. computed values (looking very good so far) and also haven't had the time to write something up yet. I'm pretty sure that the expected curve numbers computed by GMP-ECM 6 are pretty close to the truth, and that the old figures were too high. I also think the effect of curves with smaller bounds on larger factor sizes should be considered and the bound level should be increased when the probability of missing a factor of the target size with *all* curves done so far is <exp(-1). This will further reduce the number of curves to do at each level.

I'll try to write something more coherent when the latest batch of test curves finish and I have a moment to put together the results.

Alex

Prime95 · 2005-03-09, 21:36

Quote:

Originally Posted by akruppa

I also think the effect of curves with smaller bounds on larger factor sizes should be considered and the bound level should be increased when the probability of missing a factor of the target size with *all* curves done so far is <exp(-1). This will further reduce the number of curves to do at each level.

So you are saying that the new table on ECMNet's page does not take into account curves done with smaller B1. That is, to find a 30-digit factor if no ECM has been done requires 648 curves at B1=250,000. But if you've already done 262 curves at B1=50,000, then we only need to do (roughly) 648 - (262 / (250000 / 50000)) = 596 more curves at 250,000.

akruppa · 2005-03-09, 22:15

Yes.

The expected number of curves to find a p30 with B1=50k, B2=100*B1 is 5268. Doing 262 curves does 262/5268 = .0497 of the required work, so only 616 additional curves at B1=250k should be needed to get the probability of a miss <exp(-1). The effect from curves with smaller bounds, say B1=11k, is very small and can be ignored.

Similarly, if someone does curves at a high bound before the expected number of curves at lower levels are done, the effect of the "large" curves on smaller factor sizes should be considered. This will also avoid people waste cpu time on small bounds to "fill in gaps" when a lot of curves at high bounds have been done already. There are no actual gaps, they are merely an artifact of the bookkeeping method.

I think it might be better to not count curves but a fraction or percent, where "p45 nn% done" means that the probability of missing a p45 with the curves that have been done so far is exp(-nn/100). If people do curves with varying B2 parameters, for example by fine-tuning gmp-ecm, the "standard curve" with B2=100*B1 become a rather arbitrary unit that everyone need to convert to. Normalizing the unit to "100% = all finished" is probably easier in the long run.

Comments cordially invited!

Alex

Prime95 · 2005-03-10, 02:14

Quote:

Originally Posted by akruppa

I think it might be better to not count curves but a fraction or percent, where "p45 nn% done" means that the probability of missing a p45 with the curves that have been done so far is exp(-nn/100). If people do curves with varying B2 parameters, for example by fine-tuning gmp-ecm, the "standard curve" with B2=100*B1 become a rather arbitrary unit that everyone need to convert to. Normalizing the unit to "100% = all finished" is probably easier in the long run.

Technically, I agree. But from a human-factors (and historical) point of view maybe not. Prime95 ECM users are oft-times beginners. It is simpler for them to say: "I did a hundred curves on Mxxx with B1=yyy". They may have difficulty converting that to a percentage. By and large, GMP-ECM users are a much more seasoned breed.

BTW, I have to plead guilty to some sloppy bookkeeping. In my tables, GMP-ECM curve counts emailed to me are simply doubled no matter what B2 is chosen. I do appreciate the forum threads here which aggregate GMP-ECM curves and compute the multiplier properly.

garo · 2005-03-10, 10:20

Alex,
I think I'll take your suggestion for updating the Cunningham tables in the forum here. I'm also leaning towards removing the 2- and 2+ tables altogether (with the exception of 2LM) since having these tables on both George's pages and the forum is just confusing and adds work and the probability of an error.

Wacky · 2005-03-10, 12:06

Quote:

Originally Posted by garo

I'm also leaning towards removing the 2- and 2+ tables altogether (with the exception of 2LM) since having these tables on both George's pages and the forum is just confusing ...

If you do so, I suggest that you leave a deep link to George's corresponding pages along with the explanation as to why you have omittted them.

rogue · 2005-03-10, 13:23

Quote:

Originally Posted by garo

Alex,
I think I'll take your suggestion for updating the Cunningham tables in the forum here. I'm also leaning towards removing the 2- and 2+ tables altogether (with the exception of 2LM) since having these tables on both George's pages and the forum is just confusing and adds work and the probability of an error.

Here is my 2 cents.

Since George's pages only have 2+/2-, maybe he could redirect his links to the thread in this forum. The format of the tables in this forum, plus all of the other information available, such as which are reserved, make this forum a better resource.

Also, maybe Paul Zimmerman can point his Cunningham project to that thread in this forum. Again, the format is far easier to understand than those on his website.

I like one-stop shopping and to have only 1 place to coordinate all Cunningham work is a good thing.

Prime95 · 2005-03-10, 13:43

I have no problem with letting someone else maintain the 2- and 2+ tables in the forums. I'll do whatever everyone thinks is best.

Mystwalker · 2005-03-10, 13:49

My short answer would be:

A lot of people can maintain those tables, but only few (or maybe only one?) can improve prime95/mprime.

garo · 2005-03-10, 14:13

For historical reasons, I'm inclined to let George handle the 2+ and 2- tables. Plus, believe me, updating all the tables is a pain and very time-consuming and if I have two less tables to handle I'll be a lot happier :)

Regardless, it is always possible to give other people - including George - mod privileges on the forum so if we do decide to host everything on the forum, we should be able to divide the work. I did an update on the the tables last week but I'm still waiting for an email response or two before I finish the job and upload the tables that are now residing on my HD.

BTW, I wanted to ask Xyzzy if it is possible to enable HTML on the forum. Maybe I have asked before and he has said no already but I don't remember.

2005-03-09, 19:43	#1
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 3×11×223 Posts	Curve Counts According to http://www.loria.fr/~zimmerma/records/ecm/params.html the curve counts listed for the 2- and 2+ pages is too high. The values I use came from ECMNet's pages several years ago. I suspect I should convert my pages to use these new values. Opinions anyone?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
post counts	Raman	Forum Feedback	67	2016-01-07 18:35
Why different shift counts are important	Madpoo	Data	6	2015-10-11 03:55
I don't understand these relation counts	fivemack	Msieve	4	2012-10-29 11:26
Dedidicated rig; What counts in Prime Crunching?	kaffikanne	Hardware	10	2009-12-12 23:46
Case of the disappearing post counts...	PrimeCruncher	Lounge	7	2004-10-31 22:07

2005-03-09, 19:56	#2
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	I wanted to post something about curve counts for a while but I'm still running tests on how often gmp-ecm finds factors vs. computed values (looking very good so far) and also haven't had the time to write something up yet. I'm pretty sure that the expected curve numbers computed by GMP-ECM 6 are pretty close to the truth, and that the old figures were too high. I also think the effect of curves with smaller bounds on larger factor sizes should be considered and the bound level should be increased when the probability of missing a factor of the target size with all curves done so far is <exp(-1). This will further reduce the number of curves to do at each level. I'll try to write something more coherent when the latest batch of test curves finish and I have a moment to put together the results. Alex

2005-03-09, 22:15	#4
akruppa "Nancy" Aug 2002 Alexandria 4643₈ Posts	Yes. The expected number of curves to find a p30 with B1=50k, B2=100B1 is 5268. Doing 262 curves does 262/5268 = .0497 of the required work, so only 616 additional curves at B1=250k should be needed to get the probability of a miss <exp(-1). The effect from curves with smaller bounds, say B1=11k, is very small and can be ignored. Similarly, if someone does curves at a high bound before the expected number of curves at lower levels are done, the effect of the "large" curves on smaller factor sizes should be considered. This will also avoid people waste cpu time on small bounds to "fill in gaps" when a lot of curves at high bounds have been done already. There are no actual gaps, they are merely an artifact of the bookkeeping method. I think it might be better to not count curves but a fraction or percent, where "p45 nn% done" means that the probability of missing a p45 with the curves that have been done so far is exp(-nn/100). If people do curves with varying B2 parameters, for example by fine-tuning gmp-ecm, the "standard curve" with B2=100B1 become a rather arbitrary unit that everyone need to convert to. Normalizing the unit to "100% = all finished" is probably easier in the long run. Comments cordially invited! Alex

2005-03-10, 10:20	#6
garo Aug 2002 Termonfeckin, IE 3²×307 Posts	Alex, I think I'll take your suggestion for updating the Cunningham tables in the forum here. I'm also leaning towards removing the 2- and 2+ tables altogether (with the exception of 2LM) since having these tables on both George's pages and the forum is just confusing and adds work and the probability of an error.

2005-03-10, 13:43	#9
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 1CBF₁₆ Posts	I have no problem with letting someone else maintain the 2- and 2+ tables in the forums. I'll do whatever everyone thinks is best.

2005-03-10, 13:49	#10
Mystwalker Jul 2004 Potsdam, Germany 33F₁₆ Posts	My short answer would be: A lot of people can maintain those tables, but only few (or maybe only one?) can improve prime95/mprime.

2005-03-10, 14:13	#11
garo Aug 2002 Termonfeckin, IE 3²×307 Posts	For historical reasons, I'm inclined to let George handle the 2+ and 2- tables. Plus, believe me, updating all the tables is a pain and very time-consuming and if I have two less tables to handle I'll be a lot happier :) Regardless, it is always possible to give other people - including George - mod privileges on the forum so if we do decide to host everything on the forum, we should be able to divide the work. I did an update on the the tables last week but I'm still waiting for an email response or two before I finish the job and upload the tables that are now residing on my HD. BTW, I wanted to ask Xyzzy if it is possible to enable HTML on the forum. Maybe I have asked before and he has said no already but I don't remember.