I have a small request. When I get the "input number: " prompt and hit CTRL-C, I expect it to exit the program, but it doesn't.

[QUOTE=rogue]I have a small request. When I get the "input number: " prompt and hit CTRL-C, I expect it to exit the program, but it doesn't.[/QUOTE]
In dos/windows, end-of-file is Ctrl-Z; on unix it's Ctrl-D

jasonp

Here comes another one...
 

[code]
Msieve v. 0.87
random seeds: 000001fc 41be0cc4
input to factor: 5447289338864472927243448607468658081251135947850949772790467166469928349644701839663731230742873013
factoring 5447289338864472927243448607468658081251135947850949772790467166469928349644701839663731230742873013
Mon Dec 13 22:44:37 2004
using multiplier of 17
Mon Dec 13 22:44:40 2004
using sieve block of 65536
using a sieve bound of 1872109 (69737 primes)
using large prime bound of 561632700
using double large prime bound of 5610664057485900
restarting with 8821 full and 963595 partial relations


sieving in progress (press Ctrl-C to pause)
found 69867 relations (14272 full + 55595 partial), need 69865
begin with 1551322 relations
reduce to 185068 relations in 13 passes
attempting to read 14272 full and 185068 partial relations
recovered 14272 full and 185068 partial relations
recovered 198146 polynomials
attempting to build 55595 cycles
found 55595 cycles in 6 passes
distribution of cycle lengths:
length 2 : 10969
length 3 : 11120
length 4 : 9527
length 5 : 7809
length 6 : 5787
length 7 : 3904
length 8 : 2674
length 9+: 3805
largest cycle: 21 relations
Tue Dec 14 12:12:21 2004
69737 x 69801 system, weight 5482920 (avg 78.55/col)
reduce to 69279 x 69343 in 3 passes
lanczos halted after 1097 iterations
recovered 63 nontrivial dependencies
Tue Dec 14 12:17:34 2004
probable prime factor: 3208235231710883908961152859635693
probable prime factor: 1697908334470708021901025974443863788322035419494645824909356747241
Tue Dec 14 12:18:52 2004
[/code]

Fun, fun, fun! :banana: :banana: :banana:

Luigi

Jason, couldn't you please make msieve report how large the input number is again?

That way, one doesn't have to count all the digits when someone posts a new factorization to see how difficult it were :rolleyes:


-----
Cheers,
Jes

[QUOTE=JHansen]Jason, couldn't you please make msieve report how large the input number is again?[/QUOTE]

You could also count the digits in each found factor.

BTW, great program. I now use it to factor composite P-1 factors reported to GIMPS.

[QUOTE=Prime95]You could also count the digits in each found factor.

BTW, great program. I now use it to factor composite P-1 factors reported to GIMPS.[/QUOTE]
Thanks. How big do these numbers typically get?

jasonp

[QUOTE=jasonp]Thanks. How big do these numbers typically get?
[/QUOTE]

Typically 40 to 55 digits. A piece of cake for your program.

[QUOTE=jasonp]Correct operation requires Y, Y1 and Y2 to all be the same. Some
of the published reports from big factorizations, however, have all
these numbers different. If Y2 > Y1 you have a memory leak at best,
and possibly a buffer overflow.[/QUOTE]
Hm, I found one discrepancy out of maybe 50 logs I have recorded:

[CODE]$ time ./msieve <C90

Msieve v. 0.87
random seeds: 000007d0 41baf5a9
input to factor:
sieving in progress (press Ctrl-C to pause)
factoring 800790538656199724932326858750778010792401786888920397784467728148733777821289449154842409
Sat Dec 11 08:27:05 2004
using multiplier of 1
Sat Dec 11 08:27:07 2004
using sieve block of 32768
using a sieve bound of 1593607 (59982 primes)
using large prime bound of 133862988
using double large prime bound of 424608712731420

found 60201 relations (16310 full + 43891 partial), need 60110
begin with 641430 relations
reduce to 127060 relations in 10 passes
attempting to read 16310 full and 127060 partial relations
recovered 16310 full and 127060 partial relations
recovered 136487 polynomials
attempting to build 43891 cycles
found 43890 cycles in 4 passes
distribution of cycle lengths:
length 2 : 12547
length 3 : 10862
length 4 : 8031
length 5 : 5276
length 6 : 3234
length 7 : 1862
length 8 : 1018
length 9+: 1060
largest cycle: 16 relations
Sat Dec 11 11:15:47 2004
59982 x 60046 system, weight 3337928 (avg 55.59/col)
reduce to 58409 x 58473 in 3 passes
lanczos halted after 925 iterations
recovered 61 nontrivial dependencies
Sat Dec 11 11:16:41 2004
probable prime factor: 587779282137510502067613864046350351066692399
probable prime factor: 1362400076001412051240719643739195403767325991
Sat Dec 11 11:17:16 2004


