mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2021-12-30, 17:52   #1
nivek000
 
Dec 2021

17 Posts
Default NFS Expected Runtime

Hi. I have been watching a good number of GNFS factorings in YAFU, but it is still very difficult for me to understand the estimated time remaining. Is there a way to approximate this with the accumulated yield, current search range, etc.? Sometimes very similar digit length numbers take significantly different lengths of time to factor. Is this related to the yield rate (and is this based on the polynomial selection)? Or the size of the factors it will eventually find? Or all of the above?

Thanks.

- Kevin
nivek000 is offline   Reply With Quote
Old 2021-12-30, 19:10   #2
swellman
 
swellman's Avatar
 
Jun 2012

2×1,777 Posts
Default

Quote:
Originally Posted by nivek000 View Post
Hi. I have been watching a good number of GNFS factorings in YAFU, but it is still very difficult for me to understand the estimated time remaining. Is there a way to approximate this with the accumulated yield, current search range, etc.? Sometimes very similar digit length numbers take significantly different lengths of time to factor. Is this related to the yield rate (and is this based on the polynomial selection)? Or the size of the factors it will eventually find? Or all of the above?

Thanks.

- Kevin
To the best of my knowledge, speed of sieving a number N using GNFS is dependent on the Murphy e-score of the polynomial. This value is usually called “combined =“ in the log file produced by msieve. Both speed and score are also dependent on log(N). In other words, a C151 with a first digit of 1 will have characteristics which differ from a C151 starting with digit 9 even though they are both 151 decimal digits long. But I’m certainly no expert!

CADO uses another definition to score its polynomials. But a CADO produced polynomial can be scored in the same manner as msieve by either using msieve (see this post), or by what is often referred to as cownoise from its website domain - click on calculators at the top of the page and use “optimal skew” to calculate the e-score of a polynomial.

Lastly, see this list of top scoring polynomials for reference.
swellman is online now   Reply With Quote
Old 2021-12-30, 20:18   #3
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

22×31×43 Posts
Default

GNFS factoring time does not depend on the size of the factors, only on the size of the input. But that time doubles about every five digits, so a C140 takes about four times as long as a C130 to factor.

I don't use YAFU, so I can't give you good guidance about how to use the screen info to forecast time remaining- but it's pretty easy to forecast the total time for a job using that "double every 5 digits" rule of thumb.

It's not a great plan to skip from e.g. 100 digit demo jobs to a 160 digit beast without getting experience using the factoring software tools. Things happen to make jobs not quite smooth sailing, and learning what to do to save such a job when the cost of a mistake is hours rather than weeks is good for the user's sanity. As you gain experience, you learn what your personal hardware performance is- for instance, what size of job you can finish in a single day. That sort of reference point provides you a useful benchmark to estimate job time for nearly any length of job- though once you get to 170+ digits, memory capacity and custom NFS parameters become important (see the CADO subforum for such discussion examples).
VBCurtis is offline   Reply With Quote
Old 2021-12-30, 20:52   #4
nivek000
 
Dec 2021

17 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
I don't use YAFU, so I can't give you good guidance about how to use the screen info to forecast time remaining-
As a programmer, I can imagine there must be a line in ggnfs that basically says, "If <condition is met> do msieve filter check Else lattice sieve again". The questions would be: what is the condition and does YAFU (or ggnfs, really) write out log data related to the condition check.

I have surmised that there may be an accumulated relations "yield" goal that when reached an msieve filter is run to see if linear algebra can be started. Sometimes it can't start linear algebra and it says "raising min_rels by 5.00 percent" at which point more sieving is done, but is also gives a new min_rels goal. It would be nice to know what the min_rels goal is when nfs starts. Just one sieve would then give you an estimate of the factoring time.

The only thing YAFU prints at the beginning of nfs are some poly constants. I have looked in some of the other misc. files output during processing but have not come across a min_rels type number anywhere.

- Kevin
nivek000 is offline   Reply With Quote
Old 2021-12-30, 21:17   #5
swellman
 
swellman's Avatar
 
Jun 2012

DE216 Posts
Default

There are manual ways to run a small amount of sieving, and once completed Yafu will display its goal number of relations and expected time to reach that goal. I believe the # of relations are hard coded in Yafu based on lpbr and lpba values, the timing is just extrapolation of running time on your hardware.

Once the minimum number of raw relations is reached, Yafu enters the filtering phase after which it may or may not be able to build a matrix. The ability to build a matrix is highly conditional but if a matrix can’t be built, Yafu looks for another 5% raw relations. (This value can be set by the user but 5% is the default.) Repeat.

I presume you’ve read through the code for Yafu. Ggnfs is old, almost abandonware these days, though someone updated it a few years ago.

Hope this helps.

Last fiddled with by swellman on 2021-12-30 at 21:19
swellman is online now   Reply With Quote
Old 2021-12-30, 23:24   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

70438 Posts
Default

Quote:
Originally Posted by nivek000 View Post
As a programmer, I can imagine there must be a line in ggnfs that basically says, "If <condition is met> do msieve filter check Else lattice sieve again". The questions would be: what is the condition and does YAFU (or ggnfs, really) write out log data related to the condition check.

I have surmised that there may be an accumulated relations "yield" goal that when reached an msieve filter is run to see if linear algebra can be started. Sometimes it can't start linear algebra and it says "raising min_rels by 5.00 percent" at which point more sieving is done, but is also gives a new min_rels goal. It would be nice to know what the min_rels goal is when nfs starts. Just one sieve would then give you an estimate of the factoring time.

