mersenneforum.org P-1 B2 time estimates
 Register FAQ Search Today's Posts Mark Forums Read

 2009-12-30, 19:47 #1 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 37·163 Posts P-1 B2 time estimates P-1 B1 seems to be rather linear in the time to run. 1e9 takes ~10x 1e8 However, P-1 B2 isn't at all linear in the time it takes to run. Is there any relatively accurate way of estimating the length of time a certain B2 will take based on lower times? I want to work out the estimated workdone for different B1 and B2 combinations to find what the most efficient combination is.
 2009-12-30, 23:09 #2 ATH Einyen     Dec 2003 Denmark 2×17×101 Posts I went abit nuts awhile back with Excel regression analysis. Post #4 and #8 here: http://www.mersenneforum.org/showthread.php?t=9658 I also found that step1 time is linear function of B1, but step2 time is proportional to about B20.6.
 2009-12-30, 23:30 #3 axn     Jun 2003 153C16 Posts You could just ask akruppa. He wrote the implementation.
 2009-12-31, 00:10 #4 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 161110 Posts It's O(sqrt(B2)), there can be other log factors in the formula.
2009-12-31, 11:07   #5
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

37×163 Posts

Quote:
 Originally Posted by ATH I went abit nuts awhile back with Excel regression analysis. Post #4 and #8 here: http://www.mersenneforum.org/showthread.php?t=9658 I also found that step1 time is linear function of B1, but step2 time is proportional to about B20.6.
That thread looks like it is based on the old P-1 stage 2 that was in 6.1.x.
I will keep the results there in mind though and make suitable alterations if necessary.

Quote:
 Originally Posted by axn You could just ask akruppa. He wrote the implementation.
Hence why i posted in his little corner of messenneforum.
Quote:
 Originally Posted by R. Gerbicz It's O(sqrt(B2)), there can be other log factors in the formula.
This seems a reasonable estimate although it is a little out.
A B2 from 1e8-2e8 took 0.26 seconds
A B2 from 1e10-2e10 took 2.6 seconds.
A B2 from 1e12-2e12 took 32 seconds.
A B2 from 1e14-2e14 took 365 seconds.
In theory each step here should be 10x longer than the previous one. It starts off well but losses it after a while. Maybe the log factors you mentioned explain that.
The pc wasnt completely idle while doing these benchmarks although it shouldnt have influenced much. I will redo them on a completely idle pc at somepoint soon.

2009-12-31, 11:19   #6
Andi47

Oct 2004
Austria

2×17×73 Posts

Quote:
 Originally Posted by henryzz In theory each step here should be 10x longer than the previous one. It starts off well but losses it after a while. Maybe the log factors you mentioned explain that. The pc wasnt completely idle while doing these benchmarks although it shouldnt have influenced much. I will redo them on a completely idle pc at somepoint soon.
Maybe it's also influenced by RAM: You can fit B2=1e15 and maybe even B2=1e16 into 2 GB of RAM (use something like -maxmem 1950), but it will be somewhat slower than expected - and slower than if it had 4 GB of RAM available.

2009-12-31, 11:53   #7
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

178F16 Posts

Quote:
 Originally Posted by Andi47 Maybe it's also influenced by RAM: You can fit B2=1e15 and maybe even B2=1e16 into 2 GB of RAM (use something like -maxmem 1950), but it will be somewhat slower than expected - and slower than if it had 4 GB of RAM available.
i dont think there was any ram-scaling done in any of those tests

 2009-12-31, 14:22 #8 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Not an easy answer (yet again) I'm afraid. Building polynomial from roots, computing its inverse (I think) and the polyeval algorithm all take asymptotically O(n log(n)^2 loglog(n)), where n is the polynomial degree (usually in the millions). Computing the roots takes O(dS^2), where S is the degree used for the Brent-Suyama extension (e.g., 30). Reducing a polynomial modulo another is basically just a multiplication, so O(n log(n) loglog(n)). With k blocks, k+1 polynomials are built from their roots (F, and the k pieces of G), k-1 modulo reductions, if k>1 the inverse is computed, and the polyeval at the end. So yes, the time does depend on memory or more specifically, on the polynomial degree dF and the number of blocks k that you use. If you want to try curve fits, do separate fits with contant k. Alex
2009-12-31, 17:51   #9
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

37×163 Posts

Quote:
 Originally Posted by akruppa Not an easy answer (yet again) I'm afraid. Building polynomial from roots, computing its inverse (I think) and the polyeval algorithm all take asymptotically O(n log(n)^2 loglog(n)), where n is the polynomial degree (usually in the millions). Computing the roots takes O(dS^2), where S is the degree used for the Brent-Suyama extension (e.g., 30). Reducing a polynomial modulo another is basically just a multiplication, so O(n log(n) loglog(n)). With k blocks, k+1 polynomials are built from their roots (F, and the k pieces of G), k-1 modulo reductions, if k>1 the inverse is computed, and the polyeval at the end. So yes, the time does depend on memory or more specifically, on the polynomial degree dF and the number of blocks k that you use. If you want to try curve fits, do separate fits with contant k. Alex
the k values were bouncing around in my trials
i will fix it in my next trials

 Similar Threads Thread Thread Starter Forum Replies Last Post 10metreh Factoring 48 2009-04-08 01:54 brownkenny Math 2 2009-01-22 17:21 henryzz Msieve 27 2009-01-21 18:37 Unregistered Information & Answers 4 2008-12-20 21:00 kdq Software 4 2008-10-04 05:02

All times are UTC. The time now is 00:35.

Fri Feb 3 00:35:49 UTC 2023 up 168 days, 22:04, 1 user, load averages: 1.80, 1.33, 1.09