Yafu

[bsquared]

Originally Posted by bsquared

Not yet... I'm looking into it.

Ok, it should be fixed now. I've provided updated 1.14 binaries for win32 and linux64 on my site.

As a bonus, linux64 people get a sneak peak at v1.15: those binaries now incorporate GMP-ECM to do any ECM work, which of course is much faster. I haven't got this working yet for linux32 or windows... coming soon.

- ben.

P.S. Anyone know of new developments or work being done on making GMP-ECM thread-safe? I beat my head against that when trying to run it multi-threaded before finding this thread.

[bsquared]

Originally Posted by Andi_HB

Interesting is that the command factor from yafu is allways using
multi-threadet ecm.

It should only use multiple threads if you ask it to... if you aren't explicitly doing this with the -threads switch, check the yafu.ini file.

[Buzzo]

Originally Posted by bsquared

Ok, it should be fixed now. I've provided updated 1.14 binaries for win32 and linux64 on my site.

As a bonus, linux64 people get a sneak peak at v1.15: those binaries now incorporate GMP-ECM to do any ECM work, which of course is much faster. I haven't got this working yet for linux32 or windows... coming soon.

- ben.

P.S. Anyone know of new developments or work being done on making GMP-ECM thread-safe? I beat my head against that when trying to run it multi-threaded before finding this thread.

thanks, the new one's working good.

[Jeff Gilchrist]

Sorry, so just to confirm the source for 1.14 should fix all the issues in the Windows build as well so I can build a 64bit Windows binary now for you?

[bsquared]

Originally Posted by Jeff Gilchrist

Sorry, so just to confirm the source for 1.14 should fix all the issues in the Windows build as well so I can build a 64bit Windows binary now for you?

I'll have to send you the updated source. I'll try to get it to you today.

[bsquared]

Version 1.15 now available here.

New in Version 1.15
+ bugfixes
+ integrated GMP-ECM library calls into YAFU, replacing the native
P+1, P-1, and ECM routines in all provided binaries. This capability
is optionally enabled when compiling on systems with GMP and GMP-ECM
available. If not available when compiling from source, the native
YAFU routines are used. GMP-ECM runs single-threaded only (SIQS threading
is not effected).
+ added -v and -silent switches to control verbosity. multiple -v swithes are supported
with increasing verbosity. -v -v gives the same output as what 1.14 produced.
-silent should only print to the logfile, and is not available when run interactively
+ expanded the capability/readablity of the makefile
+ fixed behavior of the primes function, for small ranges (thanks Z and Lou Godio).
Also added environment variables which allow printing of primes to a file or
to the screen. By default primes will print to a file, and not to the screen.
See docfile.txt for more info.

The most noticable of these changes are the GMP-ECM addition and the change in default verbosity. Adding a -v switch or two will be necessary now to see status of a factorization in progress on the screen.

Happy Factoring!
- ben.

[Mini-Geek]

I found a bug related to parsing yafu.ini for the v or silent tags. If you just have a "v" on its own line like the example yafu.ini file it says "expected value after keyword v" and does not make it verbose. Same effect if you have "v=". "v=AnyTextHere" works. Same thing with the 'similar' keyword.
I'd expect it should be where simply a "v" (or possibly also add a synonym "verbose", to help it be clear in the .ini what it's doing) or a "silent" on its own line would be recognized. The included yafu.ini file suggests this is how it should be.

Originally Posted by bsquared

+ integrated GMP-ECM library calls into YAFU, replacing the native P+1, P-1, and ECM routines in all provided binaries.

This is great. Makes YAFU's factor command far more efficient, if nothing else.

Originally Posted by bsquared

GMP-ECM runs single-threaded only (SIQS threading is not effected).

Any chance of this coming in a later version? I was hoping YAFU implementing GMP-ECM would finally mean a good way to run multithreaded ECM.

[bsquared]

Originally Posted by Mini-Geek

I found a bug related to parsing yafu.ini for the v or silent tags. If you just have a "v" on its own line like the example yafu.ini file it says "expected value after keyword v" and does not make it verbose. Same effect if you have "v=". "v=AnyTextHere" works. Same thing with the 'similar' keyword.
I'd expect it should be where simply a "v" (or possibly also add a synonym "verbose", to help it be clear in the .ini what it's doing) or a "silent" on its own line would be recognized. The included yafu.ini file suggests this is how it should be.

Thanks, you're right I missed that. The parsing routine expects everything to have a PARAMETER=VALUE format, but the -v and -silent switches don't have values associated with them. Your workaround is the way to go for now: just set v=1 or silent=1 in the .ini until I can get this cleared up.

Originally Posted by Mini-Geek

This is great. Makes YAFU's factor command far more efficient, if nothing else.

