mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > CADO-NFS

Reply
 
Thread Tools
Old 2022-01-05, 19:33   #78
charybdis
 
charybdis's Avatar
 
Apr 2020

19·37 Posts
Default

Quote:
Originally Posted by bur View Post
The yield per 5000 q varies quite strongly, just the last three workunits had 20273, 15446 and 17053, respectively.
This is normal, it's a consequence of the varying number of special-q within ranges of size 5000. The number of relations per special-q varies much less.

Incidentally, the number of special-q per range varies less when sieving on the rational side, so on the SNFS jobs that require this, the number of relations per WU does not have as much variation.
charybdis is offline   Reply With Quote
Old 2022-01-10, 08:14   #79
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

503 Posts
Default

I'm at 190M relations of which 69.7% or 132M are unique. The C167 took 152M uniques to build a matrix, what number of uniqes can I expect for a C170?

Is the necessary number of uniques just a function of log(n) or are there other influences?

And from comparison with that C167 the uniques ratio seems a bit low, what does it depend on? Just the q-range or also size/poly/...?
bur is offline   Reply With Quote
Old 2022-01-10, 17:37   #80
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

17×311 Posts
Default

Quote:
Originally Posted by bur View Post
And from comparison with that C167 the uniques ratio seems a bit low, what does it depend on? Just the q-range or also size/poly/...?
Random properties of the poly. No way to predict ahead of time what uniques ratio will be. However, as you note Q-range does influence uniques ratio. I am happy if I'm above 70% on a job.

I expect you'll need more uniques than you did for a C167, but I've no idea how many more- maybe 5%? 10%? There's a lot of noise here, too- your C167 with a different poly may have needed 150M or 155M, etc.
VBCurtis is offline   Reply With Quote
Old 2022-01-11, 11:02   #81
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

503 Posts
Default

So the poly influences the uniques ratio, but "random" meaning not depending on the score? Is the same true for the required number of uniques? This would mean that a slightly lower scoring poly could perform better overall?

I'm at 205M total and 143M uniques (69.8%). I'll wait another day, which should bring me to 220M total and 153M uniques, before attempting to build a matrix.

That would make it 14 days of sieving for the 220M. The C167 took 12 days until I could build a matrix, so it's actually going quite well.

Btw, if C165 to C170 will double the sieving time, what is the time ratio between C167 and C170? I've been wondering that generally, interpolating within a linear relation is easy, but what is the rule for x^n?

Last fiddled with by bur on 2022-01-11 at 11:53
bur is offline   Reply With Quote
Old 2022-01-12, 08:31   #82
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

503 Posts
Default

Curtis, you suggested excess of 0.05 for building the matrix with CADO. For msieve I think the same effect is achieved with target-density? What would be a good value? Charybdis used target_density = 100 for his c170 posted on the first page of this thread.
bur is offline   Reply With Quote
Old 2022-01-12, 12:26   #83
charybdis
 
charybdis's Avatar
 
Apr 2020

12778 Posts
Default

Quote:
Originally Posted by bur View Post
Curtis, you suggested excess of 0.05 for building the matrix with CADO. For msieve I think the same effect is achieved with target-density? What would be a good value? Charybdis used target_density = 100 for his c170 posted on the first page of this thread.
The effect isn't exactly the same, though both can be used to ensure that the matrix you get isn't way too big. required_excess tells filtering not to try building a matrix if the excess is too small. target_density (in both msieve and CADO, though the values cannot be directly compared between the two) tells the merge process how dense a matrix it should try to build; denser matrices are smaller and therefore run faster, but more relations are required to build a denser matrix. The error "too few cycles, matrix probably cannot build" in msieve tells you that there weren't enough relations to build a matrix with the chosen target_density.

100 is probably sensible, though the optimum value for a given job depends on the ratio of sieving to LA speed for your system.

