mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-06-01, 16:17   #23
charybdis
 
charybdis's Avatar
 
Apr 2020

1F616 Posts
Default

Nicely done!

Quote:
Originally Posted by bsquared View Post
At the risk of increasing confusion, I ran this through yafu's poly select and it slightly prefers the other degree 5:
Yes:

Quote:
Originally Posted by charybdis View Post
You could also represent this number as 8*1281979*2^520+1, giving c5 = 10255832, c0 = 1, Y1 = 1, Y0 = -2^104. This choice of polynomial might even be slightly faster than yours; at least it has a higher E-score. For some numbers there will be even more polynomials to choose between: this will often be the case when near the crossover between degree 5 and degree 6, for instance (and here we have to test-sieve, as E-scores from different degrees are not comparable).
I suggested sieving on the rational side but YAFU just about prefers algebraic side for this polynomial - for a larger number this would call for test-sieving. k*2^n+1 would be a rational side job for the usual small values of k (e.g. 1) but as k gets bigger so do the algebraic norms.
charybdis is offline   Reply With Quote
Old 2021-06-01, 17:47   #24
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

23×54 Posts
Default

Quote:
Originally Posted by bur View Post
The factorization completed successfully!

Slightly less than 2 hours instead of 3 days for a GNFS c149.

It went back to sieving a couple of times due to me setting the rels_wanted too low as charybdis mentioned.
I think you'll fly through all the composites under 2^600 for your chosen k-value rather quickly now. :)

I'd try making lim0 and lim1 the same (use the larger of the two from my C120 file). That'll require a few more relations, maybe 10% more, but the job should go faster. About every 30 bits of exponent increase, step to the next-bigger params file for lim/lpb choices.
VBCurtis is offline   Reply With Quote
Old 2021-06-01, 18:27   #25
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

401 Posts
Default

I updated Yafu, poly generation works, it's even doing test sieving on two polys.


Quote:
I'd try making lim0 and lim1 the same (use the larger of the two from my C120 file). That'll require a few more relations, maybe 10% more, but the job should go faster. About every 30 bits of exponent increase, step to the next-bigger params file for lim/lpb choices.
Thanks for the advise. So I should just use the lim/lpb from the next params file but otherwise still use the params.c120?


And out of curiosity, what is the reasoning behing making lim0 and lim1 the same, why does it save time?

Last fiddled with by bur on 2021-06-01 at 18:29
bur is offline   Reply With Quote
Old 2021-06-01, 19:09   #26
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

23×54 Posts
Default

When the norms of the two sides are quite different in size, CADO is more efficient when making the side with the larger norm also have a larger lim.
Since your job has anorm and rnorm very similar in size, there isn't an obvious reason to make the lim's different in size.

I'd change entirely to params.c125 when you get 30 bits bigger than you are now.

SNFS jobs double in difficulty about every 9 digits, while CADO-GNFS jobs double in difficulty about every 5 digits. With YAFU giving you polynomials, you'll be able to get quite far in your factoring sequence.
VBCurtis is offline   Reply With Quote
Old 2021-06-02, 08:50   #27
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

401 Posts
Default

I tried 2^528 with yafu settings and the sieving had an ETA of about 3 h if I chose tasks.sieve.sqside = 1 as per EdH's guide. I switched to tasks.sieve.sqside = 0 and ETA changed to 1 h. I also changed lim0/1 to 4500000 instead of yafu's 6100000 (yes, never change more than one parameter when testing), but I guess the sqside=0 is the big impact?

Would it be advisable to generally use yafu's settings but with tasks.sieve.sqside = 0?

Last fiddled with by bur on 2021-06-02 at 08:50
bur is offline   Reply With Quote
Old 2021-06-02, 14:41   #28
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

23·54 Posts
Default

It's advisable to experiment a lot, as you are doing. That's how we all learned!
SNFS jobs have fewer "do it this way" guidelines, more job-specific settings.
I'm surprised there is a factor-of-2 difference in speed for sieving the other side- the norms suggest the decision should be a close call.
VBCurtis is offline   Reply With Quote
Old 2021-06-02, 21:40   #29
swellman
 
swellman's Avatar
 
Jun 2012

3,203 Posts
Default

There is a lot of empirical data on Kamada’s site that you may find helpful. It has an accumulation of data as reported over the years. Some cases are certainly non-optimal but all are definitely “what worked”.

There are also the log files spread throughout the various NFS@Home sievers. Start with lasieved - it performs sieving for the smallest factoring jobs. Keep in mind NFS@Home uses a BOINC wrapper so there are some inefficiencies baked in, such as the target number of relations being artificially elevated to compensate for a percentage of “junk” relations received back by the servers from the volunteer workers.

But experimentation is always the best way.
swellman is offline   Reply With Quote
Old 2021-06-02, 23:04   #30
charybdis
 
charybdis's Avatar
 
Apr 2020

2×251 Posts
Default

Quote:
Originally Posted by bur View Post
I tried 2^528 with yafu settings and the sieving had an ETA of about 3 h if I chose tasks.sieve.sqside = 1 as per EdH's guide. I switched to tasks.sieve.sqside = 0 and ETA changed to 1 h. I also changed lim0/1 to 4500000 instead of yafu's 6100000 (yes, never change more than one parameter when testing), but I guess the sqside=0 is the big impact?

