mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2021-03-15, 14:42   #1
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

2×412 Posts
Default YAFU 1.34.5 sometimes doesn't output all prime factors it finds

I've been playing with YAFU working through a list numbers to factor and noticed something odd. Notice in this example I pass it a C137, and it (apparently) finds 3 small factors before starting SIQS, but this isn't output to the screen, nor are the small factors listed in the "factors found" section at the end:
Code:
C:\yafu>echo factor(54418768736607191047474367397296287346558101361357615895102532027502218028864900611252344602881107231766434356924576647214698324810074769) | yafu-x64.exe -plan deep -op op.txt -of of.txt -ou ou.txt -session NUL

03/14/21 23:48:25 v1.34.5 @ 3930K, System/Build Info:
Using GMP-ECM 6.3, Powered by GMP 5.1.1
detected        Intel(R) Core(TM) i7-3930K CPU @ 3.20GHz
detected L1 = 32768 bytes, L2 = 12582912 bytes, CL = 64 bytes
measured cpu frequency ~= 3174.726070
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


>>
fac: factoring 54418768736607191047474367397296287346558101361357615895102532027502218028864900611252344602881107231766434356924576647214698324810074769
fac: using pretesting plan: deep
fac: using tune info for qs/gnfs crossover

starting SIQS on c100: 1123834575117199556793879891591685761727252434123299309584292500954870945819815460995782768587102639

==== sieving in progress ( 6 threads):  115568 relations needed ====
====            Press ctrl-c to abort and save state            ====


SIQS elapsed time = 54.2891 seconds.
Total factoring time = 54.4021 seconds


***factors found***

P39 = 421733524843190780249388261839156579767
P61 = 2664797814058212286560533454960446792210016180875809243599817

ans = 1

>>
The missing small factors:
Quote:
P8 = 10722169
P13 = 2144921195591
P19 = 2105485879475562449
The jobs I'm running are called sequentially in a batch file with a command line similar to the first line in the code above.
If I spawn another YAFU instance in another directory and interactively run factor on the number it lists all the facts as expected. This "odd" behaviour also only happens on a small fraction of my work (2%?). v1.34.5 on Win7-64.

I know this might be hard/impossible to track down since it works as expected when I re-run the job, I'm just mentioning it in case it's a known thing and/or if there's something obvious I'm doing wrong.
James Heinrich is offline   Reply With Quote
Old 2021-03-15, 16:49   #2
chris2be8
 
chris2be8's Avatar
 
Sep 2009

204310 Posts
Default

Does it work OK if you re-run in the *same* directory? If not there is probably some file in there that yafu thinks is relevant to the job but isn't.

I've never seen this in millions of yafu runs, but I always run yafu in an empty directory.

And I'm running on Linux so my experience may not be relevant.

Chris

Last fiddled with by chris2be8 on 2021-03-15 at 16:50 Reason: State OS.
chris2be8 is offline   Reply With Quote
Old 2021-03-15, 16:56   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

D6E16 Posts
Default

My guess is that this has something to do with the "-op op.txt -of of.txt -ou ou.txt" options. And/or the lack of a factor.log. And/or using a batchfile. Or all of them together. Those are corners of yafu that I don't use myself, therefore are less well tested. I will look into it. In the meantime if you see it happen again and can provide more background on the sequence of events, that might be helpful.
bsquared is offline   Reply With Quote
Old 2021-03-15, 17:00   #4
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

2×412 Posts
Default

Quote:
Originally Posted by bsquared View Post
My guess is that this has something to do with the "-op op.txt -of of.txt -ou ou.txt" options.
And/or the lack of a factor.log
I'm not 100% certain, but I'm pretty sure I saw this behavior prior to adding those op/of/ou options.
And actually there is a factor.log, not sure if it provides any additional insight:
Code:
03/14/21 23:48:25 v1.34.5 @ 3930K, ****************************
03/14/21 23:48:25 v1.34.5 @ 3930K, Starting factorization of 54418768736607191047474367397296287346558101361357615895102532027502218028864900611252344602881107231766434356924576647214698324810074769
03/14/21 23:48:25 v1.34.5 @ 3930K, using pretesting plan: deep
03/14/21 23:48:25 v1.34.5 @ 3930K, using tune info for qs/gnfs crossover
03/14/21 23:48:25 v1.34.5 @ 3930K, ****************************
03/14/21 23:48:25 v1.34.5 @ 3930K, starting SIQS on c100: 1123834575117199556793879891591685761727252434123299309584292500954870945819815460995782768587102639
03/14/21 23:48:25 v1.34.5 @ 3930K, random seeds: 3760058019, 308793872
03/14/21 23:48:27 v1.34.5 @ 3930K, ==== sieve params ====
03/14/21 23:48:27 v1.34.5 @ 3930K, n = 100 digits, 330 bits
03/14/21 23:48:27 v1.34.5 @ 3930K, factor base: 115504 primes (max prime = 3214879)
03/14/21 23:48:27 v1.34.5 @ 3930K, single large prime cutoff: 466157455 (145 * pmax)
03/14/21 23:48:27 v1.34.5 @ 3930K, double large prime range from 44 to 52 bits
03/14/21 23:48:27 v1.34.5 @ 3930K, double large prime cutoff: 4011979832943029
03/14/21 23:48:27 v1.34.5 @ 3930K, using 32k sieve core
03/14/21 23:48:27 v1.34.5 @ 3930K, sieve interval: 20 blocks of size 32768
03/14/21 23:48:27 v1.34.5 @ 3930K, polynomial A has ~ 13 factors
03/14/21 23:48:27 v1.34.5 @ 3930K, using multiplier of 1
03/14/21 23:48:27 v1.34.5 @ 3930K, using SPV correction of 21 bits, starting at offset 32
03/14/21 23:48:27 v1.34.5 @ 3930K, using SSE2 for trial division and x128 sieve scanning
03/14/21 23:48:27 v1.34.5 @ 3930K, using SSE4.1 enabled 32k sieve core
03/14/21 23:48:27 v1.34.5 @ 3930K, using SSE2 for resieving 13-16 bit primes
03/14/21 23:48:27 v1.34.5 @ 3930K, trial factoring cutoff at 105 bits
03/14/21 23:48:27 v1.34.5 @ 3930K, ==== sieving started ( 6 threads) ====
03/14/21 23:48:27 v1.34.5 @ 3930K, trial division touched 0 sieve locations out of 0
03/14/21 23:48:27 v1.34.5 @ 3930K, squfof: 0 failures, 0 attempts, 0 outside range, 0 prp, 0 useful
03/14/21 23:48:27 v1.34.5 @ 3930K, 116262 relations found: 30071 full + 86191 from 1634859 partial, using 0 polys (-1 A polys)
03/14/21 23:48:27 v1.34.5 @ 3930K, on average, sieving found 1.#J rels/poly and 1061756.66 rels/sec
03/14/21 23:48:27 v1.34.5 @ 3930K, trial division touched 0 sieve locations out of 0
03/14/21 23:48:27 v1.34.5 @ 3930K, ==== post processing stage (msieve-1.38) ====
03/14/21 23:48:28 v1.34.5 @ 3930K, begin with 1665504 relations
03/14/21 23:48:28 v1.34.5 @ 3930K, reduce to 293279 relations in 10 passes
03/14/21 23:48:30 v1.34.5 @ 3930K, recovered 293279 relations
03/14/21 23:48:30 v1.34.5 @ 3930K, recovered 274220 polynomials
03/14/21 23:48:30 v1.34.5 @ 3930K, freed 51 duplicate relations
03/14/21 23:48:30 v1.34.5 @ 3930K, attempting to build 116160 cycles
03/14/21 23:48:30 v1.34.5 @ 3930K, found 116160 cycles in 5 passes
03/14/21 23:48:30 v1.34.5 @ 3930K, distribution of cycle lengths:
03/14/21 23:48:30 v1.34.5 @ 3930K,    length 1 : 30071
03/14/21 23:48:30 v1.34.5 @ 3930K,    length 2 : 21364
03/14/21 23:48:30 v1.34.5 @ 3930K,    length 3 : 19927
03/14/21 23:48:30 v1.34.5 @ 3930K,    length 4 : 15653
03/14/21 23:48:30 v1.34.5 @ 3930K,    length 5 : 11243
03/14/21 23:48:30 v1.34.5 @ 3930K,    length 6 : 7496
03/14/21 23:48:30 v1.34.5 @ 3930K,    length 7 : 4529
03/14/21 23:48:30 v1.34.5 @ 3930K,    length 9+: 5877
03/14/21 23:48:30 v1.34.5 @ 3930K, largest cycle: 18 relations
03/14/21 23:48:30 v1.34.5 @ 3930K, matrix is 115504 x 116160 (33.9 MB) with weight 7962581 (68.55/col)
03/14/21 23:48:30 v1.34.5 @ 3930K, sparse part has weight 7962581 (68.55/col)
03/14/21 23:48:31 v1.34.5 @ 3930K, filtering completed in 3 passes
03/14/21 23:48:31 v1.34.5 @ 3930K, matrix is 109011 x 109073 (31.9 MB) with weight 7500257 (68.76/col)
03/14/21 23:48:31 v1.34.5 @ 3930K, sparse part has weight 7500257 (68.76/col)
03/14/21 23:48:31 v1.34.5 @ 3930K, saving the first 48 matrix rows for later
03/14/21 23:48:31 v1.34.5 @ 3930K, matrix is 108963 x 109073 (27.8 MB) with weight 6599836 (60.51/col)
03/14/21 23:48:31 v1.34.5 @ 3930K, sparse part has weight 6188228 (56.73/col)
03/14/21 23:48:31 v1.34.5 @ 3930K, matrix includes 64 packed rows
03/14/21 23:48:31 v1.34.5 @ 3930K, using block size 43629 for processor cache size 12288 kB
03/14/21 23:48:32 v1.34.5 @ 3930K, commencing Lanczos iteration
03/14/21 23:48:32 v1.34.5 @ 3930K, memory use: 21.6 MB
03/14/21 23:49:19 v1.34.5 @ 3930K, lanczos halted after 1725 iterations (dim = 108959)
03/14/21 23:49:20 v1.34.5 @ 3930K, recovered 16 nontrivial dependencies
03/14/21 23:49:20 v1.34.5 @ 3930K, prp39 = 421733524843190780249388261839156579767
03/14/21 23:49:20 v1.34.5 @ 3930K, prp61 = 2664797814058212286560533454960446792210016180875809243599817
03/14/21 23:49:20 v1.34.5 @ 3930K, Lanczos elapsed time = 52.5410 seconds.
03/14/21 23:49:20 v1.34.5 @ 3930K, Sqrt elapsed time = 0.1800 seconds.
03/14/21 23:49:20 v1.34.5 @ 3930K, SIQS elapsed time = 54.2891 seconds.
03/14/21 23:49:20 v1.34.5 @ 3930K, 
03/14/21 23:49:20 v1.34.5 @ 3930K, 
03/14/21 23:49:20 v1.34.5 @ 3930K, Total factoring time = 54.4021 seconds

Last fiddled with by James Heinrich on 2021-03-15 at 17:01
James Heinrich is offline   Reply With Quote
Old 2021-03-15, 17:14   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×32×191 Posts
Default

Ah, ok, thanks for posting that. In this case then it is easy: the number had already been previously factored by siqs. I can tell because of these lines:

Code:
03/14/21 23:48:27 v1.34.5 @ 3930K, ==== sieving started ( 6 threads) ====
03/14/21 23:48:27 v1.34.5 @ 3930K, trial division touched 0 sieve locations out of 0
03/14/21 23:48:27 v1.34.5 @ 3930K, squfof: 0 failures, 0 attempts, 0 outside range, 0 prp, 0 useful
03/14/21 23:48:27 v1.34.5 @ 3930K, 116262 relations found: 30071 full + 86191 from 1634859 partial, using 0 polys (-1 A polys)
03/14/21 23:48:27 v1.34.5 @ 3930K, on average, sieving found 1.#J rels/poly and 1061756.66 rels/sec
03/14/21 23:48:27 v1.34.5 @ 3930K, trial division touched 0 sieve locations out of 0
Where no actual sieving was done - the data was loaded from an existing file. When an siqs savefile exists for a factor of an input, yafu skips directly to resuming siqs on that factor and the cofactor of the input is ignored. So this is expected behavior. Whether it is the most *useful* behavior is up for debate.

