Msieve 0.87 available
 

New version just uploaded. Highlights include:

- big changes in the sieving stage, that are very complicated but
provide a hefty speedup. Most of my QA factorizations are 15-20%
faster, but my c100 test case is almost twice as fast, just 17.5 hours.
I personally think it's a fluke number; only other factorizations will tell

- a different (regrettably incompatible) savefile format that greatly
reduces the size of savefiles

- batch mode

- a Makefile

- several small bug fixes, lots of new documentation

Happy factoring,
jasonp

[QUOTE]That information can be inferred from the timestamps sprinkled through
the output. It looks like ~39 hours.

Maybe I can take a lesson from ppsiqs.exe, which saves durations in
its savefiles, and can give you an accurate runtime even if it was halted
during the run.[/QUOTE]

I know the total runtime can be taken from the log, but it would take the program probably not more than a few miliseconds to calculate the ellapsed time.

Of course, keeping track of the runtime in the save file would be even better. I have 1 or 2 slow cpu's which take days to do a factorization. It would be great to see how long the factorization actually took, even afetr interuptions.

I'll try the new version tonight

[QUOTE=smh]What cpu was used?

Jason, can you make a next version print the time it took to do the factorization?[/QUOTE]

I used a "part-time" Athlon 2100+ XP :-P

Luigi

[QUOTE=jasonp]New version just uploaded. Highlights include:

- big changes in the sieving stage, that are very complicated but
provide a hefty speedup. Most of my QA factorizations are 15-20%
faster, but my c100 test case is almost twice as fast, just 17.5 hours.
I personally think it's a fluke number; only other factorizations will tell

- a different (regrettably incompatible) savefile format that greatly
reduces the size of savefiles

- batch mode

- a Makefile

- several small bug fixes, lots of new documentation

Happy factoring,
jasonp[/QUOTE]

This means that I can't interrupt my sieving started with msieve 0.86 and continue it with version 0.87... :sad:

Luigi

Another question: did anybody test the Win32 binaries on a P4? it seems far slower than running it on an Athlon...

If no one did, I'll try and compile a P4 0.87 version under Cygwin.

Luigi

[QUOTE=ET_]Another question: did anybody test the Win32 binaries on a P4? it seems far slower than running it on an Athlon...

If no one did, I'll try and compile a P4 0.87 version under Cygwin.
[/QUOTE]
Msieve is way too slow on a P4. Fixing that (if possible) would require
a lot of quality time with one. Of course if you could get the core sieving
code to use SSE2 (or MMX or Altivec or whatever) not only would it help
a great deal, it would probably be worth a publication.

To answer your other question, 0.87 unfortunately cannot restart with
0.86's savefiles.

For the record, I have two other c100's underway, and they're ~40% done
after 13 hours. So my superfast c100 time appears to be a fluke.

jasonp

106 415 has a factor ...
 

Hi Jason,

I used three different computers for my first try with 0.87 and
everything worked correctly.


SIQS found P48 and P49.
[code]
Factorizations of Cyclotomic Numbers
[url]http://www.asahi-net.or.jp/~KC2H-MSM/cn/index.htm[/url]

(106 415 (107 513939941 2139265982831 365899366084796321) (C 96))

g4-867:~/Desktop/QS08 k5gj$ ./cyclotomic 106 415
13723212714764211893842571979805577519813962098426765325603587556197131075045661485623535541141156032235662096332781892180299529662499061
g4-867:~/Desktop/QS08 k5gj$

n = 13723212714764211893842571979805577519813962098426765325603587556197131075045661485623535541141156032235662096332781892180299529662499061
w = n ÷ 107;
x = w ÷ 513939941;
y = x ÷ 2139265982831;
z = y ÷ 365899366084796321

Out[2]:= 318810931824350089603496873449091927715882749575887966364423318942890168072543614241539805612253
Out[3]:= False
Out[4]:= 96

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

Gigabyte GA-K8VT800M motherboard (AMD64-3400+)
K8-2200, 64K L1, 1M L2, BUS 200 MHz, 2048M DDR400 PC3200

gigabyte# uname -a
FreeBSD gigabyte.dl.cox.net 5.3-RELEASE-p2 FreeBSD 5.3-RELEASE-p2 #0: Sun Dec 5 13:02:41 CST 2004
[email]root@gigabyte.dl.cox.net[/email]:/usr/src/sys/amd64/compile/MYKERNEL amd64
gigabyte#
gigabyte#
gigabyte# gcc40 -v Reading specs from /usr/local/lib/gcc/x86_64-portbld-freebsd5.3/4.0.0/specs
Configured with: ./..//gcc-4.0-20041128/configure --disable-nls --with-system-zlib --with-libiconv-prefix=/usr/local --program-suffix=40 --with-gxx-include-dir=/usr/local/lib/gcc/x86_64-portbld-freebsd5.3/4.0.0/include/c++/ --disable-shared --disable-libgcj --prefix=/usr/local x86_64-portbld-freebsd5.3
Thread model: posix
gcc version 4.0.0 20041128 (experimental) [FreeBSD]
gigabyte#
gigabyte#
gigabyte# gcc40 -O3 -march=k8 -m64 *.c -o qs087 -lm
gigabyte#
gigabyte#
gigabyte#
gigabyte# ./qs087 < c96.txt