Would it be advisable to generally use yafu's settings but with tasks.sieve.sqside = 0?
I don't know how you got such a huge difference in the ETAs; CADO can spit out some suspect values early on in the job, and I bet that if you let these jobs run to completion the running times would be much closer. I did some test-sieving on this number with YAFU's choice of polynomial and params, and tasks.sieve.sqside = 0, ie rational side sieving, is definitely faster - but not by anywhere near that much. The advantage is larger at smaller Q values and I reckon it would amount to ~15% over the whole job.

I calculated the norms for a few relations around Q=2M, and typical values are something like 10^36 for the algebraic norm and 10^39 for the rational norm. This is consistent with a small advantage for rational-side sieving. YAFU's estimates weren't too far off, but it overestimated the algebraic norm and so it chose the algebraic side for sieving.

I'd say keep on using tasks.sieve.sqside = 0 for these jobs, as it's likely that YAFU is systematically overestimating the algebraic norm. The advantage for the rational side should grow as the numbers get larger, until you switch to degree 6 at which point the algebraic side may be worth considering again.

@bsquared, if you're reading this - maybe worth getting YAFU to test-sieve algebraic vs rational when the estimated norms are close together?

Last fiddled with by charybdis on 2021-06-02 at 23:05
charybdis is offline   Reply With Quote
Old 2021-06-03, 06:15   #31
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

401 Posts
Default

Quote:
maybe worth getting YAFU to test-sieve algebraic vs rational when the estimated norms are close together?
I think it does that, when yafu is test-sieving I'm quite sure I saw it doing a test for algebraic side.


Maybe the large difference I found was caused by various factors, cado vs msieve, optimized vbcurtis parameters etc.


What also brings a nice boost is starting at much lower q-values, instead of 60000 I now start at 10000 which for some numbers had 50 rels/q while at the final q it was about 15 or 16. Maybe it's advisable to go even lower.
bur is offline   Reply With Quote
Old 2021-06-03, 11:06   #32
charybdis
 
charybdis's Avatar
 
Apr 2020

2×251 Posts
Default

Quote:
Originally Posted by bur View Post
I think it does that, when yafu is test-sieving I'm quite sure I saw it doing a test for algebraic side.
On this number, YAFU test-sieves three polynomials. For each one, it decides which side it thinks is fastest and tests only that side. I'm suggesting that it should also test algebraic vs rational for the same polynomial.


Quote:
What also brings a nice boost is starting at much lower q-values, instead of 60000 I now start at 10000 which for some numbers had 50 rels/q while at the final q it was about 15 or 16. Maybe it's advisable to go even lower.
Starting at very small q may look faster, but most of those relations will end up being duplicates, and you'll end up needing more raw relations to build a matrix. I did some testing on numbers in the c175-180 range last year which showed that starting at very low q-values is slower despite the increased yield; Curtis's rule of thumb is to aim for a qmin-to-qmax ratio of 7 to 8. I think Curtis has some updated param files for small numbers which he hasn't released yet, and I would guess that the new c120 file will have a larger qmin than 60000.
charybdis is offline   Reply With Quote
Old 2021-06-03, 13:02   #33
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

357810 Posts
Default

Quote:
Originally Posted by charybdis View Post

I calculated the norms for a few relations around Q=2M, and typical values are something like 10^36 for the algebraic norm and 10^39 for the rational norm. This is consistent with a small advantage for rational-side sieving. YAFU's estimates weren't too far off, but it overestimated the algebraic norm and so it chose the algebraic side for sieving.
I use the following as average a,b values for norm estimates (I got these from you a few months back):
a = sqrt((double)(1ULL << (2 * I - 1)) * 1000000.0 * poly->poly->skew);
b = sqrt((double)(1ULL << (2 * I - 1)) * 1000000.0 / poly->poly->skew);

But don't take into account root properties and obviously the Q is static. If there is a better way that is nearly as simple that'd be great.

But the reason it is choosing algebraic side is that yafu is biased that way on purpose. The rational norms need to be about 5 orders of magnitude larger on the rational side before it will choose to sieve there. Can't remember why I did that... I think it's because for gnfs jobs it is usually the case where alg side is better, even when the norms are slighter higher on the rational side.

Quote:
Originally Posted by charybdis View Post
@bsquared, if you're reading this - maybe worth getting YAFU to test-sieve algebraic vs rational when the estimated norms are close together?
Yes, another good idea. Should be fairly straightforward to implement.
bsquared is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A new tool to identify aliquot sequence margins and acquisitions garambois Aliquot Sequences 24 2021-02-25 23:31
Comparison of GNFS/SNFS With Quartic (Why not to use SNFS with a Quartic) EdH EdH 14 2020-04-20 16:21
new candidates for M...46 and M48 cochet Miscellaneous Math 4 2008-10-24 14:33
Please identify! Brian-E Lounge 24 2008-08-01 14:13
Easily identify composites using multiplication Nightgamer360 Miscellaneous Math 9 2007-07-09 17:38

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


Sun Oct 24 04:20:10 UTC 2021 up 92 days, 22:49, 0 users, load averages: 2.93, 2.31, 1.94

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