[QUOTE=SLi;367096]Hi,

Yafu seems to run ECM threads in a rather suboptimal way. I have set it to use 8 threads, and what I see is this:

Yafu launches 8 ECM processes at once, then waits until [I]all[/I] of them have terminated until it launches 8 new ones.

Therefore after 7 of the processes have terminated, the last one runs single-threaded to completion, which is not optimal.[/QUOTE]

Yes, this is currently the way it works. I have not had the chance yet to write a more efficient threadpool for ECM. It is on my todo list.

[QUOTE=chris2be8;367467]I'm trying to use yafu to generate SNFS polynomials, but in most cases I get something like: [code]
yafu "snfs(785147655469^11-1, (785147655469^11-1)/412321076416675668)" -np -job opn3.poly -v


02/21/14 17:56:06 v1.34.5 @ linux-5hwg, System/Build Info:
Using GMP-ECM 6.4.4, Powered by GMP 5.1.1
detected AMD Athlon(tm) II X2 240 Processor
detected L1 = 65536 bytes, L2 = 1048576 bytes, CL = 64 bytes
measured cpu frequency ~= 2800.011550
using 20 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
======= bbuhrow@gmail.com =======
======= Type help at any time, or quit to quit =======
===============================================================
cached 78498 primes. pmax = 999983


>> nfs: checking for job file - no job file found
nfs: checking for poly file - no poly file found
nfs: commencing nfs on c131: 69897995262237401384834482134705237527278265531430925083091457319961583310673219510486114342658465407446141111495051191668134955668
nfs: searching for brent special forms...
nfs: searching for homogeneous cunningham special forms...
nfs: searching for XYYXF special forms...
nfs: couldn't find special form
nfs: failed to find snfs polynomial!
[/code]
And similar for (792^48-2)/5587590670330242555933682

Am I doing something wrong? What cases can yafu find a polynomial for?

Chris[/QUOTE]


[QUOTE=docfile.txt]
Supported special forms are:
Various k*b^n+c including:
Cunningham numbers (b^n +- 1 with with b=2, 3, 5, 6, 7, 10, 11, 12)
Brent forms (b^n +/- 1, where 13<=b<=99)
Odd perfect numbers (b^n - 1, b>99)
Generalized Cullen/Woodall numbers (a*b^a +/- 1)
Others: k*2^n +/- 1, repunits, mersenne plus 2, etc.
(Note that for large b, cases with k>1 or abs(c)>1 may not be detected)
Homogeneous Cunningham numbers (a^n +/- b^n, where a,b <= 12 and gcd(a,b) == 1)
XYYXF numbers (x^y + y^x, where 1<y<x<151)
[/QUOTE]

In addition, as of r321 (currently only available as source code in SVN):

[QUOTE=sourceforce commit browser]
* will detect input *cofactors* of forms of type b^n +/- c, for c < 2^30, e.g. the C139 of 10^217 + 2
* will detect homogeneous cunningham forms, a^n +/- b^n, up to a,b <= 51
* will detect xyyxf forms, x^y + y^x, for 1 < x < y < 201
* will detect a^n +/- 1 for arbitrary a, e.g., 903716551382580990289363207931^7-1, or 12332642633^17-1
[/QUOTE]

So, your first example is successfully detected using the latest source (an example of large 'a' in a^n +/- 1). Your second example unfortunately falls under the docfile's "caveat" disclaimer: arbitrary k*a^n +/- c forms are currently detected only if both 'a' and 'n' are < 100.

If you are comfortable working with the source, you can change the maxa and maxb limits on lines 358/359 of snfs.c. It might take longer to find/generate a poly if these are raised too much (search time goes as O(maxa * maxb)), but you are free to experiment with them. It looks like a maxa of, say, 800 would work for your second example.

I think the -siqsR and -siqsT command line switches are not working correctly. I would assume that yafu terminates after the limit is reached. But it turns out that factorization is restarted. I'm using the switches with the factor() command and the -one switch.

My use-case is to find a factor within 5 minutes (or 4 hours or 8 hours) or quit if the time limit is reached. I still have to test if -ggnfsT shows the same behaviour for larger numbers.

[QUOTE=ChristianB;367924]I think the -siqsR and -siqsT command line switches are not working correctly. I would assume that yafu terminates after the limit is reached. But it turns out that factorization is restarted. I'm using the switches with the factor() command and the -one switch.

My use-case is to find a factor within 5 minutes (or 4 hours or 8 hours) or quit if the time limit is reached. I still have to test if -ggnfsT shows the same behaviour for larger numbers.[/QUOTE]