Thanks! I think yafu now is probably the fastest (and probably the easiest) way to factor general numbers below 80-85 digits.

I don't know if it's possible yet, but I'd like to also get ggnfs libraries integrated into yafu, along with msieve poly selection and an assortment of snfs poly recognition abilities, so that factor() is useful to 120+ digit levels. This will likely take a while, if ever.

Originally Posted by Mini-Geek

I was hoping YAFU implementing GMP-ECM would finally mean a good way to run multithreaded ECM.

Me too :( Sadly it looks to be a big problem, as the issue is the thread-safeness of GMP-ECM. It fundamentally has issues with running multi-threaded, for now. I'm looking into what it might take to fix, but I don't expect to get far very fast, given everything else I'm trying to do. This was discussed in the early part of the year (see the link in post 298), but has been silent since. If GMP-ECM gets fixed, it is trivial to enable multi-threading within YAFU... the code is already in place.

[bsquared]

Originally Posted by bsquared

I think yafu now is probably the fastest (and probably the easiest) way to factor general numbers below 80-85 digits.

Yafu might also be a lazy way to run GMP-ECM curves on any number, but there are a couple asterisks I should mention:

1) B2 values aren't exactly the same as default values that GMP-ECM produces for a given B1. I can't figure out a good way to make them the same yet, due to issues involved in B2-computation via the ecm_factor() interface to GMP-ECM. Maybe its easy, but I haven't figured it out yet. The current code produces B2 values that are close.

1b) Specifying B2 in Yafu doesn't do anything anymore... I need to get this fixed. Only the (different) default B2 values are available based on the B1.

2) Win64 versions might display B2=1 when running P+1, P-1, or ECM. It is really using the default B2, but GMP-ECM doesn't provide any mechanism I can find to let calling code know what B2 value was actually used. The value is only available as an output to a file, or the screen, and I don't want to write a parse just to get the B2 value used. I hacked up my local copy of GMP-ECM for Win32 and linux64 versions that allows the B2 used to be displayed, but Win64 or any build from source will have this problem.

3) For optimal performance when running ECM on large inputs (for example Cunninghams or the 4788 sequence), you should still use a locally compiled GMP-ECM as this allows optimization for your specific platform.

all for now,
- ben.

[EdH]

I have YAFU working on a WinXP Laptop, but am trying to run it on a linux PC. (Actually, the laptop is still working the factor example, right now. How long should it take?) I've only tried the factor() routine so far, since I'm just breaking into this area.

However, on the linux machine, I'm getting an "Illegal Instruction" message and exit, trying to use the factor() test from the README file. I've added the computer info and lists of sessions, logs, etc. in case they may be of help. Speaking of help, even that command has trouble on the linux machine, as shown in one of the sections below. I have run some smaller factor() sessions on the linux machine, which completed free from trouble. Other, larger trials crashed in the same fashion as the README version below.

I have noticed that several lines say, "using 64bit linux opteron data for QS time estimation"

I never see any 64bit references on my WinXP machine.

I also tried the yafu-64k-linux32 file, with identical results.

The files were from the "yafu-1.14-linux32bin.tgz" download from the YAFU home page under "32 bit Linux users" and was d/led yesterday.

I'm, of course, not ruling out some simple linux idiosyncrasy that I'm not familiar with, since, although I've been running several distributions over the last few years, I've never really gotten a good grasp of what I'm doing in linux.

Added note: I have gmp-ecm running on my linux machine, but it takes "gmp-ecm" to invoke it. References I've seen, all seem to invoke it through the "ecm" command. Is gmp-ecm called at all, if available?

*************************computer info***********************

AMD Athlon 1.8GHz  1.5G memory  76.5G free hd space
Linux version 2.6.30.9-102.fc11.i586 (mockbuild@xenbuilder4.fedora.phx.redhat.com) 
(gcc version 4.4.1 20090725 (Red Hat 4.4.1-2) (GCC) ) #1 SMP Thu Dec 3 23:46:37 EST 2009
all files in folder named Yafu

****************factor session********************************

[id@compname Yafu]$ ./yafu-32k-linux32


12/11/09 11:46:41 v1.14 @ compname, 
Initializing with Tom's Fast Math (x86-32 asm)...
cached 664581 primes. pmax = 10000079
detected cpu 8, with L1 = 65536 bytes, L2 = 65536 bytes

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

>> factor(2056802480868100646375721251575555494408897387375737955882170045672576386016591560879707933101909539325829251496440620798637813)

Processing expression: factor(2056802480868100646375721251575555494408897387375737955882170045672576386016591560879707933101909539325829251496440620798637813)

***** cpu looks to be about 1795.427970 MHz

factoring 2056802480868100646375721251575555494408897387375737955882170045672576386016591560879707933101909539325829251496440620798637813

