mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2009-03-18, 14:15   #12
mklasson
 
Feb 2004

10216 Posts
Default

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
mklasson is offline   Reply With Quote
Old 2009-03-18, 14:50   #13
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×32×7×13 Posts
Default

Quote:
Originally Posted by mklasson View Post
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 View Post
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 View Post
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
File Type: txt aliqueit-mod.txt (19.5 KB, 318 views)

Last fiddled with by bsquared on 2009-03-18 at 14:51 Reason: added attachment
bsquared is offline   Reply With Quote
Old 2009-03-18, 16:14   #14
KriZp
 
KriZp's Avatar
 
Feb 2007

2078 Posts
Default

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.
KriZp is offline   Reply With Quote
Old 2009-03-18, 16:56   #15
mklasson
 
Feb 2004

1000000102 Posts
Default

Quote:
Originally Posted by KriZp View Post
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.
mklasson is offline   Reply With Quote
Old 2009-03-18, 18:01   #16
KriZp
 
KriZp's Avatar
 
Feb 2007

33·5 Posts
Default

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.
KriZp is offline   Reply With Quote
Old 2009-03-19, 01:33   #17
mklasson
 
Feb 2004

1000000102 Posts
Default

Quote:
Originally Posted by bsquared View Post
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?
mklasson is offline   Reply With Quote
Old 2009-03-19, 04:45   #18
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×32×7×13 Posts
Default

Quote:
Originally Posted by mklasson View Post
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.
bsquared is offline   Reply With Quote
Old 2009-03-19, 08:14   #19
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Quote:
Originally Posted by mklasson View Post
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.
10metreh is offline   Reply With Quote
Old 2009-03-19, 19:12   #20
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

569610 Posts
Default

Quote:
Originally Posted by 10metreh View Post
What about 2/7*N? That's what I use.
that was what i was told at some point as well
henryzz is offline   Reply With Quote
Old 2009-03-19, 20:36   #21
mklasson
 
Feb 2004

2×3×43 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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.
mklasson is offline   Reply With Quote
Old 2009-03-20, 00:34   #22
mklasson
 
Feb 2004

2·3·43 Posts
Default

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 < <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
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!
mklasson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Resuming aliqueit johnadam74 Aliquot Sequences 4 2016-03-28 12:32
Apparent aliqueit issue with specifying factors pakaran Aliquot Sequences 2 2015-09-12 23:10
Using Several Instances of Aliqueit for a large gnfs job EdH Aliquot Sequences 6 2011-12-13 18:58
Setting up aliqueit science_man_88 Aliquot Sequences 185 2011-11-08 12:18
Tried out aliqueit.exe: ggnfs failing 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

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