YAFU 2.0

[bsquared]

Originally Posted by Gimarel

I'm getting the same SEGFAULT with gcc-9. I will try to install gcc-11, but this will take some time.

Weird. I have not changed anything in update_poly_roots_32k_avx2.c in over 5 months, according to github, and those were unrelated changes to where this error occurred. The core routine that produced the segfault hasn't changed in years. As a wild guess you could try changing -march=native to -march=znver1 or -march=znver2 and get rid of -mtune=native. Maybe the compiler is mis-identifying the exact cpu or mis-tuning the code.

Originally Posted by Gimarel

I also tried clang-11 but the build fails ...

I have never tried building with that compiler so not very surprising. The inline assembly doesn't port easily...

[bsquared]

Just checked in version 2.06. I updated the function where Gimeral's error was occurring. For me it is now faster on AVX2 systems, especially with the windows .exe, and hopefully also works for everyone.

[bsquared]

Looking back over some historical benchmarks (time in seconds for sequence of inputs), 2.06 is a pretty big speedup for AVX2 systems, for either MSVC windows or linux builds. Still hoping it is also more stable across compilers/cpus.

AVX2 linux, icc (Xeon E5-2697 v3):

version     c60     c65     c70     c75     c80     c85     c90     c95
v1.34.5     2.35    6.9	    14.8    52.4    104.8   294             3132
v1.35.0     2.2	    6.4	    12.9    43.6    89.8    262     1037    2912
v2.05       1.83    5.66    11	    37	    76.6    229		
v2.06       1.69    5.48    11.2    35.7    69.5    208     794     2210

AVX2 Windows, MSVC19 (Xeon 6134):

version         c60     c65     c70     c75     c80      c85    
v1.34.5		2.54	7.42	15.1	53.8	111.4    311
v2.05		1.93	6.98	14.3	51.7	100.6    314.2
v2.06		1.89	6.11	12.2	41.5	82.1     240.5

And for comparison, with all available instruction set enhancements (AVX512BW, AVX512VL, AVX512F):

version         c60     c65     c70     c75     c80      c85     c90     c95
v2.06		1.16	3.44	6.64	21.9	44.5     135.1   516     1516

[BudgieJane]

I've just run the C108 cofactor of 73+34.59 through yafu 2.06, although I'm sure any of the previous versions would show the same behaviour.

08/18/21 19:43:23, 
08/18/21 19:43:23, ****************************
08/18/21 19:43:23, Starting factorization of 806612539887522076624435765094947314651498682479207276130902929847315087082262158953156473845821936013965643
08/18/21 19:43:23, using pretesting plan: normal
08/18/21 19:43:23, using tune info for qs/gnfs crossover
08/18/21 19:43:23, ****************************
08/18/21 19:43:23, rho: x^2 + 3, starting 1000 iterations on C108
08/18/21 19:43:23, prp11 = 40061753549
08/18/21 19:43:23, rho: x^2 + 3, starting 1000 iterations on C98
08/18/21 19:43:23, rho: x^2 + 2, starting 1000 iterations on C98
08/18/21 19:43:23, rho: x^2 + 1, starting 1000 iterations on C98
08/18/21 19:43:24, pm1: starting B1 = 150K, B2 = gmp-ecm default on C98
08/18/21 19:43:24, current ECM pretesting depth: 0.00
08/18/21 19:43:24, scheduled 30 curves at B1=2000 toward target pretesting depth of 30.15
08/18/21 19:43:24, Finished 30 curves using GMP-ECM method on C98 input, B1=2k, B2=gmp-ecm default
08/18/21 19:43:24, current ECM pretesting depth: 15.18
08/18/21 19:43:24, scheduled 74 curves at B1=11000 toward target pretesting depth of 30.15
08/18/21 19:43:25, Finished 74 curves using GMP-ECM method on C98 input, B1=11k, B2=gmp-ecm default
08/18/21 19:43:25, current ECM pretesting depth: 20.24
08/18/21 19:43:25, scheduled 214 curves at B1=50000 toward target pretesting depth of 30.15
08/18/21 19:43:29, Finished 214 curves using GMP-ECM method on C98 input, B1=50k, B2=gmp-ecm default
08/18/21 19:43:29, pm1: starting B1 = 3750K, B2 = gmp-ecm default on C98
08/18/21 19:43:30, current ECM pretesting depth: 25.33
08/18/21 19:43:30, scheduled 402 curves at B1=250000 toward target pretesting depth of 30.15
08/18/21 19:43:52, prp28 = 2606325622300954201341849509 (curve 284 stg2 B1=250000 sigma=3962908428 thread=11)
08/18/21 19:43:53, Finished 294 curves using GMP-ECM method on C98 input, B1=250k, B2=gmp-ecm default
08/18/21 19:43:53, final ECM pretested depth: 28.75
08/18/21 19:43:53, scheduler: switching to sieve method
08/18/21 19:43:53, starting SIQS on c70: 7725139683897973308307472537355787653622803183466786522414544405964523
08/18/21 19:43:53, random seed: 2108661816
08/18/21 19:43:53, prp70 = 7725139683897973308307472537355787653622803183466786522414544405964523
08/18/21 19:43:53, Total factoring time = 30.2247 seconds

My question is: Having finished the GMP-ECM method on C98 and now noticing what we are testing is C70, why not do a PRP test before starting SIQS and selecting a random seed, etc.?

[bsquared]

Originally Posted by BudgieJane

My question is: Having finished the GMP-ECM method on C98 and now noticing what we are testing is C70, why not do a PRP test before starting SIQS and selecting a random seed, etc.?