input to factor:
real 170m10.812s
user 0m0.010s
sys 0m0.010s[/CODE]
Y2 < Y1 here, so is this something to worry about? This was using mingw-gcc-3.4.2 on WinXP.

[CODE]SamAdmin@OLLIN ~/siqs
$ gcc -v
Reading specs from c:/mingw/bin/../lib/gcc/mingw32/3.4.2/specs
Configured with: ../gcc/configure --with-gcc --with-gnu-ld --with-gnu-as --host=mingw32 --target=mingw32 --prefix=/mingw --enable-threads --disable-nls --enable-languages=c,c++,f77,ada,objc,java --disable-win32-registry --disable-shared --enable-sjlj-exceptions --enable-libgcj --disable-java-awt --without-x --enable-java-gc=boehm --disable-libgcj-debug --enable-interpreter --enable-hash-synchronization --enable-libstdcxx-debug
Thread model: win32
gcc version 3.4.2 (mingw-special)[/CODE]
and Makefile settings

[CODE]
OPT_FLAGS = -O3 -ftracer -fweb -fomit-frame-pointer
MACHINE_FLAGS = -march=pentium-m -pipe[/CODE]

[QUOTE=jasonp]
<sigh> This is hard enough without having to fight one's tools.
[/QUOTE]
Eh... I wouldn't draw too many conclusions from running beta compilers.

Incidentally I find it interesting how much differences in the random seed can affect runtime. The following was on a P3-450 running Gentoo Linux.

[CODE]sam@krang siqs $ rm msieve.dat
sam@krang siqs $ time echo 314159265358979323846264338328907078125461821459237067283727 | ./msieve-gcc343

Msieve v. 0.87
random seeds: 00006fc1 41bfb369
input to factor: factoring 314159265358979323846264338328907078125461821459237067283727
Tue Dec 14 22:45:45 2004
using multiplier of 3
Tue Dec 14 22:45:46 2004
using sieve block of 16384
using a sieve bound of 56527 (2882 primes)
using large prime bound of 2769823


sieving in progress (press Ctrl-C to pause)
found 3700 relations (1632 full + 2068 partial), need 3010
begin with 15216 relations
reduce to 3814 relations in 2 passes
attempting to read 1632 full and 3814 partial relations
recovered 1632 full and 3814 partial relations
recovered 4425 polynomials
attempting to build 2068 cycles
found 2068 cycles in 1 passes
distribution of cycle lengths:
length 2 : 2068
largest cycle: 2 relations
Tue Dec 14 22:48:12 2004
2882 x 2946 system, weight 71382 (avg 24.23/col)
reduce to 2717 x 2781 in 3 passes
lanczos halted after 44 iterations
recovered 61 nontrivial dependencies
Tue Dec 14 22:48:12 2004
probable prime factor: 314159265358979323846264338311
probable prime factor: 1000000000000000000000000000057
Tue Dec 14 22:48:16 2004


input to factor:
real 2m30.976s
user 2m30.795s
sys 0m0.161s
sam@krang siqs $ rm msieve.dat
sam@krang siqs $ time echo 314159265358979323846264338328907078125461821459237067283727 | ./msieve-gcc343

Msieve v. 0.87
random seeds: 00007013 41bfb977
input to factor: factoring 314159265358979323846264338328907078125461821459237067283727
Tue Dec 14 23:11:35 2004
using multiplier of 3
Tue Dec 14 23:11:35 2004
using sieve block of 16384
using a sieve bound of 56527 (2882 primes)
using large prime bound of 2769823


sieving in progress (press Ctrl-C to pause)
found 3176 relations (1421 full + 1755 partial), need 3010
begin with 13646 relations
reduce to 3263 relations in 2 passes
attempting to read 1421 full and 3263 partial relations
recovered 1421 full and 3263 partial relations
recovered 3854 polynomials
attempting to build 1755 cycles
found 1755 cycles in 1 passes
distribution of cycle lengths:
length 2 : 1755
largest cycle: 2 relations
Tue Dec 14 23:13:47 2004
2882 x 2946 system, weight 74163 (avg 25.17/col)
reduce to 2725 x 2789 in 3 passes
lanczos halted after 45 iterations
recovered 63 nontrivial dependencies
Tue Dec 14 23:13:47 2004
probable prime factor: 314159265358979323846264338311
probable prime factor: 1000000000000000000000000000057
Tue Dec 14 23:13:52 2004