Last fiddled with by charybdis on 2022-01-12 at 12:28
charybdis is offline   Reply With Quote
Old 2022-01-12, 17:53   #84
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

503 Posts
Default

Thanks, but msieve has no equivalent to required_excess?


The first attempt failed as expected. I had 154M uniques (the recent C167 took 152M):
Code:
Wed Jan 12 16:44:33 2022  keeping 41220401 ideals with weight <= 200, target excess is 216115
Wed Jan 12 16:44:36 2022  commencing in-memory singleton removal
Wed Jan 12 16:44:40 2022  begin with 39898507 relations and 41220401 unique ideals
Wed Jan 12 16:45:37 2022  reduce to 39629881 relations and 40951589 ideals in 21 passes
Wed Jan 12 16:45:37 2022  max relations containing the same ideal: 200
 Wed Jan 12 16:45:39 2022  filtering wants 1000000 more relations

Is it possible to estimate the number of required additional uniques from the relations:ideals ratio?
bur is offline   Reply With Quote
Old 2022-01-12, 23:11   #85
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

17·311 Posts
Default

Correct, msieve has no filtering equivalent to required_excess. We use target_density as a proxy.

Yes, you can estimate based on how early the filtering failed; but it's easier to just try filtering with a lower target_density (like default) rather than try to recall just how far away you might be based on your previous experience. That is, if a C165-175 filtering run usually has 12 filtering passes and yours failed on pass 1, you need quite a few more relations- but if it failed after pass 8 or 9, it nearly worked and an adjustment to target density or a few M more relations will get you a matrix.
VBCurtis is offline   Reply With Quote
Old 2022-01-12, 23:46   #86
charybdis
 
charybdis's Avatar
 
Apr 2020

12778 Posts
Default

In this case filtering would have failed whatever target_density was used, because there were more ideals than relations. Once you have more relations than ideals and the excess is greater than the displayed target excess value, filtering will proceed until the merge phase - maybe if it's extremely tight it could fail earlier, but I've never seen that - and if target_density is too high you get "too few cycles, matrix probably cannot build". Before the merge begins, target_density is not used at all.

I wish there was an option to dump the output of clique removal to disk if merging fails, so that you could run merge at different TDs without having to go through all the earlier stages of filtering again...
charybdis is offline   Reply With Quote
Old 2022-01-13, 08:51   #87
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

503 Posts
Default

Second attempt with 230M rels and 162M uniques, it went through to the full merge, but quit there. So it's getting closer.

Btw, if C165 to C170 will double the sieving time, what is the time ratio between C167 and C170? I've been wondering that generally, interpolating within a linear relation is easy, but what is the rule for an exponential relation?
bur is offline   Reply With Quote
Old 2022-01-13, 09:23   #88
axn
 
axn's Avatar
 
Jun 2003

14F516 Posts
Default

Quote:
Originally Posted by bur View Post
what is the time ratio between C167 and C170? I've been wondering that generally, interpolating within a linear relation is easy, but what is the rule for an exponential relation?
5 digits = factor of 2
1 digit = factor of 2^(1/5) ~= 1.15
3 digits = factor of 2^(3/5) ~= 1.52

Linear interpolation between 1 & 2 wouldn't be too far off though. You'd get 1.6 which is good enough for gov't purposes.
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Some CADO-NFS Work At Around 175-180 Decimal Digits EdH CADO-NFS 127 2020-10-07 01:47
Sigma parameter in ecm storm5510 Information & Answers 4 2019-11-30 21:32
PrimeNet error 7: Invalid parameter ksteczk PrimeNet 6 2018-03-26 15:11
Parameter Underestimation R.D. Silverman Cunningham Tables 14 2010-09-29 19:56
ECM Work and Parameter Choices R.D. Silverman Cunningham Tables 11 2006-03-06 18:46

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


Thu May 26 01:35:43 UTC 2022 up 41 days, 23:37, 0 users, load averages: 1.28, 1.21, 1.17

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.

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