-siqsR and -siqsT apply only to the siqs method. The goal of factor() is to completely factor a number; if a composite is left after siqs or nfs finishes it will assume something went wrong and try again. So while it may not be working for your use case, it is working as designed.

If you don't care about complete factorizations then you probably shouldn't be running siqs or nfs at all. Stopping partway through them with no intention to finish would be a waste of time. I'd look at using the -pretest option.

[QUOTE=bsquared;367926]-siqsR and -siqsT apply only to the siqs method. The goal of factor() is to completely factor a number; if a composite is left after siqs or nfs finishes it will assume something went wrong and try again. So while it may not be working for your use case, it is working as designed.

If you don't care about complete factorizations then you probably shouldn't be running siqs or nfs at all. Stopping partway through them with no intention to finish would be a waste of time. I'd look at using the -pretest option.[/QUOTE]

Thanks, that did the trick. The purpose behind my use-case is to factorize on low-power devices (ARM especially) and reuse the siqs or nfs savefiles as checkpoints. In the case of a BOINC project it is better to have the same runtime per task for each application and also be able to control the runtime for each device class. I'm trying to create a possible workflow with different steps and use as much devices as possible.

[QUOTE=ChristianB;367930]Thanks, that did the trick. The purpose behind my use-case is to factorize on low-power devices (ARM especially) and reuse the siqs or nfs savefiles as checkpoints. In the case of a BOINC project it is better to have the same runtime per task for each application and also be able to control the runtime for each device class. I'm trying to create a possible workflow with different steps and use as much devices as possible.[/QUOTE]
Too small job (is that SIQS?) should not be splitted, as the overhead cost would be too high.

Infinite loop on large numbers when NFS disabled
 

When factoring a large (say, 145 digits) number, after yafu has given up on ECM yafu loops telling that NFS is disabled and incidentally also appending to factor.log very fast (I found a 14 gigabyte factor.log on my computer).

Also, is the Bpoly thing that gets printed on large enough, but not too large (hmm, 125 digits?) numbers NFS related? I get that besides having disabled NFS.

Is there a way to run yafu so that it exits after ECM and does not start siqs/nfs? I'm using a separate script for nfs.

[QUOTE=SLi;369090]When factoring a large (say, 145 digits) number, after yafu has given up on ECM yafu loops telling that NFS is disabled and incidentally also appending to factor.log very fast (I found a 14 gigabyte factor.log on my computer).

Also, is the Bpoly thing that gets printed on large enough, but not too large (hmm, 125 digits?) numbers NFS related? I get that besides having disabled NFS.

Is there a way to run yafu so that it exits after ECM and does not start siqs/nfs? I'm using a separate script for nfs.[/QUOTE]

Sorry about the file... I haven't tested the NFS-disabled path very much.

The Bpoly thing is from siqs on inputs larger than (I think) 105 digits.

You want to use the -pretest option if you want to run factor() without siqs or nfs.

I wanted to report a problem I've found while trying to factor a bunch of numbers. It seems that yafu has a problem with:
factor(151116012007860377)
It goes into smallmpqs, and stays there, seemingly forever. I had let it run for about 38 minutes at one point. By that time yafu was using around 4GB of memory. I've tried to track down the issue, but I was unable to. It looks like smallmpqs can't find any relations for this number, but I'm not sure why. This is with the latest version of yafu, svn328. I see that yafu's ecm can factor this number easily. Please let me know if you need any more information.

Older versions work well on this particular factorization
[CODE]04/05/14 20:23:22 v1.34.1 @ XTREME-I7K, System/Build Info:
Using GMP-ECM, Powered by GMP
detected Intel(R) Core(TM) i7-2600K CPU @ 3.40GHz
detected L1 = 32768 bytes, L2 = 8388608 bytes, CL = 64 bytes
measured cpu frequency ~= 3254.813300
using 20 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
======= bbuhrow@gmail.com =======
======= Type help at any time, or quit to quit =======
===============================================================
cached 78498 primes. pmax = 999983


>> factor(151116012007860377)

fac: factoring 151116012007860377
fac: using pretesting plan: custom
fac: custom pretest ratio is: 0.3300
fac: using tune info for qs/gnfs crossover
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C18
rho: x^2 + 2, starting 1000 iterations on C18
rho: x^2 + 1, starting 1000 iterations on C18
pm1: starting B1 = 150K, B2 = gmp-ecm default on C18
ecm: 0/30 curves on C18, B1=2K, B2=gmp-ecm default
Total factoring time = 0.1100 seconds


***factors found***

P9 = 599233181
P9 = 252182317

ans = 1[/CODE]

I'll take a look. I hate it when I break stuff trying to make things better :smile: