Feedback for new MPQS utility sought

[error404]

Jason,

I re-tested tst300_c89 on my AMD64 and it works correctly.

*** SWAG ***

-m96bit-long-double
-m128bit-long-double
These switches control the size of long double type. The i386 application
binary interface specifies the size to be 96 bits, so -m96bit-long-double
is the default in 32 bit mode.

In the x86-64 compiler, -m128bit-long-double is the default choice as its
ABI specifies that long double is to be aligned on 16 byte boundary.


GCC in 32-bit mode uses -m96bit-long-double by default. I have ran into
round off errors and segmentation faults before when testing other peoples
software in 32-bit mode. Normally, the problems do not exist for 64-bit
systems ????


Tom

/******************************************************************************/

AMD64-3400+, 1M L2, 2G PC3200
Gigabye GA-K8VT800M motherboard

gigabyte#
gigabyte# uname -a
FreeBSD gigabyte.dl.cox.net 5.3-RELEASE FreeBSD 5.3-RELEASE #0: Sun Nov 7 15:10:12 CST 2004
root@gigabyte.dl.cox.net:/usr/src/sys/amd64/compile/MYKERNEL amd64
gigabyte#
gigabyte#
gigabyte# gcc34 -v
Reading specs from /usr/local/lib/gcc/x86_64-portbld-freebsd5.3/3.4.4/specs
Configured with: ./..//gcc-3.4-20041112/configure --disable-nls --with-system-zlib --with-libiconv-prefix=/usr/local --program-suffix=34 --with-gxx-include-dir=/usr/local/lib/gcc/x86_64-portbld-freebsd5.3/3.4.4/include/c++/ --disable-shared --disable-libgcj --prefix=/usr/local x86_64-portbld-freebsd5.3
Thread model: posix
gcc version 3.4.4 20041112 (prerelease) [FreeBSD]
gigabyte#
gigabyte#
gigabyte# gcc34 -O3 -march=k8 *.c -o qs08 -lm
gigabyte#
gigabyte#
gigabyte#
gigabyte#
gigabyte#
gigabyte# time ./qs08 < tst300c89.txt
input to factor:
factoring 96693117801151196901759163062845005740662686097142800237507655454506720219714304894194857
Mon Nov 22 12:26:29 2004
296 bits 59333 primes bound 1561013
using multiplier of 2
Mon Nov 22 12:26:30 2004
using a sieve bound of 1561013 (59333 primes)
using large prime bound of 124881040
using double large prime bound of 374708557664960
restarting from polynomial 3887
restarting with 551 full and 21721 partial relations

sieving in progress (press Ctrl-C to pause)

found 595 relations (576 full + 19 partial), need 59461
found 620 relations (601 full + 19 partial), need 59461
|
|
found 59347 relations (15391 full + 43956 partial), need 59461
found 59485 relations (15416 full + 44069 partial), need 59461
begin with 617313 relations
reduce to 129143 relations in 10 passes
attempting to read 15416 full and 129143 partial relations
recovered 15416 full and 129143 partial relations
recovered 82452 polynomials
attempting to build 44069 cycles
found 44069 cycles in 6 passes
distribution of cycle lengths:
length 2 : 11620
length 3 : 10547
length 4 : 8069
length 5 : 5839
length 6 : 3465
length 7 : 2124
length 8 : 1176
length 9+: 1229
Mon Nov 22 15:03:35 2004
59333 x 59397 system, weight 3547184 (avg 59.72/col)
reduce to 58097 x 58161 in 3 passes
lanczos halted after 920 iterations
recovered 63 nontrivial dependencies
Mon Nov 22 15:04:17 2004
probable prime factor: 130049905380069045841413544182676651433512507
probable prime factor: 743507790479100314596230492599016928949651051
Mon Nov 22 15:04:36 2004
9433.898u 32.982s 2:38:07.13 99.7% 76+57772k 21+353io 7pf+0w
gigabyte#
gigabyte#
gigabyte#

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/
/******************************************************************************/

[jasonp]

Originally Posted by error404

Jason,
I re-tested tst300_c89 on my AMD64 and it works correctly.

I think it's more likely that the segfault was data driven; the
program chooses a new random seed every time it's invoked,
otherwise the behavior during a restart would fail.

I think the next version will have to print out the random number
seeds that are used; it would be the only way to make runs
deterministic on different machines.

jasonp

[jasonp]

Version 0.82 is now available. The choice of small prime multiplier
may be different with this version, but the real reason for the release
was so that the program can print out its version number and the
the seeds used in the random number generator. This should help
me track down problems others notice, since knowing the seeds used
makes the output completely deterministic.

I've also posted a tiny utility which can build random integers that
are the product of two large primes (win32 binary included with source).
This is going to go into a script that just factors numbers at random,
in the hope of tripping over bugs.

