mersenneforum.org Aliqueit.exe discussion
 Register FAQ Search Today's Posts Mark Forums Read

 2009-03-18, 14:15 #12 mklasson   Feb 2004 10216 Posts Ah, gcc doesn't like Code: found_factor( mpz_class( trial_primes[j] ), factors ); Try changing it to Code: mpz_class tmp( trial_primes[j] ); found_factor( tmp, factors ); for now... Sorry for spamming this thread btw. EDIT: btw, just noticed something odd about yafu: Code: >yafu siqs(rho(1813647130602161341)) finds the factors and prints them to the screen (after a second "***factors found***"), but not to factor.log. Last fiddled with by mklasson on 2009-03-18 at 14:17 Reason: btw
2009-03-18, 14:50   #13
bsquared

"Ben"
Feb 2007

22×32×7×13 Posts

Quote:
 Originally Posted by mklasson Ah, gcc doesn't like Code: found_factor( mpz_class( trial_primes[j] ), factors ); Try changing it to Code: mpz_class tmp( trial_primes[j] ); found_factor( tmp, factors ); for now...
That worked, thanks. I also needed to change the run_yafu function slightly to put " " around the command, because linux needs them. Windows is indifferent to the quotes, so they might as well be in there all the time.

I've attached the modified .cc file.

Quote:
 Originally Posted by mklasson Sorry for spamming this thread btw.
Agreed, mods feel free to move this stuff where appropriate... including maybe the stuff below into the yafu thread.

Quote:
 Originally Posted by mklasson EDIT: btw, just noticed something odd about yafu: Code: >yafu siqs(rho(1813647130602161341)) finds the factors and prints them to the screen (after a second "***factors found***"), but not to factor.log.
This should be simple to fix, thanks.

- ben
Attached Files
 aliqueit-mod.txt (19.5 KB, 318 views)

Last fiddled with by bsquared on 2009-03-18 at 14:51 Reason: added attachment

 2009-03-18, 16:14 #14 KriZp     Feb 2007 2078 Posts It compiled for me with 'g++ aliqueit.cc -lgmp' where aliqueit.cc is the modified file from post #17. It is currently halfway through 800 ECM curves on a C104. Looking forward to see if it switches to ggnfs properly.
2009-03-18, 16:56   #15
mklasson

Feb 2004

1000000102 Posts

Quote:
 Originally Posted by KriZp It compiled for me with 'g++ aliqueit.cc -lgmp' where aliqueit.cc is the modified file from post #17. It is currently halfway through 800 ECM curves on a C104. Looking forward to see if it switches to ggnfs properly.
I hope you have changed the ggnfs_cmd setting in aliqueit.ini to something appropriate for your system. You'll also need to change the ggnfs_clean_cmd if you want the ggnfs work files to be deleted upon successful completion.

 2009-03-18, 18:01 #16 KriZp     Feb 2007 33·5 Posts yes, It appeared that I needed to specify the full path for it to work, even though I had put the contents of my ggnfs/bin folder into the aliqueit101 folder. It started looking for a polynomial now.
2009-03-19, 01:33   #17
mklasson

Feb 2004

1000000102 Posts

Quote:
 Originally Posted by bsquared For larger inputs say > 85 digits I'd start with the table in the GMP-ECM readme file and target doing ECM to, say, the 2/9*N digit level if the input is QSable or 1/3*N digit level if the input would otherwise need NFS.
I think 1/3*N might be a bit excessive. For a 120-digit composite that amount of ecm (factors <= 40 digits using gmp-ecm-readme settings) would seem to take me ~10 cpu-hours, whereas just pounding on it with ggnfs takes slightly more than twice that time. That's too much ecm, isn't it?

I did some experimental benchmarking today to find good ecm levels for <65 digits. It's a shame it's not that easy for c100+.

Hm, come to think of it, as nfs has better asymptotics shouldn't the ecm scaling factor for nfs be smaller than the corresponding one for qs? I.e. using 2/9*N for qs and 3/9*N for nfs seems inherently wrong. I realise they're both fuzzy guidelines, but don't you agree?

Maybe something like 11+1/5*N would be better for nfs? Or maybe I'm just wrong. In any case, how much ecm do you people often running big nfs jobs normally do?

2009-03-19, 04:45   #18
bsquared

"Ben"
Feb 2007

22×32×7×13 Posts

Quote:
 Originally Posted by mklasson I think 1/3*N might be a bit excessive. For a 120-digit composite that amount of ecm (factors <= 40 digits using gmp-ecm-readme settings) would seem to take me ~10 cpu-hours, whereas just pounding on it with ggnfs takes slightly more than twice that time. That's too much ecm, isn't it? I did some experimental benchmarking today to find good ecm levels for <65 digits. It's a shame it's not that easy for c100+. Hm, come to think of it, as nfs has better asymptotics shouldn't the ecm scaling factor for nfs be smaller than the corresponding one for qs? I.e. using 2/9*N for qs and 3/9*N for nfs seems inherently wrong. I realise they're both fuzzy guidelines, but don't you agree? Maybe something like 11+1/5*N would be better for nfs? Or maybe I'm just wrong. In any case, how much ecm do you people often running big nfs jobs normally do?
This is a good discussion, I'd love to hear someone else's opinion too. The 2/9 and 3/9 levels are often quoted for SNFS vs GNFS, and when QS is in its wheelhouse (65 to 95 digits) I liken it more to SNFS. After that point, scaling takes over and QS goes away entirely. I'll admit I don't often do the complete 1/3*N ECM level for GNFS, but I run the 64 bit linux AMD optimized lattice siever which many people still may not run, and that throws the ratio off a bit I think.

I agree that spending half the time a gnfs run would have taken on ecm seems excessive, but I don't have any data to suggest a better choice. Over a large number of factorizations, maybe something like 1/3 the time, max, would be better? Sorry I can't be more concrete.

2009-03-19, 08:14   #19
10metreh

Nov 2008

2×33×43 Posts

Quote:
 Originally Posted by mklasson I think 1/3*N might be a bit excessive. For a 120-digit composite that amount of ecm (factors <= 40 digits using gmp-ecm-readme settings) would seem to take me ~10 cpu-hours, whereas just pounding on it with ggnfs takes slightly more than twice that time. That's too much ecm, isn't it? I did some experimental benchmarking today to find good ecm levels for <65 digits. It's a shame it's not that easy for c100+. Hm, come to think of it, as nfs has better asymptotics shouldn't the ecm scaling factor for nfs be smaller than the corresponding one for qs? I.e. using 2/9*N for qs and 3/9*N for nfs seems inherently wrong. I realise they're both fuzzy guidelines, but don't you agree? Maybe something like 11+1/5*N would be better for nfs? Or maybe I'm just wrong. In any case, how much ecm do you people often running big nfs jobs normally do?
What about 2/7*N? That's what I use.

2009-03-19, 19:12   #20
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT)

569610 Posts

Quote:
 Originally Posted by 10metreh What about 2/7*N? That's what I use.
that was what i was told at some point as well

2009-03-19, 20:36   #21
mklasson

Feb 2004

2×3×43 Posts

Quote:
 Originally Posted by 10metreh What about 2/7*N? That's what I use.
I'm still not really satisfied. For a c120 I'd then do ecm to a 34.3-digit factor level. That's about 1.25 cpu-hours work, whereas the ggnfs job takes ~20-25 cpu-hours. ECMing for just 1/16th of the sieve time seems a little frugal. Ben mentioned a few posts above a tentative recommendation of ~1/3 the sieve time, and I noticed in another thread fivemack said he does about 1/4 (http://www.mersenneforum.org/showpos...&postcount=148).

Any simple fraction*N factor-digits ecm rule probably matches reality pretty badly for one size or another, assuming a constant ratio of ecm_time to sieve_time is correct, which I'm not even sure it is. Ultimately we want to find a factor as quickly as possible. Running gnfs guarantees we'll find it after a certain period of time, while doing ecm gives us a chance to maybe find it sooner. Doing ecm yields progressively worse returns though. About all I can say is that we probably should spend more than zero time ecming, but less than the full sieve time.

I still hope someone can step up with some solid math and explain the reasoning behind it and/or point to a good chunk of empirical data. Maybe something taking into consideration the probability of our composite having a factor of a certain size and the probability per time unit of finding such a factor with ecm. The gmp-ecm readme file gives at least a part of the solution in the quote "After performing the expected number of curves from Table 1, the probability that a factor of D digits was missed is exp(-1), i.e., about 37%." Anyway, surely there are wizards lurking around here for whom such tricks is a trifling matter.

In the meantime I'll be releasing a new version soon that is a lot faster for small numbers (using experimentally determined better ecm limits and letting yafu work its pollard rho magic), and hopefully a little better for bigger numbers. Without knowing what the optimal targets even are for bigger numbers though, it's hard to say. Anyway, you're of course all welcome to alter the config/source and use whatever limits you prefer.

 2009-03-20, 00:34 #22 mklasson   Feb 2004 2·3·43 Posts Well then, get aliqueit v1.02. + much faster for small numbers, and probably faster for bigger numbers, i.e. better ecm tuning. + compiles and runs under linux now. Thanks Ben. + detects when a sequence merges with an earlier sequence. Setting "detect_merge = false" can be used to skip this, should you want to try and hit the possibly imminent termination anyway. + hides yafu/msieve screen output for composites < digits. Unwanted output is redirected to . Hopefully it still compiles under linux... I can't test it, but I don't think you'll have any problems. The config file contains a few OS specific settings at the top that you'll need to change when running under non-windows. I ended up targeting ecm_time = 1/4*qs_time (or gnfs_time) by rummaging through logs of previous factorisations and constructing linear expressions for fitting the ecm efforts properly at c70 and c95 for qs and c100 and c120 for gnfs. Assuming it's a good idea to do a quarter ecm relative to the qs/gnfs time this version should perform better than previous ones on c70+. The timings are for my machine, a core i7, so ymmv. The estimates are probably decent on most machines. For qs I ended up with Code: 0.448f * input_digits - 11.26f for 20.1 at c70 and 31.3 at c95. These values are the maximum factor size we will search for using the recommended ecm steps in gmp-ecm's readme. For gnfs I got Code: 9.4f + 0.235f * input_digits for 32.9 at c100 and 37.6 at c120. To test the performance on smaller numbers I ran the Ben-chmark of doing the first 1225 lines of sequence 10212: Code: aliqueit v1.01: 1m38s Ben's unofficial yafu-aliquot: 1m18s aliqueit v1.02: 56s Performance on these small numbers is still pretty irrelevant imho, but hooray!

 Similar Threads Thread Thread Starter Forum Replies Last Post johnadam74 Aliquot Sequences 4 2016-03-28 12:32 pakaran Aliquot Sequences 2 2015-09-12 23:10 EdH Aliquot Sequences 6 2011-12-13 18:58 science_man_88 Aliquot Sequences 185 2011-11-08 12:18 Greebley Aliquot Sequences 35 2010-02-13 15:23

All times are UTC. The time now is 14:27.

Thu Aug 13 14:27:25 UTC 2020 up 11:02, 1 user, load averages: 1.62, 1.55, 1.58