mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2009-12-30, 19:47   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

6,011 Posts
Default 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.
henryzz is offline   Reply With Quote
Old 2009-12-30, 23:09   #2
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

341310 Posts
Default

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.
ATH is offline   Reply With Quote
Old 2009-12-30, 23:30   #3
axn
 
axn's Avatar
 
Jun 2003

34×67 Posts
Default

You could just ask akruppa. He wrote the implementation.
axn is offline   Reply With Quote
Old 2009-12-31, 00:10   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,597 Posts
Default

It's O(sqrt(B2)), there can be other log factors in the formula.
R. Gerbicz is offline   Reply With Quote
Old 2009-12-31, 11:07   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

177B16 Posts
Default

Quote:
Originally Posted by ATH View Post
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 View Post
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 View Post
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.
henryzz is offline   Reply With Quote
Old 2009-12-31, 11:19   #6
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

248210 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
Andi47 is offline   Reply With Quote
Old 2009-12-31, 11:53   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

6,011 Posts
Default

Quote:
Originally Posted by Andi47 View Post
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
henryzz is offline   Reply With Quote
Old 2009-12-31, 14:22   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2009-12-31, 17:51   #9
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

6,011 Posts
Default

Quote:
Originally Posted by akruppa View Post
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
henryzz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GNFS estimates 10metreh Factoring 48 2009-04-08 01:54
Chebyshev's Estimates brownkenny Math 2 2009-01-22 17:21
Msieve QS estimates henryzz Msieve 27 2009-01-21 18:37
How much time Unregistered Information & Answers 4 2008-12-20 21:00
Accuracy of completion date estimates? kdq Software 4 2008-10-04 05:02

All times are UTC. The time now is 08:04.


Tue Nov 29 08:04:42 UTC 2022 up 103 days, 5:33, 0 users, load averages: 1.29, 1.08, 0.99

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