It would be really helpful, especially with the holidays coming up here
in the U.S., if you guys can volunteer some time and computer power
to run scripts and batch files that exercise this program. I think at this
point that 85-93 digit factorizations would be best, since these are pretty
stressful but can still finish in 2-7 hours on a modern machine.

I appreciate all the feedback everyone's provided, and look forward to
better code because of it.

jasonp

[antiroach]

im currently finishing up some trial factoring for LMH, and i'd be willing to donate some time to your program. I'm currently running mandrake 10.0 on an axp2500+ amd with 512 megs of ram. hopefully thats decent enough. i dont know all that much about linux (or scripts for that matter) so instructions to get the scripts running correctly would be appreciated.

Peter Z.

[jasonp]

Originally Posted by antiroach

im currently finishing up some trial factoring for LMH, and i'd be willing to donate some time to your program. I'm currently running mandrake 10.0 on an axp2500+ amd with 512 megs of ram. hopefully thats decent enough. i dont know all that much about linux (or scripts for that matter) so instructions to get the scripts running correctly would be appreciated.

Peter,

Your machine is plenty good enough. The easiest way I can think to get
started would be

1. compile the factoring code
2. compile makenum (from the same web page)
3. put this in a script, say 'factor.sh':

for digits in  86 87 88 89
do
       for reps in 1 2 3 4 5 6
       do
                msieve `makenum $digits | tail -1`
       done
done

4. Run the script with "sh factor.sh"

This will run a half dozen factorizations of random numbers of size
86, 87, 88 and 89 digits. Save all the output, and if there's a crash
or things hang or whatever, just post or PM the text of the factorization
that ran into trouble. Hopefully I'll be able to reproduce the behavior here
based on the output.

Note that you can get a lot fancier with this, e.g. detect segfaults
and save the intermediate files, but honestly my knowledge of scripts
is pretty basic too.

Thanks for the offer.
jasonp

[antiroach]

hey i've gotten it compiled and started running some tests. an 86 digit input took about 90 minutes. this is on a p4 2.8ghz xeon (work machine). I got bored waiting for those tests to finish :) so i started running tests of smaller numbers (40 digits) and I have gotten a few segfaults. I dont know whether this is because 40 digit numbers are too small to be factored correctly with your algorithm, but anyways here are the inputs i used to generate the segfaults.

input: line 36: 29433 Segmentation fault      ./msieve 7324240144379174059434641613119391167191
input: line 48: 29445 Segmentation fault      ./msieve 9302175042894760818265027291131285148871
input: line 65: 29462 Segmentation fault      ./msieve 5094880345742071192495064652057281785211
input: line 69: 29466 Segmentation fault      ./msieve 3587404706653786146945992996387341023503
input: line 80: 29477 Segmentation fault      ./msieve 5746345230654144388630375650394461654587

all the input numbers were generated with the makenum utility.

[andi314]

i didt have any problem to factor the numbers above. my system consists of a P4 2 Ghz and Win 98

[antiroach]

here are some more segfaults: this time with 60 digit numbers

input: line 4: 30316 Segmentation fault      (core dumped) ./msieve 246704619195053877572007219091064430900448630898569586802521
input: line 7: 30320 Segmentation fault      (core dumped) ./msieve 484054488827794160344286285393974850468279770179691024066643
input: line 46: 30445 Segmentation fault      (core dumped) ./msieve 440672358677983028973687493226653503891194874493246108297451
input: line 49: 30456 Segmentation fault      (core dumped) ./msieve 454446361945072169743019924655176830178364330800771673792727
input: line 54: 30470 Segmentation fault      (core dumped) ./msieve 491075036806262663565079779961191377170875736352425434156517
input: line 57: 30474 Segmentation fault      (core dumped) ./msieve 393912258506565059207528264769349617479949041426255710396499
input: line 60: 30477 Segmentation fault      (core dumped) ./msieve 494036278069539417980440944541928892572494600288276166789471

[antiroach]

and now with 50 digits. its going to be my last batch for now. this should give you something to chew on :)

input: line 9: 31966 Segmentation fault      (core dumped) ./msieve 109689917828520751863101914264391209936211233655221
input: line 45: 32022 Segmentation fault      (core dumped) ./msieve 124043121877431601633440722191516759818060589870099
input: line 56: 32033 Segmentation fault      (core dumped) ./msieve 110129843048702631952351570410469796550322969576799
input: line 83: 32070 Segmentation fault      (core dumped) ./msieve 120317906010151429063863198553026268467411171049459
input: line 86: 32073 Segmentation fault      (core dumped) ./msieve 78991692285819737038363303800132765146100949792729

[jasonp]

Originally Posted by antiroach

and now with 50 digits. its going to be my last batch for now. this should give you something to chew on :)

<sigh> This will teach me to add new features while looking for bugs.

Version 0.83 fixes this particular bug, a side effect of the new stuff
in the previous release.

Sorry 'bout that.
jasonp

[antiroach]

cool. i'll check this version out in a couple of days ( im leaving for thanksgiving break tomorrow )