The only thing YAFU prints at the beginning of nfs are some poly constants. I have looked in some of the other misc. files output during processing but have not come across a min_rels type number anywhere.

- Kevin
After the first round of sieving completes you should see a message like this:

Code:
nfs: found 336433 relations, need at least 4468504 (filtering ETA: 0h 13m), continuing with sieving ...
Which tells you both the min_rels and the ETA to the first filter. It waits to print this until after the sieve so that it can estimate the ETA...
bsquared is offline   Reply With Quote
Old 2021-12-31, 03:30   #7
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

22×1,151 Posts
Default

Quote:
Originally Posted by bsquared View Post
After the first round of sieving completes you should see a message like this:

Code:
nfs: found 336433 relations, need at least 4468504 (filtering ETA: 0h 13m), continuing with sieving ...
Which tells you both the min_rels and the ETA to the first filter. It waits to print this until after the sieve so that it can estimate the ETA...
Is this logged somewhere other than the terminal? By the time I check this, any such message has scrolled away. I don't see it in the nfs.log. Actually, my nfs.log appears to be from an earlier session. Is the nfs.log updated as it sieves or after the fact?
EdH is offline   Reply With Quote
Old 2021-12-31, 09:10   #8
Kvasir
 
Dec 2020

24×3 Posts
Default

Quote:
Originally Posted by EdH View Post
Is this logged somewhere other than the terminal? By the time I check this, any such message has scrolled away. I don't see it in the nfs.log. Actually, my nfs.log appears to be from an earlier session. Is the nfs.log updated as it sieves or after the fact?
Details are logged in factor.log when it's sieving and nfs.log when doing linear algebra. You can follow them using tail -f on linux, or download baretail.exe on windows.
Kvasir is offline   Reply With Quote
Old 2021-12-31, 12:29   #9
nivek000
 
Dec 2021

17 Posts
Default

Quote:
Originally Posted by bsquared View Post
After the first round of sieving completes you should see a message like this:

Code:
nfs: found 336433 relations, need at least 4468504 (filtering ETA: 0h 13m), continuing with sieving ...
Which tells you both the min_rels and the ETA to the first filter. It waits to print this until after the sieve so that it can estimate the ETA...
I have never seen an ETA in this type of message. I must be using a different NFS library that you are. I see messages like...

Code:
12/29/21 18:10:03, final ECM pretested depth: 36.38
12/29/21 18:10:03, scheduler: switching to sieve method
12/29/21 18:10:03, nfs: commencing nfs on c152: 11047006535274396604827194619846887383623935779264657081145934950581563078251248440455538938686026540917445630537112531580439524505632520211989740047529
12/29/21 18:10:03, nfs: input divides 2^521 + 271441
12/29/21 18:10:03, nfs: using supplied cofactor: 11047006535274396604827194619846887383623935779264657081145934950581563078251248440455538938686026540917445630537112531580439524505632520211989740047529
12/29/21 18:10:03, nfs: commencing snfs on c152: 11047006535274396604827194619846887383623935779264657081145934950581563078251248440455538938686026540917445630537112531580439524505632520211989740047529
12/29/21 18:10:05, nfs: commencing lattice sieving with 8 threads
12/29/21 18:22:36, nfs: commencing lattice sieving with 8 threads
And then that continues until...

Code:
12/30/21 23:35:26, nfs: commencing lattice sieving with 8 threads
12/30/21 23:44:39, nfs: commencing msieve filtering
12/30/21 23:47:15, nfs: raising min_rels by 5.00 percent to 10579706
12/30/21 23:47:15, nfs: commencing lattice sieving with 8 threads
12/30/21 23:56:44, nfs: commencing lattice sieving with 8 threads
12/31/21 00:06:15, nfs: commencing msieve filtering
12/31/21 00:09:33, nfs: commencing msieve linear algebra
12/31/21 00:22:06, nfs: commencing msieve sqrt
The only min_rels ever output by the library I am using is if filtering fails.

If you can point me to where to download a "better" library I would be grateful.
nivek000 is offline   Reply With Quote
Old 2021-12-31, 13:34   #10
swellman
 
swellman's Avatar
 
Jun 2012

2·1,777 Posts
Default

What verbose level are you using? I use -v and always see what bsquared is describing. Could that be the issue?

Code:
yafu “nfs(number_to_be_factored)” -v -r -R -ns 20000000,20010000 -siever 14
Or similar syntax.
swellman is online now   Reply With Quote
Old 2021-12-31, 13:44   #11
nivek000
 
Dec 2021

17 Posts
Default

So, that would be the issue. I have not been using the -v flag. With that flag I see lots of ETA values for different parts of the process. Many thanks!

- Kevin
nivek000 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Runtime C++ error Cazor Denis Software 8 2020-11-20 22:56
If you were expected to work, but not expected to get a job or pay, what would be good things to do? jasong Lounge 10 2018-06-04 16:39
runtime question yoyo YAFU 1 2015-01-08 07:07
Predicting QS and NFS runtime jasonp Factoring 2 2011-03-07 01:22
ECM Runtime and F20 D. B. Staple Factoring 11 2007-12-12 16:52

All times are UTC. The time now is 20:44.


Fri Jul 1 20:44:30 UTC 2022 up 78 days, 18:45, 1 user, load averages: 1.80, 1.45, 1.51

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.

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