?

Log in

No account? Create an account

factordb

« previous entry | next entry »
Sep. 14th, 2011 | 01:54 pm
mood: coldcold

I came across a neat project yesterday, factordb — a database of integers along with their primality status and known factors (if any).

It's really neat to play around with, and you can contribute, too. :) Which is what I've been doing and why I needed to compile yafu last night (well, presumably, any factoring tool would've sufficed, but yafu seems easy to use and well-rounded); however, actually piecing it together on Cygwin has been a bit of a hassle, so here's what I did. :P

To start with, you'll need GMP 5.0.2, GMP-ECM 6.3, msieve 1.49 and yafu 1.28.5. Cygwin may actually have a GMP package (I didn't check), but I wanted to compile things for myself so the code used by the libraries wouldn't be quite as generic.

Set your CFLAGS to something reasonable and fast (I used -march=core2 -mtune=core2 -O3, since I have a Core2 CPU), and start by compiling GMP. In order to do this, I had to specify I want the 32-bit ABI (export ABI=32) first; after that, it was straightforward. Compiling GMP-ECM also was, at least after I told the linker where to find the newly-installed GMP (export LDFLAGS=-L/usr/local/lib, although you can just as well adjust LDPATH instead). Be sure to run make check for both packages to ensure that they're working correctly. :)

Building msieve is still straightforward; edit the Makefile to adjust the C compiler options (it specifies -march=k8 by default), and then build it by running make x86 ECM=1.

Building yafu took a bit more fiddling. Start by adjusting the C compiler options in the Makefile again; in the NFS section of the Makefile, adjust the linker search path for msieve on line 61 (change the linker flag there to just plain -L../msieve, and be sure to create the symlink for msieve if you haven't yet), and add the missing -lz to the linker flags at the end of line 73.

You can start compiling now (make x86 GMPECM=1 NFS=1), but you'll run into compile errors. First of all, SHM_R and SHM_W will be undefined in factor/gmp-ecm/ecm.c, so change SHM_R | SHM_W to IPC_CREAT | 0666 on line 31.

Next up, there'll be errors in factor/qs/tdiv_scan.c and factor/qs/smallmpqs.c:

gcc -march=core2 -mtune=core2 -DHAVE_GMP_ECM -DHAVE_GMP -DUSE_NFS -DHAVE_GMP -DHAVE_GMP_ECM -O3 -fomit-frame-pointer -Wall -I. -Iinclude -I../gmp/include -I../gmp-ecm/include -I../gmp/include -I../gmp-ecm/include -m32 -c -o factor/qs/tdiv_scan.o factor/qs/tdiv_scan.c
factor/qs/tdiv_scan.c:116:63: warning: backslash and newline separated by space
factor/qs/tdiv_scan.c: In function ‘check_relations_siqs_4’:
factor/qs/tdiv_scan.c:351:3: error: unknown register name ‘r11’ in ‘asm’
factor/qs/tdiv_scan.c:351:3: error: unknown register name ‘r10’ in ‘asm’
factor/qs/tdiv_scan.c:351:3: error: unknown register name ‘r9’ in ‘asm’
factor/qs/tdiv_scan.c:351:3: error: unknown register name ‘r8’ in ‘asm’
factor/qs/tdiv_scan.c: In function ‘check_relations_siqs_8’:
factor/qs/tdiv_scan.c:499:3: error: unknown register name ‘r11’ in ‘asm’
factor/qs/tdiv_scan.c:499:3: error: unknown register name ‘r10’ in ‘asm’
factor/qs/tdiv_scan.c:499:3: error: unknown register name ‘r9’ in ‘asm’
factor/qs/tdiv_scan.c:499:3: error: unknown register name ‘r8’ in ‘asm’
factor/qs/tdiv_scan.c: In function ‘check_relations_siqs_16’:
factor/qs/tdiv_scan.c:651:3: error: unknown register name ‘r11’ in ‘asm’
factor/qs/tdiv_scan.c:651:3: error: unknown register name ‘r10’ in ‘asm’
factor/qs/tdiv_scan.c:651:3: error: unknown register name ‘r9’ in ‘asm’
factor/qs/tdiv_scan.c:651:3: error: unknown register name ‘r8’ in ‘asm’
make: *** [factor/qs/tdiv_scan.o] Error 1

gcc -march=core2 -mtune=core2 -DHAVE_GMP_ECM -DHAVE_GMP -DUSE_NFS -DHAVE_GMP -DHAVE_GMP_ECM -O3 -fomit-frame-pointer -Wall -I. -Iinclude -I../gmp/include -I../gmp-ecm/include -I../gmp/include -I../gmp-ecm/include -m32 -c -o factor/qs/smallmpqs.o factor/qs/smallmpqs.c
factor/qs/smallmpqs.c: In function ‘smpqs_check_relations.clone.4.clone.5’:
factor/qs/smallmpqs.c:1086:3: error: unknown register name ‘r11’ in ‘asm’
factor/qs/smallmpqs.c:1086:3: error: unknown register name ‘r10’ in ‘asm’
factor/qs/smallmpqs.c:1086:3: error: unknown register name ‘r9’ in ‘asm’
factor/qs/smallmpqs.c:1086:3: error: unknown register name ‘r8’ in ‘asm’
make: *** [factor/qs/smallmpqs.o] Error 1

The quickest way to fix that is probably to just delete rows 58-131 and 133-197 (respectively; also change the following #elif to an #if in each file). I think this'll make the whole thing less efficient, but c'est la vie. :P

Then you'll get an error in top/driver.c:

gcc -march=core2 -mtune=core2 -DHAVE_GMP_ECM -DHAVE_GMP -DUSE_NFS -DHAVE_GMP -DHAVE_GMP_ECM -O3 -fomit-frame-pointer -Wall -I. -Iinclude -I../gmp/include -I../gmp-ecm/include -I../gmp/include -I../gmp-ecm/include -m32 -c -o top/driver.o top/driver.c
top/driver.c:36:28: fatal error: config.h: No such file or directory
compilation terminated.
make: *** [top/driver.o] Error 1

This file turns out to belong to GMP-ECM, but it's not installed along with the library, so just change the include path to ../../ecm-6.3/config.h (you'll still need to have your GMP-ECM build tree around, obviously).

This fixes compilation, but you'll still encounter linker errors:

gcc -m32 -march=core2 -mtune=core2 -DHAVE_GMP_ECM -DHAVE_GMP -DUSE_NFS -DHAVE_GMP -DHAVE_GMP_ECM -O3 -fomit-frame-pointer -Wall -I. -Iinclude -I../gmp/include -I../gmp-ecm/include -I../gmp/include -I../gmp-ecm/include -m32 arith/tfm/fp_mul_comba.o arith/tfm/fp_mul_comba_small_set.o arith/tfm/fp_sqr_comba.o arith/tfm/fp_sqr_comba_small_set.o arith/tfm/fp_sqr_comba_generic.o arith/tfm/fp_2expt.o arith/tfm/fp_cmp_mag.o arith/tfm/fp_mont_small.o arith/tfm/fp_montgomery_calc_normalization.o arith/tfm/fp_montgomery_reduce.o arith/tfm/fp_montgomery_setup.o arith/tfm/fp_mul_2.o arith/tfm/s_fp_sub.o factor/qs/msieve/lanczos.o factor/qs/msieve/lanczos_matmul0.o factor/qs/msieve/lanczos_matmul1.o factor/qs/msieve/lanczos_matmul2.o factor/qs/msieve/lanczos_pre.o factor/qs/msieve/sqrt.o factor/qs/msieve/savefile.o factor/qs/msieve/gf2.o top/driver.o top/utils.o top/stack.o top/calc.o top/test.o factor/factor_common.o factor/rho.o factor/squfof.o factor/trialdiv.o factor/tune.o factor/qs/filter.o factor/qs/tdiv.o factor/qs/tdiv_small.o factor/qs/tdiv_med.o factor/qs/tdiv_large.o factor/qs/tdiv_scan.o factor/qs/sieve.o factor/qs/new_poly.o factor/qs/poly_roots.o factor/qs/update_poly_roots.o factor/qs/siqs_test.o factor/qs/siqs_aux.o factor/qs/smallmpqs.o factor/qs/SIQS.o factor/gmp-ecm/ecm.o factor/gmp-ecm/pp1.o factor/gmp-ecm/pm1.o factor/nfs/nfs.o arith/arith0.o arith/arith1.o arith/arith2.o arith/arith3.o top/eratosthenes/count.o top/eratosthenes/offsets.o top/eratosthenes/primes.o top/eratosthenes/roots.o top/eratosthenes/linesieve.o top/eratosthenes/soe.o top/eratosthenes/tiny.o top/eratosthenes/worker.o top/eratosthenes/wrapper.o -o yafu -L../gmp/lib/linux -L../gmp-ecm/lib/linux -lecm -lgmp -L/usr/local/lib -L../msieve -L../gmp/lib/linux -L../gmp-ecm/lib/linux -lecm -lmsieve -lgmp -lz -lm -lpthread
factor/qs/smallmpqs.o:smallmpqs.c:(.text+0x5576): undefined reference to `_align_free'
factor/qs/SIQS.o:SIQS.c:(.text+0x1d0f): undefined reference to `_align_free'
factor/qs/SIQS.o:SIQS.c:(.text+0x1d1a): undefined reference to `_align_free'
factor/qs/SIQS.o:SIQS.c:(.text+0x1d25): undefined reference to `_align_free'
factor/qs/SIQS.o:SIQS.c:(.text+0x1d32): undefined reference to `_align_free'
factor/qs/SIQS.o:SIQS.c:(.text+0x1d40): more undefined references to `_align_free' follow
collect2: ld returned 1 exit status
make: *** [x86] Error 1

It turns out that this is due to an omission in include/types.h: add a line at line 334 that says #define align_free free and recompile everything as above, and you should end up with a yafu.exe binary. I've put up a patch with all these changes here.

In order to factor things in the background automatically, you'll want something like yoyo's script. The current-as-of-today version is available here, in this this thread; put your yafu binary in the same place as this script, and edit line 21 to use the right binary and also avoid shell interpretation of the parentheses by replacing "yafu factor($composite) |" with "./yafu.exe factor\\($composite\\) |".

Alas, you're (probably) not quite done yet. Running the script will work in principle now, but it'll abort early without finding any factors:

get composites
Factoring 79 digits: 2907810265178604397432223905191295912636434259538678532393827097124153898839031

factoring 2907810265178604397432223905191295912636434259538678532393827097124153898839031
using pretesting plan: normal

div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 1, starting 1000 iterations on C79
rho: x^2 + 3, starting 1000 iterations on C79
rho: x^2 + 2, starting 1000 iterations on C79
pp1: starting B1 = 20K, B2 = gmp-ecm default on C79
pp1: starting B1 = 20K, B2 = gmp-ecm default on C79
pp1: starting B1 = 20K, B2 = gmp-ecm default on C79
pm1: starting B1 = 100K, B2 = gmp-ecm default on C79Error, no result found

Fortunately, straceing the problem reveals the root of the problem:

[...]
202 2591153 [main] yafu 3320 shmget: shmget (key = 0, size = 4, shmflg = 0x1B6)
133 2591286 [main] yafu 3320 transport_layer_pipes::connect: Try to connect to named pipe: \\.\pipe\cygwin-c5e39b7a9d22bafb-lpc
86 2591372 [main] yafu 3320 transport_layer_pipes::connect: Error opening the pipe (2)
78 2591450 [main] yafu 3320 client_request::make_request: cygserver un-available
[...]

In order to fix this, run cygserver-config, then start the service (cygrunsrv -S cygserver). Then just run the script, and it should start fetching numbers, factoring them and uploading the results, and generally working beautifully. :)

