mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2018-05-22, 21:30   #1
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

37·89 Posts
Default new yafu stuff

I just checked in a few updates; some bugfixes and some improvements.

yafu's sieve of Eratosthenes received several improvements, especially at large offsets, and including AVX-512 optimizations (build with SKYLAKEX=1)

Also, after 10+ years I finally got around to doing something about LaurV's request to implement "loops and ifs"

Why now? I don't know, but it was fun to work on after all.

New functions "if", "for", "forprime", and "forfactors"

The new functions have laughable error/syntax checking so I'm sure that if anyone tries it out it will start to fail in many interesting ways.

Very brief syntax of each:
for(init; test; iter; body)
where each of the 4 arguments can have assignments and the body can have nested loops or ifs

forprime(var=start;stop;body)
same as 'for'

forfactors(init;body)
loops over any factors found in the previous factorization, defining the special variables _f and _fpow for the factor and exponent associated with the current iteration of the loop.
body can have nested loops/ifs

if(condition;if_body[;else_body])
else_body is optional
condition can make use of e.g., the comparison operators <, >, ==, lte, gte
if_body and/or else_body can have nested loops/ifs

As mentioned, loops and ifs can be nested, but everything must be on one line!

I've attached a few examples that you can run as a script, or one line at a time in the interpreter:
Code:
./yafu -script testscript.txt
This of course is work-in-progress - thanks in advance for any testing and feedback!
Attached Files
File Type: txt testscript.txt (327 Bytes, 86 views)
bsquared is offline   Reply With Quote
Old 2018-05-22, 21:34   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

37·89 Posts
Default

I guess this means that yafu can do this now:

Code:
 ./yafu "forprime(p=2;11213;if(llt(p);print(p);))"


3
5
7
13
17
19
31
61
89
107
127
521
607
1279
2203
2281
3217
4253
4423
9689
9941
11213
bsquared is offline   Reply With Quote
Old 2018-05-23, 04:04   #3
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5×11×61 Posts
Default

Good stuff! Now I have to update a lot of machines. Since you're announcing it, does that mean it's in trunk, or wip, also? I know, I've been lazy and didn't look yet, but I will.


Thanks for all...
EdH is offline   Reply With Quote
Old 2018-05-23, 07:16   #4
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

+1

"Why now? I don't know, but it was fun to work on after all."

That describes pretty much all my open source work in the last 30 years.
danaj is offline   Reply With Quote
Old 2018-05-23, 11:41   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

63358 Posts
Default

Quote:
Originally Posted by EdH View Post
Good stuff! Now I have to update a lot of machines. Since you're announcing it, does that mean it's in trunk, or wip, also? I know, I've been lazy and didn't look yet, but I will.


Thanks for all...
It is still in wip, but I plan to move everything back into trunk soon.

I'd probably wait until some dust settles before you update *all* of your machines...
bsquared is offline   Reply With Quote
Old 2018-05-23, 15:50   #6
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5·11·61 Posts
Default

Quote:
Originally Posted by bsquared View Post
...
I'd probably wait until some dust settles before you update *all* of your machines...
Always good advice. Thanks!
EdH is offline   Reply With Quote
Old 2018-06-04, 14:46   #7
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

CDD16 Posts
Default

r372 has new AVX512 code for SIQS, plus a couple tweaks for more efficiently running on large numbers of threads. RSA-100 in 6 minutes on a 256-thread KNL 7210. Even without the AVX512 code the KNL is pretty fast (about 9 minutes).

I've also tested on a skylake 7800x but the performance gains aren't as nice there. Maybe 10% and only with larger (80 digits or more) inputs.

This is linux only at this point... I have not yet been able to find a compiler capable of avx512 for windows and so I haven't been able to test there. The Intel compiler can, I know, but I don't have a windows version of it.

Code:
starting SIQS on c100: 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139

==== sieve params ====
n = 100 digits, 330 bits
factor base: 115520 primes (max prime = 3204611)
single large prime cutoff: 464668595 (145 * pmax)
double large prime range from 44 to 52 bits
double large prime range from 10269531661321 to 3988944358351073
allocating 9 large prime slices of factor base
buckets hold 2048 elements
large prime hashtables have 1179648 bytes
using KNL-AVX2 enabled 32k sieve core
sieve interval: 8 blocks of size 32768
polynomial A has ~ 13 factors
using multiplier of 1
using SPV correction of 19 bits, starting at offset 30
trial factoring cutoff at 100 bits

==== sieving in progress (256 threads):  115584 relations needed ====
====             Press ctrl-c to abort and save state            ====
119777 rels found: 29067 full + 90710 from 1703942 partial, (4709.08 rels/sec)

