mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Aliquot Sequences (https://www.mersenneforum.org/forumdisplay.php?f=90)
-   -   Aliqueit.exe discussion (https://www.mersenneforum.org/showthread.php?t=11618)

mklasson 2009-03-18 14:15

Ah, gcc doesn't like
[code]
found_factor( mpz_class( trial_primes[j] ), factors );
[/code]

Try changing it to
[code]
mpz_class tmp( trial_primes[j] );
found_factor( tmp, factors );
[/code]

for now...

Sorry for spamming this thread btw. :smile:

EDIT: btw, just noticed something odd about yafu:
[code]
>yafu siqs(rho(1813647130602161341))
[/code]

finds the factors and prints them to the screen (after a second "***factors found***"), but not to factor.log.

bsquared 2009-03-18 14:50

1 Attachment(s)
[quote=mklasson;165880] Ah, gcc doesn't like
[code]
found_factor( mpz_class( trial_primes[j] ), factors );
[/code]

Try changing it to
[code]
mpz_class tmp( trial_primes[j] );
found_factor( tmp, factors );
[/code]

for now...
[/quote]

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=mklasson;165880]
Sorry for spamming this thread btw. :smile:

[/quote]

Agreed, mods feel free to move this stuff where appropriate... including maybe the stuff below into the yafu thread.


[quote=mklasson;165880]
EDIT: btw, just noticed something odd about yafu:
[code]
>yafu siqs(rho(1813647130602161341))
[/code]

finds the factors and prints them to the screen (after a second "***factors found***"), but not to factor.log. [/quote]

This should be simple to fix, thanks.

- ben

KriZp 2009-03-18 16:14

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.

mklasson 2009-03-18 16:56

[QUOTE=KriZp;165894]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.[/QUOTE]

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.

KriZp 2009-03-18 18:01

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.

mklasson 2009-03-19 01:33

[QUOTE=bsquared;165836]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.[/QUOTE]

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+. :smile:

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?

bsquared 2009-03-19 04:45

[quote=mklasson;165945]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+. :smile:

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?[/quote]

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.

10metreh 2009-03-19 08:14

[quote=mklasson;165945]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+. :smile:

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?[/quote]

What about 2/7*N? That's what I use.

henryzz 2009-03-19 19:12

[quote=10metreh;165972]What about 2/7*N? That's what I use.[/quote]
that was what i was told at some point as well

mklasson 2009-03-19 20:36

[QUOTE=10metreh;165972]What about 2/7*N? That's what I use.[/QUOTE]

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 ([url]http://www.mersenneforum.org/showpost.php?p=154644&postcount=148[/url]).

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. :smile:

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.

mklasson 2009-03-20 00:34

Well then, get [url=http://mklasson.com/aliquot.php]aliqueit v1.02[/url].

+ 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 < <hide_output_limit> digits. Unwanted output is redirected to <null_device>.

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[/code] 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[/code] 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
[/code]
Performance on these small numbers is still pretty irrelevant imho, but hooray! :smile:


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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.