Could you ever have a case where, for whatever reason, multiple adjacent lines in your batchfile are cofactors of some common number? Then you might see this behavior.
bsquared is offline   Reply With Quote
Old 2021-03-15, 17:23   #6
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

1101001000102 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
Does it work OK if you re-run in the *same* directory? If not there is probably some file in there that yafu thinks is relevant to the job but isn't.
It does work OK re-running it in the same directory, at least it does now. I think it may be related to sequential running of similar numbers. In this case I ran factorization on two numbers sequentially:
Quote:
fac: factoring 5075350774326275872677847868028967585435195188712061514335628549363679870077117849126640757376712420011886993846541371173565565401
P13 = 2144921195591
P19 = 2105485879475562449
P39 = 421733524843190780249388261839156579767
P61 = 2664797814058212286560533454960446792210016180875809243599817

fac: factoring 54418768736607191047474367397296287346558101361357615895102532027502218028864900611252344602881107231766434356924576647214698324810074769
P8 = 10722169
P13 = 2144921195591
P19 = 2105485879475562449
P39 = 421733524843190780249388261839156579767
P61 = 2664797814058212286560533454960446792210016180875809243599817
The second number is effectively a continuation of the prior one. (In case you're wondering, these are composite factors of M1087).I'm re-running a test on these two specific sequential candidates right now in a clean directory, will probably take an hour or so to see what happens.
James Heinrich is offline   Reply With Quote
Old 2021-03-15, 17:25   #7
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

1101001000102 Posts
Default

Quote:
Originally Posted by bsquared View Post
So this is expected behavior. Whether it is the most *useful* behavior is up for debate.
In my opinion there's no debate, to me this seems highly un-useful.
That said, I'm sure I'm that weirdo user who uses YAFU all wrong.

Quote:
Originally Posted by bsquared View Post
When an siqs savefile exists for a factor of an input..
Is there a way to disable this? Would deleting siqs.dat between candidates "fix" it?

Last fiddled with by James Heinrich on 2021-03-15 at 17:29
James Heinrich is offline   Reply With Quote
Old 2021-03-15, 17:43   #8
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

65568 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
In my opinion there's no debate, to me this seems highly un-useful.
That said, I'm sure I'm that weirdo user who uses YAFU all wrong.
Thanks for the feedback. You're not doing anything wrong. In fact in this case I can see that it's probably not working as it should. I don't think there is any documentation of what it should do in this case but in general, "factor" tries to completely factor inputs. So ignoring part of the input just because there is a savefile it can resume probably isn't working in the right spirit of things.


Quote:
Originally Posted by James Heinrich View Post
Is there a way to disable this? Would deleting siqs.dat between candidates "fix" it?
Well, yes, but obviously this is a suboptimal fix as it would then refactor the large part of the input. But until I can implement a real fix it will work.

Another way would be to restructure your input file to remove situations like this. You really only need to factor the larger number... the smaller one can be constructed from a subset of its factors.
bsquared is offline   Reply With Quote
Old 2021-03-15, 19:43   #9
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

2·412 Posts
Default

Quote:
Originally Posted by bsquared View Post
Another way would be to restructure your input file to remove situations like this. You really only need to factor the larger number... the smaller one can be constructed from a subset of its factors.
In my particular example I don't actually need to factor them at all, since the candidate numbers are constructed of known factors. I was just fiddling around experimenting with YAFU and generated this data set and observed the unexpected behavior.
James Heinrich is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
yafu doesn't build with CUDA enabled Happy5214 YAFU 2 2021-01-29 01:42
Running YAFU via Aliqueit doesn't find yafu.ini EdH YAFU 8 2018-03-14 17:22
Yafu not writing to the output file as requested BudgieJane YAFU 3 2016-02-22 15:14
Verser Finds Four Factors, Finishes 'Feuillian wblipp ElevenSmooth 4 2008-07-17 11:58
SOB Finds a big prime! Prime95 Lounge 5 2007-05-06 09:01

All times are UTC. The time now is 22:06.

Mon May 17 22:06:54 UTC 2021 up 39 days, 16:47, 0 users, load averages: 3.43, 3.60, 3.51

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