div: primes less than 10000
rho: x^2 + 1, doing 1000 iterations on C127 
rho: x^2 + 1, doing 1000 iterations on C121 
rho: x^2 + 3, doing 1000 iterations on C121 
rho: x^2 + 2, doing 1000 iterations on C121 
rho: x^2 + 2, doing 1000 iterations on C112 
pp1: base 1458297508, doing B1 = 20K, B2 = 1M on C112, processed < 1000003
pp1: base 4202712479, doing B1 = 20K, B2 = 1M on C112, processed < 1000003
pp1: base 514418479, doing B1 = 20K, B2 = 1M on C112, processed < 20011
pm1: base 4259100753, doing B1 = 100K, B2 = 5M on C100, processed < 5000011
***** using 64bit linux opteron data for QS time estimation
***** qs time estimate = 41816.343724 seconds
ecm: 5 curves on C100 input, at B1 = 2K, B2 = 200K
***** 15 digit level took 0.696635 seconds.
***** using 64bit linux opteron data for QS time estimation
***** qs time estimate = 2849.245570 seconds
***** estimating 90 more curves can be run at 20 digit level
ecm: 67 curves on C87 input, at B1 = 11K, B2 = 1100K
***** 20 digit level took 34.583163 seconds.
***** using 64bit linux opteron data for QS time estimation
***** qs time estimate = 84.948337 seconds
***** estimating -6 more curves can be run at 25 digit level

starting SIQS on c70: 3950565477929583959090443657115834369563721138106225828250209513731263
restarting siqs from saved data set
0 relations found: 0 full + 0 from 0 partial
threw away 0 relations with large primes too small

==== sieve params ====
n = 71 digits, 233 bits
factor base: 12132 primes (max prime = 277687)
single large prime cutoff: 18049655 (65 * pmax)
allocating 7 large prime slices of factor base
buckets hold 1024 elements
sieve interval: 6 blocks of size 32768
polynomial A has ~ 9 factors
using multiplier of 3
using small prime variation correction of 19 bits
using SSE2 for trial division and x64 sieve scanning
trial factoring cutoff at 83 bits

==== sieving in progress (1 thread):   12196 relations needed ====
====           Press ctrl-c to abort and save state           ====
Illegal instruction
[id@compname Yafu]$

************************factor.log contents**********************************

 ****************************
 Starting factorization of 2056802480868100646375721251575555494408897387375737955882170045672576386016591560879707933101909539325829251496440620798637813
 ****************************
 Rho method, input has 420 bits, 1000 max iterations per poly
 poly x^2 + 1: found prp6 = 280673 in 0.0100 sec
 poly x^2 + 1: 0.1300 sec
 poly x^2 + 3: 0.1200 sec
 poly x^2 + 2: found prp10 = 2756163353 in 0.1000 sec
 poly x^2 + 2: 0.1100 sec
 Williams P+1 method, input has 371 bits, B1 = 20000, B2 = 1000000
 base 1458297508: 0.3100 sec
 base 4202712479: 0.3100 sec
 base 514418479: found prp12 = 598990818061 in 0.1300 sec
 Pollard P-1 method, input has 332 bits, B1 = 100000, B2 = 5000000
 base 4259100753: 0.9300 sec
 25 curves using Lenstra ECM method, input has 332 bits, B1 = 2000, B2 = 200000
 Found prp13 = 4527716228491 in stg2 of curve 5 (thread 0) with sigma = 1825703568
 90 curves using Lenstra ECM method, input has 289 bits, B1 = 11000, B2 = 1100000
 Found prp18 = 248158049830971629 in stg2 of curve 67 (thread 0) with sigma = 3558994494
 starting SIQS on c70: 3950565477929583959090443657115834369563721138106225828250209513731263
 random seeds: 3443356975, 3382818837

*************************session.log contents*****************************************

 Initializing with Tom's Fast Math (x86-32 asm)...
 cached 664581 primes. pmax = 10000079
 detected cpu 8, with L1 = 65536 bytes, L2 = 65536 bytes
 New random seeds: 3924042862, 2834572396

************************separate session**demoing "help"******************

[id@compname Yafu]$ ./yafu-32k-linux32


12/11/09 13:17:11 v1.14 @ compname, 
Initializing with Tom's Fast Math (x86-32 asm)...
cached 664581 primes. pmax = 10000079
detected cpu 8, with L1 = 65536 bytes, L2 = 65536 bytes

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

>> help

searching for help on 'help'
>>

Thanks for any help.

Take Care,
Ed

[Mini-Geek]

Originally Posted by EdH

(Actually, the laptop is still working the factor example, right now. How long should it take?)

Barring any ridiculously bad luck on ECM, an extremely slow CPU, or other extreme circumstances, within 15 minutes at most. My computer, using 2 threads, took just over a minute.