sieving required 6419308 total polynomials (4705 'A' polynomials)
trial division touched 258498542 sieve locations out of 3365566152704
squfof: 0 failures, 1386863 attempts, 121153992 outside range, 6726584 prp, 1281923 useful
total reports = 258498542, total surviving reports = 129718525
total blocks sieved = 102712976,avg surviving reports per block = 1.26
large prime scan failures = 0
QS elapsed time = 368.4496 seconds.
bsquared is offline   Reply With Quote
Old 2018-06-07, 21:08   #8
VictordeHolland
 
VictordeHolland's Avatar
 
"Victor de Hollander"
Aug 2011
the Netherlands

23·3·72 Posts
Default

Compiling [r373 wip] on Ubuntu 16.04 with a Sandybridge based processor wanted zlib.h in the /include/ folder (it wasn't in the snapshot I downloaded, but that could be my mistake). No problems/errors otherwise (some warnings, but I tend to ignore those ).
Resulting binary attached (haven't tested it on a other Ubunutu or Linux machine) but I could use EdHs binary from http://mersenneforum.org/showpost.ph...2&postcount=13 so I'm hoping mine also works for other people (and if it doesn't not much lost).


YAFU r373 wip (SSE4.1)
Code:
make all x86_64 NFS=1 USE_SSE41=1
with
GMP 6.1.2
GMP-ECM 7.0.4 (the release version, I think it is SVN2991)
Msieve SVN1019

The computer doesn't have the fancy features such as AVX2 or AVX-512 (only 'normal' AVX), but it is still pretty fast (RSA-100 in less than 11 min)

Code:
06/07/18 22:30:52 v1.35-beta @ E5-2650, nfs: commencing nfs on c100: 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
06/07/18 22:30:52 v1.35-beta @ E5-2650, nfs: commencing poly selection with 32 threads
06/07/18 22:30:52 v1.35-beta @ E5-2650, nfs: setting deadline of 38 seconds
06/07/18 22:31:37 v1.35-beta @ E5-2650, nfs: completed 1174 ranges of size 250 in 44.6341 seconds
06/07/18 22:31:37 v1.35-beta @ E5-2650, nfs: best poly = # norm 1.176668e-13 alpha -4.539699 e 1.188e-08 rroots 2
06/07/18 22:31:37 v1.35-beta @ E5-2650, nfs: commencing lattice sieving with 32 threads
06/07/18 22:32:01 v1.35-beta @ E5-2650, nfs: commencing lattice sieving with 32 threads
06/07/18 22:32:26 v1.35-beta @ E5-2650, nfs: commencing lattice sieving with 32 threads
06/07/18 22:32:50 v1.35-beta @ E5-2650, nfs: commencing lattice sieving with 32 threads
06/07/18 22:33:18 v1.35-beta @ E5-2650, nfs: commencing lattice sieving with 32 threads
06/07/18 22:33:41 v1.35-beta @ E5-2650, nfs: commencing lattice sieving with 32 threads
06/07/18 22:34:07 v1.35-beta @ E5-2650, nfs: commencing lattice sieving with 32 threads
06/07/18 22:34:33 v1.35-beta @ E5-2650, nfs: commencing lattice sieving with 32 threads
06/07/18 22:34:58 v1.35-beta @ E5-2650, nfs: commencing lattice sieving with 32 threads
06/07/18 22:35:24 v1.35-beta @ E5-2650, nfs: commencing lattice sieving with 32 threads
06/07/18 22:35:51 v1.35-beta @ E5-2650, nfs: commencing lattice sieving with 32 threads
06/07/18 22:36:16 v1.35-beta @ E5-2650, nfs: commencing lattice sieving with 32 threads
06/07/18 22:36:43 v1.35-beta @ E5-2650, nfs: commencing lattice sieving with 32 threads
06/07/18 22:37:10 v1.35-beta @ E5-2650, nfs: commencing lattice sieving with 32 threads
06/07/18 22:37:39 v1.35-beta @ E5-2650, nfs: commencing msieve filtering
06/07/18 22:39:13 v1.35-beta @ E5-2650, nfs: commencing msieve linear algebra
06/07/18 22:40:45 v1.35-beta @ E5-2650, nfs: commencing msieve sqrt
06/07/18 22:41:17 v1.35-beta @ E5-2650, prp50 = 37975227936943673922808872755445627854565536638199
06/07/18 22:41:17 v1.35-beta @ E5-2650, prp50 = 40094690950920881030683735292761468389214899724061
06/07/18 22:41:17 v1.35-beta @ E5-2650, NFS elapsed time = 625.1015 seconds.
Attached Files
File Type: 7z yafu-linux64.7z (1.48 MB, 71 views)
VictordeHolland is offline   Reply With Quote
Old 2018-06-19, 03:13   #9
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

32·193 Posts
Default

Trying to compile the latest committed version of YAFU with the following command:

Code:
make clean && make all x86_64 USE_SSE41=1
and I get the following errors at the linking step:
Code:
arith/monty.o: In function `addmod':
/home/wombat/yafu-code/branches/wip/include/monty.h:49: multiple definition of `addmod'
factor/rho.o:/home/wombat/yafu-code/branches/wip/include/monty.h:49: first defined here
arith/monty.o: In function `u64div':
/home/wombat/yafu-code/branches/wip/include/monty.h:62: multiple definition of `u64div'
factor/rho.o:/home/wombat/yafu-code/branches/wip/include/monty.h:62: first defined here
arith/monty.o: In function `mulredc':
/home/wombat/yafu-code/branches/wip/include/monty.h:71: multiple definition of `mulredc'
factor/rho.o:/home/wombat/yafu-code/branches/wip/include/monty.h:71: first defined here
arith/monty.o: In function `mulredc63':
/home/wombat/yafu-code/branches/wip/include/monty.h:114: multiple definition of `mulredc63'
factor/rho.o:/home/wombat/yafu-code/branches/wip/include/monty.h:114: first defined here
collect2: error: ld returned 1 exit status
make: *** [all] Error 1
This is being built with ECM 7.0.5 and GMP-6.1.2. Dropping USE_SSE41=1 doesn't change anything.
wombatman is offline   Reply With Quote
Old 2018-06-20, 12:33   #10
Brian Gladman
 
Brian Gladman's Avatar
 
May 2008
Worcester, United Kingdom

523 Posts
Default

Quote:
Originally Posted by bsquared View Post
r372 has new AVX512 code for SIQS, plus a couple tweaks for more efficiently running on large numbers of threads. RSA-100 in 6 minutes on a 256-thread KNL 7210. Even without the AVX512 code the KNL is pretty fast (about 9 minutes).

I've also tested on a skylake 7800x but the performance gains aren't as nice there. Maybe 10% and only with larger (80 digits or more) inputs.

This is linux only at this point... I have not yet been able to find a compiler capable of avx512 for windows and so I haven't been able to test there. The Intel compiler can, I know, but I don't have a windows version of it.
Hi Ben,

I have access to the Intel compiler running in Visual Studio 2017 so I might be able to compile it if the Visual Studio build files are up to date. However, I don't have an AVX512 capable machine so I would not be able to test the result.
Brian Gladman is offline   Reply With Quote
Old 2018-06-21, 18:50   #11
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

37×89 Posts
Default

Quote:
Originally Posted by wombatman View Post
Trying to compile the latest committed version of YAFU with the following command:

Code:
make clean && make all x86_64 USE_SSE41=1
and I get the following errors at the linking step:
Code:
arith/monty.o: In function `addmod':
/home/wombat/yafu-code/branches/wip/include/monty.h:49: multiple definition of `addmod'
factor/rho.o:/home/wombat/yafu-code/branches/wip/include/monty.h:49: first defined here
arith/monty.o: In function `u64div':
/home/wombat/yafu-code/branches/wip/include/monty.h:62: multiple definition of `u64div'
factor/rho.o:/home/wombat/yafu-code/branches/wip/include/monty.h:62: first defined here
arith/monty.o: In function `mulredc':
/home/wombat/yafu-code/branches/wip/include/monty.h:71: multiple definition of `mulredc'
factor/rho.o:/home/wombat/yafu-code/branches/wip/include/monty.h:71: first defined here
arith/monty.o: In function `mulredc63':
/home/wombat/yafu-code/branches/wip/include/monty.h:114: multiple definition of `mulredc63'
factor/rho.o:/home/wombat/yafu-code/branches/wip/include/monty.h:114: first defined here
collect2: error: ld returned 1 exit status
make: *** [all] Error 1
This is being built with ECM 7.0.5 and GMP-6.1.2. Dropping USE_SSE41=1 doesn't change anything.
You are using the latest msys2 install as your build environment? I haven't been able to reproduce this...
bsquared is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Running YAFU via Aliqueit doesn't find yafu.ini EdH YAFU 8 2018-03-14 17:22
Some old stuff Batalov Miscellaneous Math 1 2017-01-27 04:56
Raman's stuff Raman Chess 8 2013-04-16 20:52
useful stuff paulunderwood Linux 3 2005-12-05 22:18
Extra Stuff... Xyzzy Lounge 11 2003-09-15 23:22

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

Wed Sep 30 22:28:28 UTC 2020 up 20 days, 19:39, 0 users, load averages: 1.20, 1.38, 1.44

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.