If you have more than one core, you can run multiple instances, too (in multiple directories, so the log files from each instance won't interfere with each other) set threads to a higher value (e.g. 4) in yafu.ini.

Link | Leave a comment | Share

Comments {4}

Winterheart

(no subject)

from: winterheart01
date: Sep. 14th, 2011 06:22 pm (UTC)
Link

minor note, using less commonly used CFLAGS can cause compile errors and instability.
Intel core 2 (cuo) procesors are nothing more than i386 arch
so -mtune=i386 -march=i386 -O2 (yes, not O3) will definitly do.
-fomit-frame-pointer might also best be left out.

(this is not only based from the Gentoo Wiki but also from years of setting my compile flags for ebuils :) )

Reply | Thread

Schneelocke

(no subject)

from: schnee
date: Sep. 14th, 2011 06:32 pm (UTC)
Link

But newer CPUs have new instructions (and even instruction sets) that the original i386 didn't have and that the compiler can utilize when allowed. (In fact, if there was no functional difference between core2 and i386, it'd make no sense for GCC to accept the former; and of course, it would make no difference.)

-O3 was the default for most of the tools used, anyway, and -fomit-frame-pointer also isn't something I specified myself.

And make check passed for GMP and GMP-ECM, at least. :) (I really think the others should come with test suites, too, but they don't.)

Reply | Parent | Thread

Winterheart

(no subject)

from: winterheart01
date: Sep. 14th, 2011 06:36 pm (UTC)
Link

Whilst I agree, mostly since I love to utilise new features myself ;), sadly there still are many libraries that dare to fail/crash due to some compiler flags.

Many poeple even refuse to provide support when they see special stuff because it does weird stuff to the ASM code.

Reply | Parent | Thread

Schneelocke

(no subject)

from: schnee
date: Sep. 14th, 2011 06:45 pm (UTC)
Link

Yeah, some people unfortunately have the wrong attitude there. :/

Reply | Parent | Thread