No particular reason, but notice that it doesn't spend very long in SIQS. 0 seconds to be exact. Checking the input for various properties is the first thing siqs does. And also the first thing other routines do as well. It isn't part of the autofactorer loop because one could write something like this instead of factor, and then no primality test would be performed:

siqs(ecm(pm1(rho(trial(n,10000))), 100))

[charybdis]

While trying to do a 2.05 vs 2.06 benchmark, I discovered that the -batchfile option seems to be broken. When I run "yafu "siqs(@)" -batchfile in.bat", yafu quits with

>> fopen error: No such file or directory
couldn't open R for reading

Happens on linux and windows. Old versions (pre v2) work properly.

PS. Thanks for all the excellent work over the last couple of months!

[bsquared]

Originally Posted by charybdis

While trying to do a 2.05 vs 2.06 benchmark, I discovered that the -batchfile option seems to be broken. When I run "yafu "siqs(@)" -batchfile in.bat", yafu quits with

>> fopen error: No such file or directory
couldn't open R for reading

Happens on linux and windows. Old versions (pre v2) work properly.

PS. Thanks for all the excellent work over the last couple of months!

Yes, I've noticed that as well but haven't got around to fixing it yet. Mostly because cat in.bat | yafu "siqs(@)" still works, somehow.

Also, fyi, yafu has a built-in siqs benchmark function:

./yafu "siqsbench"

Output is written to a bench.log file instead of factor.log.

This is what I run over and over again during testing.

[charybdis]

Originally Posted by bsquared

Also, fyi, yafu has a built-in siqs benchmark function:

./yafu "siqsbench"

Thank you for the tip! I'm seeing a >10% speedup at c90 and c95

[BudgieJane]

I'm having problems with version 2.06. It works OK on my new computer, running Windows 10 Pro, but it will not run on my old ones running Windows 7 Pro. It puts up the welcome message, waits something like half a minute, then quietly returns me to the command prompt:

JANELT3 C:\Users\Jane\Documents\Maths\yafu\Versions\yafu-2.06 > yafu-x64


YAFU Version 2.06
Built with Microsoft Visual Studio 1922
Using GMP-ECM 7.0.4, Powered by MPIR 3.0.0
Detected Intel(R) Core(TM) i7-4710MQ CPU @ 2.50GHz
Detected L1 = 32768 bytes, L2 = 6291456 bytes, CL = 64 bytes
Using 1 random witness for Rabin-Miller PRP checks
Cached 664579 primes; max prime is 9999991

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

>>
JANELT3 C:\Users\Jane\Documents\Maths\yafu\Versions\yafu-2.06 >

Is there something I ought to have somewhere on those old computers but which is missing, but the new computer does have it?

[WraithX]

Originally Posted by BudgieJane

I'm having problems with version 2.06. It works OK on my new computer, running Windows 10 Pro, but it will not run on my old ones running Windows 7 Pro. It puts up the welcome message, waits something like half a minute, then quietly returns me to the command prompt:

Is there something I ought to have somewhere on those old computers but which is missing, but the new computer does have it?

It works fine on my Windows 7 Pro x64.

C:\yafu\yafu_2.06>yafu-x64.exe


YAFU Version 2.06
Built with Microsoft Visual Studio 1922
Using GMP-ECM 7.0.4, Powered by MPIR 3.0.0
Detected Intel(R) Xeon(R) CPU E5-2687W v4 @ 3.00GHz
Detected L1 = 32768 bytes, L2 = 31457280 bytes, CL = 64 bytes
Using 1 random witness for Rabin-Miller PRP checks
Cached 664579 primes; max prime is 9999991

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

>> factor(10^19+49)

fac: factoring 10000000000000000049
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 100 digits
fac: no tune info: using qs/snfs crossover of 75 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C20
Total factoring time = 0.0400 seconds


***factors found***

PRP10 = 8532383917
PRP10 = 1172005397

ans = 1

>>

I used the program Dependency Walker to see what dll's are linked/used by yafu. The ones I think you might be missing are VCOMP140.DLL and VCRUNTIME140.DLL.

These are included with the Microsoft Visual C++ Redistributable packages from Microsoft. You can find links to the latest here (I'd recommend both the 32-bit and 64-bit):
https://support.microsoft.com/en-us/...f-95f26a218cc0

[BudgieJane]

Originally Posted by WraithX

It works fine on my Windows 7 Pro x64.

...

I used the program Dependency Walker to see what dll's are linked/used by yafu. The ones I think you might be missing are VCOMP140.DLL and VCRUNTIME140.DLL.

These are included with the Microsoft Visual C++ Redistributable packages from Microsoft. You can find links to the latest here (I'd recommend both the 32-bit and 64-bit):
https://support.microsoft.com/en-us/...f-95f26a218cc0

No, I've got them. Dependency Walker says what are missing are these:

API-MS-WIN-CORE-WINRT-ERROR-L1-1-0.DLL
API-MS-WIN-CORE-WINRT-L1-1-0.DLL
API-MS-WIN-CORE-WINRT-ROBUFFER-L1-1-0.DLL
API-MS-WIN-CORE-WINRT-STRING-L1-1-0.DLL
DCOMP.DLL
IESHIMS.DLL

and I searched the web for one of them and came up with https://stackoverflow.com/questions/...t-dll-problems which I've been looking at without much luck. I've also tried installing vc_redist.x64.exe, again no luck. About the only good thing that has come out of my fiddling with all this is that it has installed edge on my Win-7 machine (so much for lack of further support for Windoze 7!). I think the time has come to upgrade to Win-10 Pro for my development machine (now where can I get a decent one dirt cheap?)