Msieve v. 0.87
random seeds: 00000255 41bb66dd
input to factor: factoring 318810931824350089603496873449091927715882749575887966364423318942890168072543614241539805612253
Sat Dec 11 15:30:05 2004
using multiplier of 1
Sat Dec 11 15:30:07 2004
using sieve block of 65536
using a sieve bound of 1753069 (65882 primes)
using large prime bound of 308540144
using double large prime bound of 1908802421804784

sieving in progress (press Ctrl-C to pause)
found 6 relations (6 full + 0 partial), need 66010
found 11 relations (11 full + 0 partial), need 66010
|
|
found 4715 relations (3753 full + 962 partial), need 66010
found 4723 relations (3758 full + 965 partial), need 66010
^C
received signal 2; shutting down
found 4744 relations (3776 full + 968 partial), need 66010
found 4744 relations (3776 full + 968 partial), need 66010
Sat Dec 11 18:02:16 2004
gigabyte#




Motorola PPc-7455 (Titanium)
G4-867, 256K L2, 1M L3, 768M PC133, Bus 133MHz

g4-867:~/Desktop/QS08 k5gj$ uname -a
Darwin g4-867.k5gj 7.6.0 Darwin Kernel Version 7.6.0: Sun Oct 10 12:05:27 PDT 2004; root:xnu/xnu-517.9.4.obj~1/RELEASE_PPC Power Macintosh powerpc
g4-867:~/Desktop/QS08 k5gj$
g4-867:~/Desktop/QS08 k5gj$
g4-867:~/Desktop/QS08 k5gj$ /usr/local/bin/gcc34 -v
Reading specs from /usr/local/lib/gcc/powerpc-apple-darwin7.6.0/3.4.4/specs
Configured with: /usr/gcc-3.4-20041119/./configure --program-suffix=34 --enable-languages=c --disable-nls
Thread model: posix
gcc version 3.4.4 20041119 (prerelease)
g4-867:~/Desktop/QS08 k5gj$
g4-867:~/Desktop/QS08 k5gj$
g4-867:~/Desktop/QS08 k5gj$ /usr/local/bin/gcc34 -O3 -mtune=7450 *.c -o qs087
g4-867:~/Desktop/QS08 k5gj$
g4-867:~/Desktop/QS08 k5gj$
g4-867:~/Desktop/QS08 k5gj$
g4-867:~/Desktop/QS08 k5gj$ ./qs087 < c96.txt

Msieve v. 0.87
random seeds: 00000246 41bb59b0
input to factor: factoring 318810931824350089603496873449091927715882749575887966364423318942890168072543614241539805612253
Sat Dec 11 14:33:52 2004
using multiplier of 1
Sat Dec 11 14:33:59 2004
using sieve block of 32768
using a sieve bound of 1753069 (65882 primes)
using large prime bound of 308540144
using double large prime bound of 1908802421804784

sieving in progress (press Ctrl-C to pause)
^Cund 2341 relations (2094 full + 247 partial), need 66010
received signal 2; shutting down
found 2353 relations (2101 full + 252 partial), need 66010
Sat Dec 11 18:07:05 2004
g4-867:~/Desktop/QS08 k5gj$

concatenate msieve.dat files

g4-867:~/Desktop/QS08 k5gj$
g4-867:~/Desktop/QS08 k5gj$ ./qs087 < c96.txt

Msieve v. 0.87
random seeds: 00000290 41bb8bed
input to factor: factoring 318810931824350089603496873449091927715882749575887966364423318942890168072543614241539805612253
Sat Dec 11 18:08:13 2004
using multiplier of 1
Sat Dec 11 18:08:20 2004
using sieve block of 32768
using a sieve bound of 1753069 (65882 primes)
using large prime bound of 308540144

using double large prime bound of 1908802421804784
restarting with 5877 full and 402999 partial relations

sieving in progress (press Ctrl-C to pause)
found 8899 relations (5963 full + 2936 partial), need 66010
^C
found 13314 relations (7690 full + 5624 partial), need 66010
received signal 2; shutting down
found 13332 relations (7695 full + 5637 partial), need 66010
Sat Dec 11 20:55:35 2004
k5gj-s-Computer:~/Desktop/QS08 k5gj$




ASUS K8V-SE motherboard (AMD64-3400+)
K8-2200, 64K L1, 1M L2, CPU BUS 200 MHz, 512M DDR400 PC3200

