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)

bsquared 2009-03-17 14:31

Aliqueit.exe discussion
 
[quote=mklasson;165739]I've made a little home for aliqueit as well that will always have the latest version: [URL]http://mklasson.com/aliquot.php[/URL] (similar to the ubasic program except it's C++ and created this millenium :razz:)[/quote]

Thanks, this is working good for me. Good enough that I might consider doing some work on these fancy aliquot-thingamagigs.

I had actually started to code an aliquot sequence, err, computer, in YAFU because I refused to work with the UBASIC thing. But I can abandon that now. If anyone wants a chuckle, try running aliquot(N) in yafu, where N is the starting number. Its an undocumented feature, which will become an undocumented non-feature in the next version. It uses only yafu routines, so will start to choke around 95+ digits, can't parse anything, so can only start from scratch, and doesn't output anything useful either. And may produce bad results... heh... told you it's only good for a laugh.

- ben.

bsquared 2009-03-17 16:25

[quote=bsquared;165756]told you it's only good for a laugh.

- ben.[/quote]

It is faster though, for the starting values. Just (re)did the first 1225 iterations of 10212 in less than 2 minutes. But all the sequences are already past that point anyway, right?

p.s.
feel free to delete this and the preceeding posts - they are just clutter.

mklasson 2009-03-17 22:54

[QUOTE=bsquared;165772]It is faster though, for the starting values. Just (re)did the first 1225 iterations of 10212 in less than 2 minutes.[/QUOTE]

Aliqueit could probably gain a good bit of overall speed from better ecm limits for all sizes of inputs. The current limits are basically a few half-decent guesses extrapolated to increasingly worse guesses.

I considered emulating the behaviour of aliquot.ub, but as that source code says "These are VERY wild guesses" I'm not sure that would be much better. :smile:

I don't know how optimal msieve's choices are. Maybe approximating that behaviour is a better start. Anyone with more knowledge of the matter care to chime in?

bsquared 2009-03-18 03:14

[quote=mklasson;165817]Aliqueit could probably gain a good bit of overall speed from better ecm limits for all sizes of inputs. The current limits are basically a few half-decent guesses extrapolated to increasingly worse guesses. I don't know how optimal msieve's choices are. Maybe approximating that behaviour is a better start. Anyone with more knowledge of the matter care to chime in?

[/quote]
For smaller inputs, say less than 50 or 60 digits you could try just using msieve/yafu more. Msieve has good ecm choices for getting rid of small factors as does yafu, and the QS routines will quickly take care of the rest. For anything less than 60 digits you shouldn't be doing much ecm at all, IMO, assuming you first do trial division and pollard rho for a few hundred milliseconds. In yafu use the 'factor' function to automatically do this or something more customizable like siqs(rho(trial(N))).

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.

In between 60 and 85 some ecm would be good to do. You may be able to get away with just calling msieve and letting it deal with the ecm'ing, but that assumes the user's msieve has that capability which it may not if home-built. Yafu's ecm is probably sufficiently slower at this point that gmp-ecm would be a good idea before QS.

Anyway, my $0.02.

- ben.

henryzz 2009-03-18 07:34

[quote=mklasson;165817]Aliqueit could probably gain a good bit of overall speed from better ecm limits for all sizes of inputs. The current limits are basically a few half-decent guesses extrapolated to increasingly worse guesses.

I considered emulating the behaviour of aliquot.ub, but as that source code says "These are VERY wild guesses" I'm not sure that would be much better. :smile:

I don't know how optimal msieve's choices are. Maybe approximating that behaviour is a better start. Anyone with more knowledge of the matter care to chime in?[/quote]
what version of aliquot.ub are you using?

mklasson 2009-03-18 11:22

[QUOTE=bsquared;165836]Anyway, my $0.02.[/QUOTE]

A bankable $0.02. :)

[QUOTE=henryzz;165853]what version of aliquot.ub are you using?[/QUOTE]

None at all. I tried it once but the bundled interpreter complained about 64-bit windows and refused to start. That quote was from v1.25 though (from Sander's site).

bsquared 2009-03-18 13:33

[quote=mklasson;165739]I've made a little home for aliqueit as well that will always have the latest version: [URL]http://mklasson.com/aliquot.php[/URL] (similar to the ubasic program except it's C++ and created this millenium :razz:)[/quote]

I'm having some trouble compiling this under linux. Is that supported at all? I would also not rule out me doing something stoopid during compiling, as I haven't used c++ much.