input to factor:
real 2m16.778s
user 2m16.595s
sys 0m0.159s
[/CODE]
:surprised

[QUOTE=trilliwig]
Hm, I found one discrepancy out of maybe 50 logs I have recorded:

[...]

Y2 < Y1 here, so is this something to worry about? This was using mingw-gcc-3.4.2 on WinXP.
[/QUOTE]
Not really, it just means your factorization finished a little too soon.
But if the current stable 3.4 version is 3.4.3 then it would be nice to
find a fix; I've seen factorization logs where Y2 > (Y + 2500), meaning
the factorization needlessly ran 4% longer.

Anyway, if I can't find a way to trick the compiler into working then
avoiding memory leaks and crashes is easy. The next version will certainly
have safeguards in place.

[QUOTE=trilliwig]
Incidentally I find it interesting how much differences in the random seed can affect runtime. The following was on a P3-450 running Gentoo Linux.
[/QUOTE]

I think the cache blocking introduced in 0.87 is too aggressive for Intel
CPUs; the next version will have to scale it back somewhat for them.

That being said, the exact rate that relations are found depends on the
(random) polynomials that are chosen, and for a C60 only a few polynomials
are needed. As the input size goes up the number of polynomials needed
goes through the roof, and individual differences in polynomials average out.
Or it's an indication that polynomials are not being chosen carefully
enough :smile:

jasonp

C103 factorization + question
 

Hi. Here's another success story from the XYYXF project. The number is C103_138_11:

[CODE]Msieve v. 0.87
random seeds: 00000998 41bf582e
input to factor: 112922758178357135520496934132883414874783775714138391298075021
6109454329382963228217542471269383126751
factoring 1129227581783571355204969341328834148747837757141383912980750216109454
329382963228217542471269383126751
Tue Dec 14 22:16:37 2004
using multiplier of 3
Tue Dec 14 22:16:39 2004
using sieve block of 65536
using a sieve bound of 1948799 (72436 primes)
using large prime bound of 584639700
using double large prime bound of 6031133206325100
restarting with 10669 full and 1187986 partial relations


sieving in progress (press Ctrl-C to pause)
found 72625 relations (14728 full + 57897 partial), need 72564
begin with 1618243 relations
reduce to 192986 relations in 12 passes
attempting to read 14728 full and 192986 partial relations
recovered 14728 full and 192986 partial relations
recovered 206941 polynomials
attempting to build 57897 cycles
found 57897 cycles in 6 passes
distribution of cycle lengths:
length 2 : 11210
length 3 : 11578
length 4 : 9902
length 5 : 8150
length 6 : 6017
length 7 : 4078
length 8 : 2867
length 9+: 4095
largest cycle: 21 relations
Wed Dec 15 09:06:33 2004
72436 x 72500 system, weight 5131685 (avg 70.78/col)
reduce to 72002 x 72066 in 3 passes
lanczos halted after 1140 iterations
recovered 62 nontrivial dependencies
Wed Dec 15 09:09:38 2004
probable prime factor: 39379355524455995913392108042042787203
probable prime factor: 286756237308729041649442902251929351660196434166564351058
39808117
Wed Dec 15 09:10:35 2004[/CODE]

The savefile was 117MB.

As you can see, it only takes a few minutes to finish the 72K X 72K matrix. It took a [I]lot[/I] longer to find the relations though (I don't know exactly how long. I've used two computers for this).

Is it possible to shift some of the workload away from the sieving and over to the matrix? What if one used a factorbase twice as large as the current one for factorizations over 90 digits? How would that affect the sieving time?

-----
Cheers,
Jes

[QUOTE=JHansen]Hi. Here's another success story from the XYYXF project. The number is C103_138_11:

[...]

As you can see, it only takes a few minutes to finish the 72K X 72K matrix. It took a [I]lot[/I] longer to find the relations though (I don't know exactly how long. I've used two computers for this).

Is it possible to shift some of the workload away from the sieving and over to the matrix? What if one used a factorbase twice as large as the current one for factorizations over 90 digits? How would that affect the sieving time?
[/QUOTE]
I experimented with doing that for a random C95. Making the factor base
50% larger increases the speed at which smooth relations are found, but
because 50% more relations are needed the sieving stage takes about
the same time it did before. The variation was literally 5 minutes in a six
hour sieving run.

I haven't repeated the exercise with larger numbers; like Paul said, data
points take a long time to generate. Practically speaking, when the double
large prime effect hits full force then an extra 10000 relations take only
a little longer toward the end of the factorization. This is what I meant
when I said that QS was forgiving of suboptimal parameter choices.

jasonp