root@k8-2200 QS08]# uname -a
Linux k8-2200.k5gj 2.6.9-1.681_FC3 #1 Thu Nov 18 15:13:22 EST 2004 x86_64 x86_64 x86_64 GNU/Linux
[root@k8-2200 QS08]#
[root@k8-2200 QS08]#
[root@k8-2200 QS08]# gcc -v
Reading specs from /usr/lib/gcc/x86_64-redhat-linux/3.4.2/specs
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --enable-shared --enable-threads=posix --disable-checking --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-languages=c,c++,objc,java,f77 --enable-java-awt=gtk --host=x86_64-redhat-linux
Thread model: posix
gcc version 3.4.2 20041017 (Red Hat 3.4.2-6.fc3)
[root@k8-2200 QS08]#
[root@k8-2200 QS08]#
[root@k8-2200 QS08]# gcc -O3 -march=k8 -m64 *.c -o qs087 -lm
[root@k8-2200 QS08]#
[root@k8-2200 QS08]#
[root@k8-2200 QS08]#
[root@k8-2200 QS08]# ./qs087 < c96.txt

Msieve v. 0.87
random seeds: 00000d6a 41bbb3ad
input to factor: factoring 318810931824350089603496873449091927715882749575887966364423318942890168072543614241539805612253
Sat Dec 11 20:57:49 2004
using multiplier of 1
Sat Dec 11 20:57:51 2004
using sieve block of 65536
using a sieve bound of 1753069 (65882 primes)
using large prime bound of 308540144
using double large prime bound of 1908802421804784
restarting with 7695 full and 525317 partial relations

sieving in progress (press Ctrl-C to pause)
found 13354 relations (7702 full + 5652 partial), need 66010
found 13373 relations (7708 full + 5665 partial), need 66010
|
|
found 66068 relations (15735 full + 50333 partial), need 66010
found 66068 relations (15735 full + 50333 partial), need 66010
begin with 1076476 relations
reduce to 158295 relations in 12 passes
attempting to read 15735 full and 158295 partial relations
recovered 15735 full and 158295 partial relations
recovered 170771 polynomials
attempting to build 50333 cycles
found 50333 cycles in 6 passes
distribution of cycle lengths:
length 2 : 11635
length 3 : 11309
length 4 : 8941
length 5 : 6815
length 6 : 4494
length 7 : 3015
length 8 : 1769
length 9+: 2355
largest cycle: 20 relations
Sun Dec 12 00:34:45 2004
65882 x 65946 system, weight 4453463 (avg 67.53/col)
reduce to 64976 x 65040 in 3 passes
lanczos halted after 1029 iterations
recovered 63 nontrivial dependencies
Sun Dec 12 00:35:34 2004
probable prime factor: 205177732079223834923136958397065641086927780129
probable prime factor: 1553828130341405013222404004541918319450603908157
Sun Dec 12 00:35:57 2004
[root@k8-2200 QS08]#

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

n = 205177732079223834923136958397065641086927780129 * 1553828130341405013222404004541918319450603908157
Out[2]:= 318810931824350089603496873449091927715882749575887966364423318942890168072543614241539805612253
Out[3]:= False
Out[4]:= 96

/******************************************************************************/
/******************************************************************************/
/******************************************************************************/[/code]

Suggestion regarding posting log files
 

Hi all!

I would suggest that all who publishes a log file from a factorization puts the log inside a CODE environment, like I did in post #20. This is done by marking all the text from the factorization and pressing the button with a # on it.

That way a post won't be several screens long to read.


-----
Cheers,
Jes

[QUOTE=JHansen]Hi all!

I would suggest that all who publishes a log file from a factorization puts the log inside a CODE environment, like I did in post #20. This is done by marking all the text from the factorization and pressing the button with a # on it.

That way a post won't be several screens long to read.
[/QUOTE]

Agreed, so i took the liberty to do this for the post on the last page of this thread.

William, Alex and Paul:

You're absolutely right, I have to excuse for any confusion I might have been responsible for. I absent-mindedly thought that P-1 is slower than ECM and concluded the rest of my posting by logic (which was based on wrong assumptions).
Thanks for pointing this out!

Continued development?
 

So it looks like the basics are all there for Msieve, and AFAICT it's
loads faster than other QS programs. Where do I go from here?

I've gotten a few suggestions for usability improvements, most of
which are easy and can be folded into the next release. If I think
of another idea to speed up sieving or somebody trips over a bug,
it'll definitely cause a new version. What I'm not sure of is whether
it's worth everyone's time to continue hardcore development of the
core code.

According to Paul's 3-large-prime QS paper, the speedup to expect
from going to 3 large primes is a factor of ~1.7 when the input is
large enough. Problem is, 'large enough' may well be past the point
where Msieve will always be slower than using GGNFS. I estimate
that point to be ~103 digits right now, since for numbers that size
Msieve takes ~3 days and GGNFS takes maybe 2-3 days. Adding
3LP support can maybe move the crossover point to 105-106 digits.
And GGNFS is under constant development; it already eats numbers
this small for breakfast.

Is it worth the effort? There are no geek points available (though it
flatters me) for spending weeks running my code when you could
spend days running somebody else's. And before you rush ahead and
say 'go for it!' because it costs you nothing to do so, realize that when
I'm in the middle of this stuff I get *very* obsessed about it. Everything
that's not my day job gets put on hold. Not that I mind (or else I wouldn't
do it), but understand that changing algorithmic stuff in there is hard.

What do you think?
jasonp