[CODE]
[EMAIL="buhrow@barista:~/aliquot$"]buhrow@barista:~/aliquot$[/EMAIL] g++ aliqueit.cc -l /user/buhrow/gmp/install4.2.3/lib/libgmp.a
aliqueit.cc:14:20: error: direct.h: No such file or directory
aliqueit.cc:109: error: âmpz_classâ was not declared in this scope
aliqueit.cc:109: error: template argument 1 is invalid
aliqueit.cc:109: error: template argument 3 is invalid
aliqueit.cc:109: error: template argument 4 is invalid
aliqueit.cc:109: error: invalid type in declaration before â;â token
aliqueit.cc:112: error: variable or field âfactorâ declared void
aliqueit.cc:112: error: âmpz_classâ was not declared in this scope
aliqueit.cc:112: error: âmpz_classâ was not declared in this scope
aliqueit.cc:112: error: template argument 1 is invalid
aliqueit.cc:112: error: template argument 1 is invalid
aliqueit.cc:112: error: template argument 2 is invalid
aliqueit.cc:112: error: âfactorsâ was not declared in this scope
aliqueit.cc:112: error: âmpz_classâ was not declared in this scope
aliqueit.cc:112: error: template argument 1 is invalid
aliqueit.cc:112: error: template argument 2 is invalid
aliqueit.cc:112: error: ânew_factorsâ was not declared in this scope
aliqueit.cc:112: error: expected primary-expression before âboolâ
aliqueit.cc:128: error: âmpz_classâ has not been declared
aliqueit.cc: In function âvoid add_and_check_cycle(unsigned int, int&)â:
aliqueit.cc:129: error: request for member âcountâ in âseq_valuesâ, which is of non-class type âintâ
aliqueit.cc:130: error: invalid types âint[int]â for array subscript
aliqueit.cc:133: error: invalid types âint[int]â for array subscript
aliqueit.cc: In function âvoid precalc_trial_primes()â:
aliqueit.cc:138: error: âmpz_classâ was not declared in this scope
aliqueit.cc:138: error: expected `;' before âpâ
aliqueit.cc:139: error: âpâ was not declared in this scope
aliqueit.cc: At global scope:
aliqueit.cc:272: error: âmpz_classâ was not declared in this scope
aliqueit.cc:272: error: template argument 1 is invalid
aliqueit.cc:272: error: template argument 2 is invalid
aliqueit.cc: In function âint find_log_factors(std::string, std::string, std::string, std::string, int&)â:
aliqueit.cc:285: error: request for member âpush_backâ in âfactorsâ, which is of non-class type âintâ
aliqueit.cc:285: error: âmpz_classâ was not declared in this scope
aliqueit.cc: At global scope:
aliqueit.cc:298: error: âmpz_classâ was not declared in this scope
aliqueit.cc:298: error: template argument 1 is invalid
aliqueit.cc:298: error: template argument 1 is invalid
aliqueit.cc:298: error: template argument 2 is invalid
aliqueit.cc: In function âvoid merge_factors(int&)â:
aliqueit.cc:299: error: request for member âbeginâ in âfactorsâ, which is of non-class type âintâ
aliqueit.cc:299: error: request for member âendâ in âfactorsâ, which is of non-class type âintâ
aliqueit.cc:300: error: request for member âsizeâ in âfactorsâ, which is of non-class type âintâ
aliqueit.cc:301: error: invalid types âint[size_t]â for array subscript
aliqueit.cc:301: error: invalid types âint[long unsigned int]â for array subscript
aliqueit.cc:302: error: invalid types âint[long unsigned int]â for array subscript
aliqueit.cc:302: error: invalid types âint[size_t]â for array subscript
aliqueit.cc:303: error: request for member âeraseâ in âfactorsâ, which is of non-class type âintâ
aliqueit.cc:303: error: request for member âbeginâ in âfactorsâ, which is of non-class type âintâ
aliqueit.cc: At global scope:
aliqueit.cc:310: error: âmpz_classâ was not declared in this scope
aliqueit.cc:310: error: template argument 1 is invalid
aliqueit.cc:310: error: template argument 2 is invalid
aliqueit.cc: In function âint run_ecm(std::string, int&)â:
aliqueit.cc:311: error: â_unlinkâ was not declared in this scope
aliqueit.cc: At global scope:
aliqueit.cc:331: error: âmpz_classâ was not declared in this scope
aliqueit.cc:331: error: template argument 1 is invalid
aliqueit.cc:331: error: template argument 2 is invalid
aliqueit.cc: In function âint run_yafu(std::string, std::string, int&)â:
aliqueit.cc:332: error: â_unlinkâ was not declared in this scope
aliqueit.cc: At global scope:
aliqueit.cc:341: error: âmpz_classâ was not declared in this scope
aliqueit.cc:341: error: template argument 1 is invalid
aliqueit.cc:341: error: template argument 2 is invalid
aliqueit.cc: In function âint run_msieve(std::string, int&)â:
aliqueit.cc:342: error: â_unlinkâ was not declared in this scope
aliqueit.cc: At global scope:
aliqueit.cc:351: error: âmpz_classâ was not declared in this scope
aliqueit.cc:351: error: template argument 1 is invalid
aliqueit.cc:351: error: template argument 2 is invalid
aliqueit.cc: In function âint run_ggnfs(std::string, int&)â:
aliqueit.cc:354: error: â_chdirâ was not declared in this scope
aliqueit.cc: At global scope:
aliqueit.cc:373: error: variable or field âfound_factorâ declared void
aliqueit.cc:373: error: âmpz_classâ was not declared in this scope
aliqueit.cc:373: error: âfactorâ was not declared in this scope
aliqueit.cc:373: error: âmpz_classâ was not declared in this scope
aliqueit.cc:373: error: template argument 1 is invalid
aliqueit.cc:373: error: template argument 1 is invalid
aliqueit.cc:373: error: template argument 2 is invalid
aliqueit.cc:373: error: âfactorsâ was not declared in this scope
aliqueit.cc:379: error: variable or field âadd_factorsâ declared void
aliqueit.cc:379: error: âmpz_classâ was not declared in this scope
aliqueit.cc:379: error: ânâ was not declared in this scope
aliqueit.cc:379: error: âmpz_classâ was not declared in this scope
aliqueit.cc:379: error: template argument 1 is invalid
aliqueit.cc:379: error: template argument 1 is invalid
aliqueit.cc:379: error: template argument 2 is invalid
aliqueit.cc:379: error: âfactorsâ was not declared in this scope
aliqueit.cc:379: error: âmpz_classâ was not declared in this scope
aliqueit.cc:379: error: template argument 1 is invalid
aliqueit.cc:379: error: template argument 2 is invalid
aliqueit.cc:379: error: ânew_factorsâ was not declared in this scope
[/CODE]

Maybe this is helpful to know:
[CODE]
[EMAIL="buhrow@barista:~/aliquot$"]buhrow@barista:~/aliquot$[/EMAIL] g++ -v
Using built-in specs.
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr --enable-shared --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --enable-nls --with-gxx-include-dir=/usr/include/c++/4.2 --program-suffix=-4.2 --enable-clocale=gnu --enable-libstdcxx-debug --enable-objc-gc --enable-mpfr --disable-libmudflap --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.2.3 (Debian 4.2.3-5)
[/CODE]

mklasson 2009-03-18 13:41

[QUOTE=bsquared;165873]I'm having some trouble compiling this under linux. Is that supported at all?[/QUOTE]

I haven't tried it, but there's no reason it shouldn't work.

I'm using GMP's C++ class mpz_class, so try including gmpxx.lib. It's strangely not needed when compiling with MSVC though (gmp.lib is sufficient).

bsquared 2009-03-18 13:50

ok, that helped. But it still can't find direct.h for the file manipulation stuff.

[code]
buhrow@barista:~/aliquot$ g++ aliqueit.cc -I /user/buhrow/gmp/gmp-4.2.3/ -l /user/buhrow/gmp/install4.2.3/lib/libgmp.a
aliqueit.cc:14:20: error: direct.h: No such file or directory
aliqueit.cc: In function âint run_ecm(std::string, std::vector<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, std::allocator<__gmp_expr<__mpz_struct [1], __mpz_struct [1]> > >&)â:
aliqueit.cc:311: error: â_unlinkâ was not declared in this scope
aliqueit.cc: In function âint run_yafu(std::string, std::string, std::vector<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, std::allocator<__gmp_expr<__mpz_struct [1], __mpz_struct [1]> > >&)â:
aliqueit.cc:332: error: â_unlinkâ was not declared in this scope
aliqueit.cc: In function âint run_msieve(std::string, std::vector<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, std::allocator<__gmp_expr<__mpz_struct [1], __mpz_struct [1]> > >&)â:
aliqueit.cc:342: error: â_unlinkâ was not declared in this scope
aliqueit.cc: In function âint run_ggnfs(std::string, std::vector<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, std::allocator<__gmp_expr<__mpz_struct [1], __mpz_struct [1]> > >&)â:
aliqueit.cc:354: error: â_chdirâ was not declared in this scope
aliqueit.cc: In function âvoid factor(mpz_class, std::vector<std::pair<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, int>, std::allocator<std::pair<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, int> > >&, std::vector<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, std::allocator<__gmp_expr<__mpz_struct [1], __mpz_struct [1]> > >&, bool)â:
aliqueit.cc:408: error: invalid initialization of non-const reference of type âmpz_class&â from a temporary of type âmpz_classâ
aliqueit.cc:373: error: in passing argument 1 of âvoid found_factor(mpz_class&, std::vector<std::pair<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, int>, std::allocator<std::pair<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, int> > >&)â
[/code]

Edit:
Ahhh, that's because it's a MS specific header file. I'll see if there's a linux substitute.

mklasson 2009-03-18 13:57

Yeah, appears to be ms-specific. unistd.h -> unlink() and chdir() for linux.

bsquared 2009-03-18 14:05

[quote=mklasson;165877]Yeah, appears to be ms-specific. unistd.h -> unlink() and chdir() for linux.[/quote]

yep. A couple of #ifdef's and that problem is gone. Here's the last hurdle:

[CODE]
[EMAIL="buhrow@barista:~/aliquot$"]buhrow@barista:~/aliquot$[/EMAIL] g++ aliqueit.cc -I /user/buhrow/gmp/gmp-4.2.3/ -l /user/buhrow/gmp/install4.2.3/lib/libgmp.a
aliqueit.cc: In function âvoid factor(mpz_class, std::vector<std::pair<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, int>, std::allocator<std::pair<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, int> > >&, std::vector<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, std::allocator<__gmp_expr<__mpz_struct [1], __mpz_struct [1]> > >&, bool)â:
aliqueit.cc:433: error: invalid initialization of non-const reference of type âmpz_class&â from a temporary of type âmpz_classâ
aliqueit.cc:398: error: in passing argument 1 of âvoid found_factor(mpz_class&, std::vector<std::pair<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, int>, std::allocator<std::pair<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>, int> > >&)â
[/CODE]

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:

bsquared 2009-03-20 02:21

[quote=mklasson;166040] Well then, get [URL="http://mklasson.com/aliquot.php"]aliqueit v1.02[/URL].


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.

[/quote]

Yep, works fine for me.

[quote=mklasson;166040]
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.

[/quote]
These look like decent relationships, nice work! What external (i.e. non-yafu) ecm work is done for < 70 digits? I could parse the .ini, I guess, but I'm lazy tonight.

[quote=mklasson;166040]
To test the performance on smaller numbers I ran the Ben-chmark of doing the first 1225 lines of sequence 10212:
[/quote]

:cool:

bsquared 2009-03-20 02:33

[quote=mklasson;166040]Well then, get [URL="http://mklasson.com/aliquot.php"]aliqueit v1.02[/URL].
[/quote]

If you don't have access to a linux system then maybe you can't do anything about this, but I have one request. When I try to kill aliqueit when it's running via cntl-c it instead kills the program (yafu/msieve/ecm) that is running at that moment, and aliqueit immediately continues on and launches another factorization. So I have to cntl-z to the background, ps for the process IDs, kill the factorization job, then kill aliqueit, then fg aliqueit. Quite a process to stop the thing from running. Is there a way for aliqueit to intercept the cntl-c and stop it's execution instead?

mklasson 2009-03-20 02:44

[QUOTE=bsquared;166046]Yep, works fine for me.

These look like decent relationships, nice work! What external (i.e. non-yafu) ecm work is done for < 70 digits? I could parse the .ini, I guess, but I'm lazy tonight.[/QUOTE]

Goody, thanks.

[code]
digits #curves
45 10
50 15
55 20
60 30
65 40
[/code]
Starting with B1=1 and auto-incremented using "ecm -I 1". Starting a little higher than 1 could probably shave another ms off the time. :smile:

[QUOTE=bsquared;166050]Is there a way for aliqueit to intercept the cntl-c and stop it's execution instead?[/QUOTE]

Alas, I have no idea about that. It's been a long time since I did any linux coding...

smh 2009-03-21 08:45

Can i make one more request?

I would like to be able to skip the ecm stage when i resume a sequence and straight away start with yafu or msieve.

I have composites that have quite a bit of ecm done on them already and searching for 25 or 30 digit factors wouldn't make sense.

Of course i could crack the composite first, but that way i won't be able to run the sequence unatended over night.

mdettweiler 2009-03-21 10:50

[quote=smh;166167]Can i make one more request?

I would like to be able to skip the ecm stage when i resume a sequence and straight away start with yafu or msieve.

I have composites that have quite a bit of ecm done on them already and searching for 25 or 30 digit factors wouldn't make sense.

Of course i could crack the composite first, but that way i won't be able to run the sequence unatended over night.[/quote]
Open Task Manager and kill the ECM process (or, use pgrep/pkill under Linux); aliqueit will see that ECM has ended, find no factors in the log, and proceed on (either to QS, or to the next stage of ECM). If more stages of ECM are considered necessary by aliqueit, you'll need to kill those, too, but once you've gotten to the last one (should be only two or three at maximum most of the time) it will then consider ECM done and progress on to Yafu/msieve for QS. :smile:

mklasson 2009-03-21 12:53

[QUOTE=smh;166167]Can i make one more request?[/quote]

Please do, I'm happy to hear it.

[QUOTE=mdettweiler;166175]Open Task Manager and kill the ECM process (or, use pgrep/pkill under Linux)[/QUOTE]

Yeah, this is what I've been doing as well. Is that ok for you Sander? I could add a switch to do what you want but the code would be kinda ugly.

I often stop when I see a ggnfs-pol51 running, "manually" find a better poly with msieve instead, and then restart. I would like to use msieve-polyfind in the automation instead but it's currently crashing too often for me to be usable unattended. :down:

Aah, I'll just add the switch anyway... Saves a few seconds manual labor. :smile:

Here you go: [url=http://mklasson.com/aliquot.php]aliqueit v1.03[/url].

+ cmdline arg "-e" skips ecm on the current iteration and goes straight to qs/gnfs. Further iterations use ecm normally.

+ prints and logs a cheerful msg if an ecm factor >= <neat_factor_limit_ecm> digits is found.

+ prints the size of the composite we're currently processing.

* scientifies printed B1 values. 1000000 -> 1e6.

* fixed a potential bug where we'd ecm forever ("ecm -c 0") or until we found a factor. It never actually happened, but it could have if the ecm level formulas had looked different.

* changed the default <big_ecm_cutoff> to 65 instead of 70. This results in a little more ecm being done for c65-c69.

smh 2009-03-21 17:48

[QUOTE=mdettweiler]Open Task Manager and kill the ECM process (or, use pgrep/pkill under Linux)[/quote]Thanks, i never thought of that.
[QUOTE=mklasson;166180]Yeah, this is what I've been doing as well. Is that ok for you Sander? I could add a switch to do what you want but the code would be kinda ugly.[/QUOTE]This would be fine for me.[QUOTE=mklasson;166180]Aah, I'll just add the switch anyway... Saves a few seconds manual labor. :smile:[/quote]Even better, thanks.[QUOTE=mklasson;166180]
+ prints the size of the composite we're currently processing.[/quote]Thanks, this is helpful.

10metreh 2009-03-22 07:39

I think aliqueit's ECM limits need improving. I am currently working on a C93 from iteration 1985 of sequence 130396, and before starting msieve, aliqueit proceeded to do a full t30 and then 73 curves at 1M!

1. A full t30 is not needed on a C93.
2. (This is a new one) If ECM needs to be run to 32.5 digits, that does not mean that you have to run half t35. I would guess about 1/3 t35 would be better.

smh 2009-03-22 09:39

OK, one more request. Not that important, just to make our live a little easier ;-)

The aliqueit.log contains all ecm curves. This makes the log quite big and information is hard to find. Would it be possible to just print something like [CODE]
"c103: ran 430 ecm curves at B1=25e4..."
"c103: ran 651 ecm curves at B1=1e6..."[/CODE]

mklasson 2009-03-22 14:02

[QUOTE=10metreh;166238]1. A full t30 is not needed on a C93.[/quote]

On what do you base this and what would you prefer instead? I'm not saying you're wrong, it's just that if you want to spend about 1/4 of the qs time on ecm that's roughly the amount of ecm you'll have to do. Again, I'm not sure if 1/4 time is the best figure but it seems decent enough and I have yet to find some solid justification for any specific amount. Please show me the light of reason if you're hoarding it.

[QUOTE=10metreh;166238]2. (This is a new one) If ECM needs to be run to 32.5 digits, that does not mean that you have to run half t35. I would guess about 1/3 t35 would be better.[/QUOTE]

Good point. The estimates (and reasoning behind them) are rough enough that I don't really think it matters though. I certainly don't know whether it's best to spend 1/3, 1/4, or 1/5 of the qs time ecming a c93 for example. Furthermore, the way I get the factor digit estimate in the first place is via linear inter-/extrapolation from appropriate [b]factor sizes[/b] at c70 and c95. What I really want is appropriate [b]time[/b] scaling though, with the time approximately doubling for every 3 input digits (for qs). The way the ecm table is set up with progressively harder and more curves for each digit level converts the linear factor size limits into something resembling exponential time limits.

The net effect of all this is definitely not the perfect scaling sought, and you're right, removing the linearity between 30 and 35 would be good. I think ultimately the whole linear scaling of factor size needs to go though, and be replaced with proper time scaling and data for how long a curve takes for a given B1 and input size. But maybe this is overkill given that I still don't know whether ecm_time/qs_time = 1/4 is a fundamentally good idea. :smile:

mklasson 2009-03-22 14:16

[QUOTE=smh;166245]OK, one more request. Not that important, just to make our live a little easier ;-)

The aliqueit.log contains all ecm curves. This makes the log quite big and information is hard to find. Would it be possible to just print something like [CODE]
"c103: ran 430 ecm curves at B1=25e4..."
"c103: ran 651 ecm curves at B1=1e6..."[/CODE][/QUOTE]

I know what you mean... The reason I want the ecm logs saved is I'm naively hoping to get lucky and find a humongous ecm record factor. :lol: It would be a shame to not have the sigma saved when that happens.

I could skip saving the ecm log if no factor was found though, and only print a line like you suggested. That'd cut down heavily on the spam. Sounds like a good compromise, and very easy to implement.

smh 2009-03-22 14:40

Or just print the lucky curve if a factor is found

mklasson 2009-03-22 14:50

[QUOTE=smh;166265]Or just print the lucky curve if a factor is found[/QUOTE]

Arrr, and here I thought I could get away cheap... :smile: But yeah, it would be cleaner. I'll think about it.

10metreh 2009-03-22 15:37

[quote=mklasson;166259]On what do you base this and what would you prefer instead? I'm not saying you're wrong, it's just that if you want to spend about 1/4 of the qs time on ecm that's roughly the amount of ecm you'll have to do. Again, I'm not sure if 1/4 time is the best figure but it seems decent enough and I have yet to find some solid justification for any specific amount. Please show me the light of reason if you're hoarding it.[/quote]

The most I would possibly run on a C93 is t30. t30 + 73 @ 35 digits is too much. On my incredibly slow computer, a t30 on a C93 takes 51 minutes. 73 curves at 1e6 takes another 35 minutes. That's 86 minutes. And that's a lot.

mklasson 2009-03-22 16:07

[QUOTE=10metreh;166268]The most I would possibly run on a C93 is t30. t30 + 73 @ 35 digits is too much. On my incredibly slow computer, a t30 on a C93 takes 51 minutes. 73 curves at 1e6 takes another 35 minutes. That's 86 minutes. And that's a lot.[/QUOTE]

But do you have any reasoning, math, or experimental data that supports your conclusion of "too much"? Like I said, I'm aiming for roughly a fourth of the qs time spent ecming. Can you explain [b]why[/b] that is too much? I'd be very happy to hear it, but just saying that you think it's "too much" and "a lot" doesn't really help me much I'm afraid. :mellow:

10metreh 2009-03-22 16:13

[quote=mklasson;166270]But do you have any reasoning, math, or experimental data that supports your conclusion of "too much"? Like I said, I'm aiming for roughly a fourth of the qs time spent ecming. Can you explain [B]why[/B] that is too much? I'd be very happy to hear it, but just saying that you think it's "too much" and "a lot" doesn't really help me much I'm afraid. :mellow:[/quote]

Sorry. BTW, do you know what a more common term for "a fourth" is? [COLOR=white]A quarter.[/COLOR]

Feature request for aliqueit: store the known factors of the iteration being worked on in a file and immediately check the file for them as soon as you resume, so you don't have to go searching for the factors in aliqueit.log when you want to resume.

mklasson 2009-03-22 16:34

[QUOTE=10metreh;166271]Sorry. BTW, do you know what a more common term for "a fourth" is? [COLOR=white]A quarter.[/COLOR][/quote]

:lol: uh, yes? Yes, yes, I do! If you look carefully you'll see I have in fact already used the magic word in this very thread! :shock: Was there a particular reason you said that? Am I missing out on a joke or something here?

[QUOTE=10metreh;166271]Feature request for aliqueit: store the known factors of the iteration being worked on in a file and immediately check the file for them as soon as you resume, so you don't have to go searching for the factors in aliqueit.log when you want to resume.[/QUOTE]

You rarely have a big enough factor in the middle of an iteration that it's worth the bother saving and restoring it though. But sure, it would be neat. I'll think about it.

10metreh 2009-03-22 16:47

[quote=mklasson;166274]You rarely have a big enough factor in the middle of an iteration that it's worth the bother saving and restoring it though. But sure, it would be neat. I'll think about it.[/quote]

The other thing involves the -e option. If you use -e, you have to put the factor(s) in the command line if they are larger than the trial factoring cutoff. For instance, with my current iteration of 130396, there was a C99 which had a P7 factor, leaving a C93 which I am sieving at this very moment. However, when I started aliqueit with "aliqueit 130396 -e", it went off into a GNFS on the C99 without finding the P7. So I had to run "aliqueit 130396 -f 3373717 -e" instead, after finding the factor in aliqueit.log buried under full t20, t25 and t30 runs.

mklasson 2009-03-22 16:50

[QUOTE=mklasson;166274]You rarely have a big enough factor in the middle of an iteration that it's worth the bother saving and restoring it though. But sure, it would be neat. I'll think about it.[/QUOTE]

Hmm... except if you're restarting with "-e" and skipping ecm altogether of course. It would be a great shame to run gnfs on a c120 instead of a c110...

10metreh 2009-03-22 16:52

[quote=mklasson;166279]Hmm... except if you're restarting with "-e" and skipping ecm altogether of course. It would be a great shame to run gnfs on a c120 instead of a c110...[/quote]

...when a P10 is lurking within. Of course, msieve would find the factor during the run, so it wouldn't be a GNFS at all if you used msieve for the poly search, and wouldn't be a complete GNFS unless you used factLat.pl.

P.S. Look at my post count!

mklasson 2009-03-22 17:04

No joke then? :cry:

[QUOTE=10metreh;166277]...buried under full t20, t25 and t30 runs.[/QUOTE]

Very subtle. :lol:

Fortunately you'll at least have much less dirt to paw your way through in the next version. I'll see about doing something nicer.

10metreh 2009-03-22 17:12

[quote=mklasson;166281]No joke then? :cry:[/quote]

Yes joke, actually (I apologise about my deliberately poor English). I just forgot!

And I'm moving out of beastly territory now. Change to location field needed!

mklasson 2009-03-22 20:50

[QUOTE=10metreh;166282]Yes joke, actually (I apologise about my deliberately poor English). I just forgot![/quote]

Regardless, here's a new [url=http://mklasson.com/aliquot.php]aliqueit v1.04[/url].

Btw, if you can compile the code it's an easy change to make it do less ecm if you really don't like the current situation. If more people feel the same way I can add some sort of config setting for it as well. If they could also explain why they feel it's too much then maybe I could make the defaults better for all. Given enough similar opinions I'll probably run with the herd even without an explanation.

Anyway:

+ also does P-1/P+1 in addition to ecm using the gmp-ecm recommended 10*B1 for P-1 and 3x 5*B1 for P+1.

+ only saves relevant parts of the ecm log, or nothing at all if no factor was found.

+ logs "*** c<digits> = <factor>" for found composite factors.

+ scans through the last 100KB of the log file when starting up and uses all relevant factors it finds. Makes restarting easier as you no longer need to manually specify factors with "-f" if you found them with the latest aliqueit run.

Phil MjX 2009-03-23 22:49

Hello !

I have tried aliqueit with the sequence I am dealing with (5400 at index 3022) but I encountered a crash when verifying it :

at index 2924, the program does crash with Win XP !

I have been checking this problem with two machines : a Pentium M and a Core duo laptop.

I have checked the 2924th step and it is ok when processing alone

I have also tried with the 13200 sequence (that is the 5400 minus one step) and the program still crash at index 2924 (that is the 2925th of the 5400 sequence)...

Is this a bug :smile: ?

Kind regards !

mklasson 2009-03-23 23:30

[QUOTE=Phil MjX;166421]Hello !

I have tried aliqueit with the sequence I am dealing with (5400 at index 3022) but I encountered a crash when verifying it :

at index 2924, the program does crash with Win XP !

I have been checking this problem with two machines : a Pentium M and a Core duo laptop.

I have checked the 2924th step and it is ok when processing alone

I have also tried with the 13200 sequence (that is the 5400 minus one step) and the program still crash at index 2924 (that is the 2925th of the 5400 sequence)...

Is this a bug :smile: ?

Kind regards ![/QUOTE]

Well, it sure isn't a feature. :smile:

Sounds very odd though. You're basically saying it always crashes at index 2924 for you regardless of sequence? Could you send me the elf file or attach it here? I just tried a sequence with 2931 lines (biggest I could find) without any problems.

mdettweiler 2009-03-24 06:30

I've been using aliqueit on Linux since version 1.01 and am, overall, quite happy with it. However, there are a couple of feature requests that I personally would find quite useful, if they aren't too hard to implement:

-I generally prefer to set aliqueit to do TF up to 1e8 instead of the default 1e4. However, the primary downside of this is that aliqueit takes quite some time to precalculate all the primes for TF when it first starts up. It's still only a couple of minutes, but nonetheless it got me thinking: would it possibly be faster to have aliqueit write its precalculated primes to disk after it calculates them, and then load them from that file upon all subsequent startups?

-When the program is first started, it prints to screen the full initial composite of the current line, and the number of digits it contains. Would it be possible to have it do this for all lines, not just the first one? That would make it a little easier to track how much a sequence has grown/shrunk since the program was started.

Thanks,
Max :smile:

axn 2009-03-24 08:11

[QUOTE=mdettweiler;166444]I generally prefer to set aliqueit to do TF up to 1e8 instead of the default 1e4. However, the primary downside of this is that aliqueit takes quite some time to precalculate all the primes for TF when it first starts up. It's still only a couple of minutes[/QUOTE]
Calculating all primes up to 1e8 takes "couple of minutes"? That's just wrong! :smile:

Seriously... with an optimized implementation of SoE, it is faster to calculate the primes than reading them from disk.

mklasson 2009-03-24 11:08

[QUOTE=axn;166456]Calculating all primes up to 1e8 takes "couple of minutes"? That's just wrong! :smile:

Seriously... with an optimized implementation of SoE, it is faster to calculate the primes than reading them from disk.[/QUOTE]

I have put absolutely zero effort into the precalcing... It's just a loop with mpz_nextprime. With trial_cutoff = 1e4 it takes a couple of ms so it really hasn't seemed worth the bother. You've almost shamed me into doing something about it though. :lol:

There are several lazier options however. I could use gmp-ecm to do the trial factoring ("-t trial_cutoff"). Or, probably better, I could let yafu do a pollard rho right after the trial factoring. That would probably make a trial_cutoff of 1e8 really suboptimal and I could get away with not doing anything about the trial factoring. Yafu already does the rho, but after the ecm phase for bigger numbers which is presumably not optimal. Thoughts?

[QUOTE=mdettweiler;166444]-When the program is first started, it prints to screen the full initial composite of the current line, and the number of digits it contains. Would it be possible to have it do this for all lines, not just the first one? That would make it a little easier to track how much a sequence has grown/shrunk since the program was started.[/QUOTE]

Something like
[code]
1445 . c127 = 1684219780053232790182532264150037585657262227235724020539452224672674641583964846829593256612940760791424573187987177454181744 = 2^4 * ...
[/code]
on the screen? I could certainly do that.

bsquared 2009-03-24 13:18

[quote=mklasson;166475]I have put absolutely zero effort into the precalcing... It's just a loop with mpz_nextprime. With trial_cutoff = 1e4 it takes a couple of ms so it really hasn't seemed worth the bother. You've almost shamed me into doing something about it though. :lol:

There are several lazier options however. I could use gmp-ecm to do the trial factoring ("-t trial_cutoff"). Or, probably better, I could let yafu do a pollard rho right after the trial factoring. That would probably make a trial_cutoff of 1e8 really suboptimal and I could get away with not doing anything about the trial factoring. Yafu already does the rho, but after the ecm phase for bigger numbers which is presumably not optimal. Thoughts?


[/quote]

Yafu and gmp-ecm can both trial divide to user specified limits, but using those programs with high bounds would get expensive because the primes would need to be regenerated each time, even though it is fast. Yafu takes ~0.2 seconds to get all the primes up to 1e8.

That said, I definately don't think trial factoring to 1e8 is optimal. This is what Rho is for - it is supurb at pulling 6 to 9 digit factors in tens of milliseconds; much faster than you could do by trial division. I think Rho should be used right after trial division to low bounds (1e4).


- ben.

Phil MjX 2009-03-24 17:06

1 Attachment(s)
[QUOTE=mklasson;166425]Well, it sure isn't a feature. :smile:

Sounds very odd though. You're basically saying it always crashes at index 2924 for you regardless of sequence? Could you send me the elf file or attach it here? I just tried a sequence with 2931 lines (biggest I could find) without any problems.[/QUOTE]

For sure !

Kind Regards !

mklasson 2009-03-24 17:18

Ah, the problem is that the 2924 line has no space between "*" and the cofactor. Even so, it certainly isn't polite to crash...

Just add a space for now and it'll work ok.

Thanks!

mklasson 2009-03-24 17:33

[QUOTE=bsquared;166493]That said, I definately don't think trial factoring to 1e8 is optimal. This is what Rho is for - it is supurb at pulling 6 to 9 digit factors in tens of milliseconds; much faster than you could do by trial division. I think Rho should be used right after trial division to low bounds (1e4).[/QUOTE]

This sounds good to me. I tried doing a "yafu rho(n)" separately before the ecm phase but the overhead with log parsing and whatnot resulted in a pretty dissatisfying performance. I've put together an internal rho now though which saves some time (and gives me some fun :smile:).

Curiously, the original Floyd cycle finder yields better speed than the Brent version when I benchmark on real sequence data. "In the lab" Brent seems to perform significantly faster though... I've probably just overlooked something.

mdettweiler 2009-03-24 17:49

[quote=mklasson;166475]Something like
[code]
1445 . c127 = 1684219780053232790182532264150037585657262227235724020539452224672674641583964846829593256612940760791424573187987177454181744 = 2^4 * ...
[/code]on the screen? I could certainly do that.[/quote]
Perfect. :smile:

mklasson 2009-03-24 18:15

[QUOTE=mklasson;166521]Curiously, the original Floyd cycle finder yields better speed than the Brent version when I benchmark on real sequence data. "In the lab" Brent seems to perform significantly faster though... I've probably just overlooked something.[/QUOTE]

Too low iteration cap... Upping it to 6k gives Brent the upper hand in real life as well.

Doing the first 1225 lines of 10212 takes 48s now.

Incidentally, running the entire sequence for 840 (one of the original Lehmer Six) takes just 30 seconds. Isn't Moore's Law great? :lol:

10metreh 2009-03-24 18:18

[quote=mklasson;166533]Too low iteration cap... Upping it to 6k gives Brent the upper hand in real life as well.

Doing the first 1225 lines of 10212 takes 48s now.

Incidentally, running the entire sequence for 840 (one of the original Lehmer Six) takes just 30 seconds. Isn't Moore's Law great? :lol:[/quote]

If Moore's Law continues, sequence 840 will take 0.00002 seconds by 2050. :lol:

Phil MjX 2009-03-24 18:41

[QUOTE=mklasson;166519]Ah, the problem is that the 2924 line has no space between "*" and the cofactor. Even so, it certainly isn't polite to crash...

Just add a space for now and it'll work ok.

Thanks![/QUOTE]

Thanks a lot to you !
Politeness isn't a bug so all is OK :smile: !

mklasson 2009-03-24 18:57

[QUOTE=mklasson;166533]Incidentally, running the entire sequence for 840 (one of the original Lehmer Six) takes just 30 seconds. Isn't Moore's Law great? :lol:[/QUOTE]

Ack... I should've said "Dr Lehmer sure was impatient..." instead. What a lost opportunity! :lol:

[QUOTE=Phil MjX;166537]Thanks a lot to you !
Politeness isn't a bug so all is OK :smile: ![/QUOTE]

I was aiming for "Being buggy isn't polite", but I like your version as well. :smile:

hhh 2009-03-29 11:37

Can we please have the subordinated commands started at low priority? For the long jobs, I adjust it by hand, but that's no solution.

And could there be a switch to skip ecm for the first line? Like when you stop the program and restart it. Even better would be to keep track of the ecm done.

When I stop the program, restart, stop, restart, there are too many factors stored, which leads to "Warning, 2 is no factor." of so messages.

Finally, imagine aliqueit is working on some c100. after some ecm, a p20 is found, leaving a c80. Then, ecm starts over at zero, even if one would better continue directly at the 20 digit level.

For everything else: nice work, and thank you! H.

mklasson 2009-03-29 11:57

[QUOTE=hhh;167100]Can we please have the subordinated commands started at low priority? For the long jobs, I adjust it by hand, but that's no solution. [/quote]

I suppose I could, but it's very easy to do yourself with "start" or "nice" depending on your system. For windows, "start /b /low /wait aliqueit.exe 162126" starts aliqueit.exe [b]and all it's subprocesses[/b] with low priority.

[QUOTE=hhh;167100]And could there be a switch to skip ecm for the first line? Like when you stop the program and restart it. Even better would be to keep track of the ecm done.[/quote]

There already is. Sander beat you to it. :smile: Try "-e". Yeah, keeping track of work done would be neat.

[QUOTE=hhh;167100]When I stop the program, restart, stop, restart, there are too many factors stored, which leads to "Warning, 2 is no factor." of so messages.[/quote]

I know, it's bugged me a little too. All in all though, it's just a minor cosmetic thing.

[QUOTE=hhh;167100]Finally, imagine aliqueit is working on some c100. after some ecm, a p20 is found, leaving a c80. Then, ecm starts over at zero, even if one would better continue directly at the 20 digit level.[/quote]

Yeah... I should do something about that.

[QUOTE=hhh;167100]For everything else: nice work, and thank you! H.[/QUOTE]

Thanks for the kind words and your comments.

10metreh 2009-03-29 11:58

[quote=hhh;167100]Can we please have the subordinated commands started at low priority? For the long jobs, I adjust it by hand, but that's no solution.

And could there be a switch to skip ecm for the first line? Like when you stop the program and restart it. Even better would be to keep track of the ecm done.

When I stop the program, restart, stop, restart, there are too many factors stored, which leads to "Warning, 2 is no factor." of so messages.

Finally, imagine aliqueit is working on some c100. after some ecm, a p20 is found, leaving a c80. Then, ecm starts over at zero, even if one would better continue directly at the 20 digit level.

For everything else: nice work, and thank you! H.[/quote]

There is a switch to skip ecm for the first line, and it's -e. Also, I often don't want jobs started at low priority, so could there be a -n switch for low priority?

mklasson 2009-03-29 12:11

[QUOTE=10metreh;167106]There is a switch to skip ecm for the first line, and it's -e. Also, I often don't want jobs started at low priority, so could there be a -n switch for low priority?[/QUOTE]

Yeah, if I do implement it it'll be in the form of a switch.

mklasson 2009-03-29 18:30

Some improvements for now: [url=http://mklasson.com/aliquot.php]aliqueit v1.05[/url].

+ prints the size of the starting composite for each line.
+ runs pollard rho (internal) right after the trial factoring. Nice speedup for small numbers.
+ runs auto-increasing ecm forever instead of exiting if something goes wrong and ggnfs fails to find a factor.
+ detects some malformed elf files instead of crashing while verifying... Thanks Phil MjX.
+ "-h" prints a little help text on cmdline args.
+ logs cofactors explicitly.
+ the expressions used to determine maximum ecm level can now be customised with <qs_k>, <qs_m>, <gnfs_k>, and <gnfs_m>.
+ "-p" runs aliqueit and all spawned processes at idle priority.

I'm hoping it still compiles under linux. The priority code is ripped from a 5-year old proth_sieve, but I highly doubt it's become invalid since then.

Andi47 2009-03-30 04:30

Just a question (I have not yet tested it): Does aliqueit print some statistical data for GNFS to a logfile (siever used, how many relations needed, size of special Q range)?

mklasson 2009-03-30 10:43

[QUOTE=Andi47;167202]Just a question (I have not yet tested it): Does aliqueit print some statistical data for GNFS to a logfile (siever used, how many relations needed, size of special Q range)?[/QUOTE]

It creates a new directory for each ggnfs run, runs ggnfs, cleans up the work files afterwards, parses ggnfs.log to find the factors, and continues working on the next sequence line. So no, and yes. It doesn't write any of that stuff to aliqueit.log, but the original ggnfs.log and summary file is saved so you'll find the info there. You can also customise what files will be deleted upon completion so it's possible to save other files you may want as well.

Joshua2 2009-03-30 18:34

does aliquot use msieve for the final calculations, or for the initial polynomial selection? I have read that msieve is better at both those tasks.

mklasson 2009-03-30 18:42

[QUOTE=Joshua2;167301]does aliquot use msieve for the final calculations, or for the initial polynomial selection? I have read that msieve is better at both those tasks.[/QUOTE]

By default it's set up to use msieve for gnfs postprocessing, yeah. That's all done outside of aliqueit though. Just make sure aliqueit.ini->gnfs_cmd uses factMsieve.pl and it'll be alright.

Alas, no, it uses the polyfinder in ggnfs for now. I've considered letting msieve find a poly, but haven't implemented it yet.

Andi47 2009-03-30 19:27

[QUOTE=mklasson;167305]
Alas, no, it uses the polyfinder in ggnfs for now. I've considered letting msieve find a poly, but haven't implemented it yet.[/QUOTE]

Is it possible to start an ubasic program from the "DOS"-command line? In this case, the line calling facmsieve.pl could be (optionally!) replaced by a line calling my [URL="http://www.mersenneforum.org/showthread.php?t=11438"]Ubasic script for GNFS[/URL]*), which uses msieve for poly selection and postprocessing.

*) the script needs a worktodo.txt file to start. It needs renamed gnfs-lasieve4I1?e files too, see the documentation of gnfs.ub. I think the script still contains the line which copies msieve.log to msieve.old when it's finished, so the factors can be parsed out of the msieve.old file.

10metreh 2009-03-30 19:29

[quote=Andi47;167315]Is it possible to start an ubasic program from the "DOS"-command line? In this case, the line calling facmsieve.pl could be (optionally!) replaced by a line calling my [URL="http://www.mersenneforum.org/showthread.php?t=11438"]Ubasic script for GNFS[/URL]*, which uses msieve for poly selection and postprocessing.

(the script needs a worktodo.txt file to start. It needs renamed gnfs-lasieve4I1?e files too, see the documentation of gnfs.ub. I think the script still contains the line which copies msieve.log to msieve.old when it's finished, so the factors can be parsed out of the msieve.old file.)[/quote]

Personally, I think an option in the config file would be best for this, because gnfs.ub is susceptible to various odd ubasic bugs.

Joshua2 2009-03-30 19:32

I believe it doesn't work with vista x64 as well I heard, which it wouldn't if its 16bit.

Andi47 2009-03-30 19:38

[QUOTE=10metreh;167316]Personally, I think an option in the config file would be best for this, because gnfs.ub is susceptible to various odd ubasic bugs.[/QUOTE]

That's what I was thinking of when I was writing the word "optionally!".

P.S.: theoretically it should be possible to use gnfs.ub without a change in aliqueit.exe - for this a change in gnfs.ub would be necessary to output the factors in the same way as factmsieve.pl does, and to change the line in the .ini file to call gnfs.ub instead of factmsieve.pl.

mklasson 2009-03-30 19:44

[QUOTE=Andi47;167315]Is it possible to start an ubasic program from the "DOS"-command line? In this case, the line calling facmsieve.pl could be (optionally!) replaced by a line calling my [URL="http://www.mersenneforum.org/showthread.php?t=11438"]Ubasic script for GNFS[/URL]*), which uses msieve for poly selection and postprocessing.[/quote]

Beats me. But yeah, all aliqueit needs from the program run with gnfs_cmd is a ggnfs.log file afterwards with the factors presented in msieve or factLat.pl fashion. As input to gnfs_cmd aliqueit writes a test.n file containing "n: <composite>".

edit: oh, and it passes "test" as argument to gnfs_cmd.

Andi47 2009-03-30 19:57

[QUOTE=mklasson;167320]Beats me. But yeah, all aliqueit needs from the program run with gnfs_cmd is a ggnfs.log file afterwards with the factors presented in msieve or factLat.pl fashion. As input to gnfs_cmd aliqueit writes a test.n file containing "n: <composite>".[/QUOTE]

So I need to tell gnfs.ub that test.n is a valid input file. I will try to get it to run during my easter holiday.

Joshua2 2009-03-30 20:05

I could probably write a c# exe to run msieve and convert and make a proper .poly so gnfs can just run, would that help?
If aliquot used 1.40 instead of 1.38 would that speed things up much? Or maybe thats yafu's fault, but does it make much difference?

Andi47 2009-03-30 20:19

[QUOTE=Joshua2;167325]If aliquot used 1.40 instead of 1.38 would that speed things up much? Or maybe thats yafu's fault, but does it make much difference?[/QUOTE]

Using msieve 1.40 instead of anything older than msieve 1.39 would speed up GNFS *very much*, as msieve 1.39 and newer finds MUCH better polynomials than msieve 1.38 and older.

Joshua2 2009-03-30 20:20

I think I was referring to yafu using msieve 1.38 in post processing. Is that changed?

bsquared 2009-03-30 20:33

[quote=Joshua2;167327]I think I was referring to yafu using msieve 1.38 in post processing. Is that changed?[/quote]

It still uses 1.38. With QS (the only thing you care about in YAFU), it makes no difference.

mklasson 2009-03-30 20:34

[QUOTE=Joshua2;167325]I could probably write a c# exe to run msieve and convert and make a proper .poly so gnfs can just run, would that help?[/quote]

The main reason aliqueit doesn't already use msieve to find polys is that I've had msieve crash on me several times when poly-finding. Msieve's poly finding skills have thus been unfit for automated use. Having it crash and stall a core for half a day or so soon outweighs the benefits of finding a better poly when it does work ok.

I mostly tried poly-finding with msieve v1.40 beta 2 though. Hopefully those bugs have been ironed out by now.

Writing the actual code in aliqueit to have it use msieve for poly-finding should be fairly simple. If you do write the exe you mentioned though, you could simply set gnfs_cmd=yourexe and then start ggnfs yourself once you're done with the poly finding.

[QUOTE=Joshua2;167325]If aliquot used 1.40 instead of 1.38 would that speed things up much? Or maybe thats yafu's fault, but does it make much difference?[/QUOTE]

For the post processing the speedup, if any, probably isn't overwhelming but I don't know. Nevertheless, 1.40 is surely preferable to 1.38 anyway.

Andi47 2009-03-31 01:25

Where do I get a windows binary of cat.exe? (factmsieve.pl needs this.)

Edit: [URL="http://www.mersenneforum.org/showpost.php?p=119176&postcount=8"]found it[/URL]. Strange that the forum search didn't find it.

Joshua2 2009-03-31 03:38

So it sounds like me writing a little exe in c# wouldn't help aliquot. I found aliquot doing some repeating work. Probably fixing this would speed things up around 5%. It duplicates work after a factor is found. For example this is from my log:

Cofactor 7439342966178752447740164752385228998587835414831595841951784722555871730599705844073149722983572349 (100 digits)
c100: running rho..., P-1 at B1=11e4..., P+1 x3 at B1=55e3...,74 ecm curves at B1=11e3..., P-1 at B1=5e5..., P+1 x3 at B1=25e4..., 214 ecm curves at B1=5e4...
********** Factor found in step 2: 257719442509877978414047
*** prp24 = 257719442509877978414047
Cofactor 28866052532662972076403483527667476891502047008353645767926700119928657349667 (77 digits)

[I]c77: running rho...
c77: running P-1 at B1=11e4...
c77: running P+1 x3 at B1=55e3...
c77: running 74 ecm curves at B1=11e3...
c77: running P-1 at B1=5e5...
c77: running P+1 x3 at B1=25e4...
c77: running 138 ecm curves at B1=5e4...
[/I]
Italicized is duplicate work. Instead run higher ecm bounds or go straight to yafu. (I could be missing something too :)
c77: running qs (yafu)...

Joshua2 2009-03-31 04:22

It happened again when ecm found a factor in a 100+ number, but was still C96, and has to redo a lot of ecm work. The way to fix it is probably to have a boolean value that keeps track of whether ecm has been run, and if true, go straight to qs or gnfs. Alternatively would be to keep track of how many curves were run and finish the rest of the curves, which would probably not be any better.

10metreh 2009-03-31 06:40

[quote=Joshua2;167363]It happened again when ecm found a factor in a 100+ number, but was still C96, and has to redo a lot of ecm work. The way to fix it is probably to have a boolean value that keeps track of whether ecm has been run, and if true, go straight to qs or gnfs. Alternatively would be to keep track of how many curves were run and finish the rest of the curves, which would probably not be any better.[/quote]

I think the duplicated work problem only really occurs when you're working on stuff like C120s, you find a P30 factor after nearly completing t30, and it proceeds to run t30 again on the C91 that results. t25 only takes a few minutes, so the problem only starts happening when cofactors from t30 runs need (or rather don't need) t30 runs themselves.

smh 2009-03-31 08:13

Hi Mikael,

What files does aliqueit look for factors and in what format do i have to put the factors?

For example, i'm running aliqueit on a pc which can't run GNFS, so i just let it run more ECM but in the mean time i factor the number on a couple of other pc's with GNFS. I would like to put the factor in a file, kill ecm, yafu or msieve and let aliqueit automatically pick up the factor.

10metreh 2009-03-31 08:17

[quote=smh;167401]Hi Mikael,

What files does aliqueit look for factors and in what format do i have to put the factors?

For example, i'm running aliqueit on a pc which can't run GNFS, so i just let it run more ECM but in the mean time i factor the number on a couple of other pc's with GNFS. I would like to put the factor in a file, kill ecm, yafu or msieve and let aliqueit automatically pick up the factor.[/quote]

Kill aliqueit, and restart it with -f <the_factor>. You can use as many -f's as you like.

mklasson 2009-03-31 09:42

[QUOTE=Joshua2;167357]So it sounds like me writing a little exe in c# wouldn't help aliquot.[/quote]

Well, it would certainly help any person wanting to use msieve for poly-finding before I write that code in aliqueit itself.

[QUOTE=Joshua2;167357]I found aliquot doing some repeating work. Probably fixing this would speed things up around 5%. [/QUOTE]

I don't think it's that much of a problem. The more ecm you've done when you find a factor, the larger the factor will tend to be. Consequently if any significant amount of ecm has been done the resulting cofactor will be much smaller and the waste relative to the total time probably not that big. It's not like you run the full ecm workload, find a p5, and then run another full ecm on the original number again. You're certainly right though, aliqueit should keep track of the work done and continue from there.

smh 2009-03-31 09:46

[QUOTE=10metreh;167402]Kill aliqueit, and restart it with -f <the_factor>. You can use as many -f's as you like.[/QUOTE]Thats [B]NOT[/B] an answer to my question.

mklasson 2009-03-31 09:50

[QUOTE=smh;167401]Hi Mikael,

What files does aliqueit look for factors and in what format do i have to put the factors?

For example, i'm running aliqueit on a pc which can't run GNFS, so i just let it run more ECM but in the mean time i factor the number on a couple of other pc's with GNFS. I would like to put the factor in a file, kill ecm, yafu or msieve and let aliqueit automatically pick up the factor.[/QUOTE]

It's different depending on which program it's currently running. If aliqueit is running ecm it looks in <ecm_tempfile> and expects the factor in the format gmp-ecm outputs it. For yafu it's factor.log, for msieve it's msieve.log, and for ggnfs it's ggnfs.log.

I could add a general file that's checked for factors before any new run is done I guess, but would that really be significantly easier for you than killing aliqueit and restarting it with -f <factor>?

smh 2009-03-31 11:51

[QUOTE=mklasson;167411]I could add a general file that's checked for factors before any new run is done I guess, but would that really be significantly easier for you than killing aliqueit and restarting it with -f <factor>?[/QUOTE] No need to go through the trouble.

For ECM, would it be sufficient to put a line like[CODE]prp43 factor: 6171102341771357501785350706054199126217431[/CODE] in the tempfile or does the program expect another format?

mklasson 2009-03-31 12:12

[QUOTE=smh;167418]No need to go through the trouble.

For ECM, would it be sufficient to put a line like[CODE]prp43 factor: 6171102341771357501785350706054199126217431[/CODE] in the tempfile or does the program expect another format?[/QUOTE]

It expects "Factor found" to be on the line, and the factor to come immediately after ": ", so a line like
[code]
Factor found: 6171102341771357501785350706054199126217431
[/code]
should do fine. Note that it's case sensitive though.

The original gmp-ecm lines I match look like
[code]
********** Factor found in step 1: 491102639
********** Factor found in step 2: 144894098912136169
[/code]

mklasson 2009-03-31 20:30

A fresh [url=http://mklasson.com/aliquot.php]aliqueit v1.06[/url] can use msieve to find a gnfs poly, and does so by default.

Setting use_msieve_polyfind=false let's ggnfs find it instead (old behaviour).

Joshua2 2009-03-31 23:57

Cool, I started writing a program, but was having quite a bit of difficulty do to not knowing anything about perl or cygwin.

So I'm trying to get your prog to work, and it says "'msieve' is not recognized as an internal or external command," WARNING: gnfs failed to find a factor. This really shouldn't happen.

msieve is in the directory, and in the gnfs directory...

mklasson 2009-04-01 00:14

[QUOTE=Joshua2;167497]Cool, I started writing a program, but was having quite a bit of difficulty do to not knowing anything about perl or cygwin.

So I'm trying to get your prog to work, and it says "'msieve' is not recognized as an internal or external command," WARNING: gnfs failed to find a factor. This really shouldn't happen.

msieve is in the directory, and in the gnfs directory...[/QUOTE]

It sounds like you need to either put msieve somewhere included in your PATH environment variable so it can be run from anywhere, or adjust your <msieve_cmd> setting in aliqueit.ini to include the full path to your msieve executable.

Aliqueit automatically creates a new directory for each ggnfs run and the <msieve_cmd> executable needs to be runnable from inside that directory.

Joshua2 2009-04-01 00:18

ok, that fixed it. I have cygwin installed, and it looks like you have strawberry perl installed. Is there anything I need to do about that? (I also have activepearl installed) The only way I figured out to get the script to work is to load cygwin bash and cd into the right directory and type "perl factmsieve.pl example.poly"
I'm thinking I need ggnfs_cmd = c:\cygwin\bin\perl "c:\program files\ggnfs\factMsieve.pl"
Edit: Woot! Thanks it seems to be working!

mklasson 2009-04-01 00:22

[QUOTE=Joshua2;167501]ok, that fixed it. I have cygwin installed, and it looks like you have strawberry perl installed. Is there anything I need to do about that? (I also have activepearl installed) The only way I figured out to get the script to work is to load cygwin bash and cd into the right directory and type perl factmsieve.pl example.poly[/QUOTE]

Yes, you will need to change <ggnfs_cmd> to use your perl interpreter instead. You'll also need to use the correct path to your factMsieve.pl in <ggnfs_cmd>.

Andi47 2009-04-01 12:56

Error with v.1.05
 
1 Attachment(s)
I just found a squfof_error.log file in my aliqueit directory which contains (only) this line:

[code]error on N = 0x6279c2a5af1[/code]

I attached the aliqueit.log file (zipped), maybe it helps to track down the error.

mklasson 2009-04-01 13:01

[QUOTE=Andi47;167568]I just found a squfof_error.log file in my aliqueit directory which contains (only) this line:

[code]error on N = 0x6279c2a5af1[/code]

I attached the aliqueit.log file (zipped), maybe it helps to track down the error.[/QUOTE]

That's from yafu. Ben's fixed some squfof bugs lately so if you're running an old yafu version it's a good idea to upgrade (always is).


All times are UTC. The time now is 09:09.

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