Msieve v. 1.47 and 148 digit composite

Just a quick question to see if I am doing some thing very wrong or if all is well, I can not tell.

Here is the situation. I compiled Msieve v. 1.47 on an AMD Opteron server running Solaris 10 while using the Sun Studio 12 compiler tools to get reasonably optimal binaries. I did take advantage of the optimized math libs also with -llibmopt and interdependecy issues with -xdepend and -xO4.

The resultant binary seems to be able to factor some smaller numbers thus :

# uname -a
SunOS ganymede 5.10 Generic_142901-14 i86pc i386 i86pc
# psrinfo -pv
The physical processor has 1 virtual processor (0)
  x86 (AuthenticAMD family 15 model 5 step 10 clock 2389 MHz)
        AMD Opteron(tm) Processor 250
The physical processor has 1 virtual processor (1)
  x86 (AuthenticAMD family 15 model 5 step 10 clock 2389 MHz)
        AMD Opteron(tm) Processor 250
# prtconf | grep Memory
Memory size: 4032 Megabytes

# ptime ./msieve -s test000.dat -l test000.log -mb 256 -v -t 4 -e 32853323250096457284572454292875769988101705814723784759331132642166464814574883

Msieve v. 1.47
Fri Oct  1 22:34:12 2010
random seeds: 8403adef 6e386af1
factoring 32853323250096457284572454292875769988101705814723784759331132642166464814574883 (80 digits)
no P-1/P+1/ECM available, skipping
commencing quadratic sieve (80-digit input)
using multiplier of 3
using 64kb Opteron sieve core
sieve interval: 6 blocks of size 65536
processing polynomials in batches of 17
using a sieve bound of 1257247 (48647 primes)
using large prime bound of 125724700 (26 bits)
using trial factoring cutoff of 27 bits
polynomial 'A' values have 10 factors

sieving in progress (press Ctrl-C to pause)
48952 relations (25405 full + 23547 combined from 260847 partial), need 48743
48952 relations (25405 full + 23547 combined from 260847 partial), need 48743
sieving complete, commencing postprocessing
begin with 286251 relations
reduce to 69524 relations in 2 passes
attempting to read 69524 relations
recovered 69524 relations
recovered 58338 polynomials
attempting to build 48952 cycles
found 48952 cycles in 1 passes
distribution of cycle lengths:
   length 1 : 25405
   length 2 : 23547
largest cycle: 2 relations
matrix is 48647 x 48952 (7.1 MB) with weight 1476770 (30.17/col)
sparse part has weight 1476770 (30.17/col)
filtering completed in 3 passes
matrix is 34325 x 34387 (5.5 MB) with weight 1160670 (33.75/col)
sparse part has weight 1160670 (33.75/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 34277 x 34387 (3.7 MB) with weight 874177 (25.42/col)
sparse part has weight 632541 (18.39/col)
using block size 13710 for processor cache size 1024 kB
commencing Lanczos iteration
memory use: 2.1 MB
lanczos halted after 543 iterations (dim = 34277)
recovered 18 nontrivial dependencies
prp36 factor: 633691810707436654263765898525306957
prp44 factor: 51844323526005302967016436897551020246371119
elapsed time 00:09:18

real     9:17.529
user     9:16.908
sys         0.246
#

This looks correct and may even be reasonable quick. Again I am not sure.

To perform a common sense check I compiled the sources on a very very old 400 MHz Pentium III based machine and then ran the exact same test thus :

$ psrinfo -v
Status of virtual processor 0 as of: 10/02/10 17:31:15
  on-line since 09/06/10 19:42:51.
  The i386 processor operates at 400 MHz,
        and has an i387 compatible floating point processor.
Status of virtual processor 1 as of: 10/02/10 17:31:15
  on-line since 09/06/10 19:42:55.
  The i386 processor operates at 400 MHz,
        and has an i387 compatible floating point processor.

$ uname -a
SunOS titan 5.8 Generic_127722-03 i86pc i386 i86pc
.
.
.
sparse part has weight 1162111 (33.80/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 34269 x 34381 (3.2 MB) with weight 872916 (25.39/col)
sparse part has weight 633029 (18.41/col)
using block size 13707 for processor cache size 512 kB
commencing Lanczos iteration
memory use: 2.1 MB
lanczos halted after 544 iterations (dim = 34267)
recovered 17 nontrivial dependencies
prp36 factor: 633691810707436654263765898525306957
prp44 factor: 51844323526005302967016436897551020246371119
elapsed time 02:25:58

real  2:25:58.901
user  2:25:53.696
sys         2.184

There we see that the very old baseline 400MHz Intel Pentium III processor ran the same factor test using 8758.901 secs. The newer and somewhat faster 64-bit AMD Opteron ran the same test in 557.529 secs. This is a speed increase factor of about 15.71 times. This is much better than just a clock speed factor of ( 2389MHz / 400MHz ) = 5.97. I'm happy with that.

So then I tried a larger number :

# ptime ./msieve -s test001.dat -l test001.log -v -t 4 5118112698665072812520866447773637877346372738061830362488665585404041331503549909040610381146134652023670197106080332578287665297420147584029320829


Msieve v. 1.47
Fri Oct  1 22:48:38 2010
random seeds: 7dfe5dce 69c85b6c
factoring 5118112698665072812520866447773637877346372738061830362488665585404041331503549909040610381146134652023670197106080332578287665297420147584029320829 (148 digits)
no P-1/P+1/ECM available, skipping
commencing quadratic sieve (148-digit input)
using multiplier of 13
using 64kb Opteron sieve core
sieve interval: 153 blocks of size 65536
processing polynomials in batches of 1
using a sieve bound of 36237749 (1109091 primes)
using large prime bound of 4294967295 (31 bits)
using double large prime bound of 218437776016143360 (51-58 bits)
using trial factoring cutoff of 58 bits
polynomial 'A' values have 16 factors

sieving in progress (press Ctrl-C to pause)

This has been running for many hours with no end in sight :

# prstat -R -n 10 -c 10
   PID USERNAME  SIZE   RSS STATE  PRI NICE      TIME  CPU PROCESS/NLWP
 24514 root      154M  147M cpu0     0    0  18:49:17  50% msieve/1
   420 daemon     10M 5448K sleep   59    0   7:26:26 0.4% rcapd/1
  4942 root     3384K 2624K cpu1   100    -   0:00:00 0.0% prstat/1
 13589 root     6156K 4548K sleep   58    0   0:01:11 0.0% snmpd/1
  9923 root       13M 7788K sleep    1    0   0:00:03 0.0% nscd/23
   505 root     2520K 1092K sleep   59    0   0:00:00 0.0% automountd/2
   503 daemon   5792K 1284K sleep   59    0   0:00:04 0.0% nfsmapid/4
   384 root     5064K 1988K sleep   59    0   0:00:00 0.0% syseventd/16
   389 root     6196K 3220K sleep   59    0   0:01:30 0.0% nscd/36
   302 root     6208K 3420K sleep   59    0   0:00:22 0.0% devfsadm/9
Total: 134 processes, 569 lwps, load averages: 1.02, 1.01, 1.01
   PID USERNAME  SIZE   RSS STATE  PRI NICE      TIME  CPU PROCESS/NLWP
 24514 root      154M  147M cpu0     0    0  18:49:27  50% msieve/1
   420 daemon     10M 5448K sleep   59    0   7:26:26 0.4% rcapd/1
  4942 root     3788K 3020K cpu1   100    -   0:00:00 0.0% prstat/1
 13589 root     6156K 4548K sleep   58    0   0:01:11 0.0% snmpd/1
  9923 root       13M 7788K sleep    1    0   0:00:03 0.0% nscd/23
   505 root     2520K 1092K sleep   59    0   0:00:00 0.0% automountd/2
   503 daemon   5792K 1284K sleep   59    0   0:00:04 0.0% nfsmapid/4
   384 root     5064K 1988K sleep   59    0   0:00:00 0.0% syseventd/16
   389 root     6196K 3220K sleep   59    0   0:01:30 0.0% nscd/36
   302 root     6208K 3420K sleep   59    0   0:00:22 0.0% devfsadm/9
Total: 134 processes, 570 lwps, load averages: 1.02, 1.01, 1.01
   PID USERNAME  SIZE   RSS STATE  PRI NICE      TIME  CPU PROCESS/NLWP
 24514 root      154M  147M cpu0     0    0  18:49:37  50% msieve/1
   420 daemon     10M 5448K sleep   59    0   7:26:27 0.4% rcapd/1
  4942 root     3788K 3020K cpu1   100    -   0:00:00 0.0% prstat/1
 13589 root     6156K 4548K sleep   58    0   0:01:11 0.0% snmpd/1
  9923 root       13M 7788K sleep    1    0   0:00:03 0.0% nscd/23
   505 root     2520K 1092K sleep   59    0   0:00:00 0.0% automountd/2
   503 daemon   5792K 1284K sleep   59    0   0:00:04 0.0% nfsmapid/4
   384 root     5064K 1988K sleep   59    0   0:00:00 0.0% syseventd/16
   389 root     6196K 3220K sleep   59    0   0:01:30 0.0% nscd/36
   302 root     6208K 3420K sleep   59    0   0:00:22 0.0% devfsadm/9
Total: 134 processes, 570 lwps, load averages: 1.02, 1.01, 1.01
#
#

Almost 19 hours with no output at all.

This bothers me.

Has Msieve come to a grinding halt ?

Thank you for any response at all dear number crunchers.

Dennis

[schickel]

Originally Posted by Unregistered

Almost 19 hours with no output at all.

This bothers me.

Has Msieve come to a grinding halt ?

Thank you for any response at all dear number crunchers.

Dennis

Unfortunately, no, it's still grinding away. The problem here is that while the quadratic sieve is fantastic for small numbers, it scales very badly as the size of the input increases.

I forget what the factor is, but the run time for QS doubles for every 3-4(?) digits you add to the input number.

If the time doubles for every 4 digits, it's not that bad. If 80 digits takes ~9 minutes, then 148 digits is going to take ~2.4 years.

If, however, the run time doubles every 3 digits, things look a little worse: if 80 digits takes 9 minutes, 148 digits is going to take ~143 years.

The good thing is that, barring file corruption in the case of a power interruption, with a clean shut down, msieve can resume the job from where you stop it, so you can reboot to apply security updates or OS updates as you go.

What you really want need to look into is GNFS. a good starting place is here. Take a look around there and if you have any questions, feel free to ask here. We've got a great bunch of people around that are willing to help out as you get started.

Also, the best advice you'll get is to start small and work up from there. I managed a c146 on my own in ~3 weeks.... If you don't mind being asked, what is the origin of the c148 under consideration?

Frank

[blastwave]

Unfortunately, no, it's still grinding away.

Okay, perhaps I should have started much much smaller.

What you really want need to look into is GNFS....

OKay, thank you very much. I have a pile of hardware here that often sits and spins doing nothing really for weeks on end. I figured that I should put it to good use. I had a RHEL5 ( dual AMD64, 4G mem etc etc ) server that I "rediscovered" spinning in the datacenter. No one had logged into it since Wed Aug 4 and that was only for a quick patch check. Previous to that it sat doing nothing since Tue May 25. I figured that it should be doing "something" at least. I pretty much live in the Solaris world and was thinking that I could look at doing some GIMPS work with some idle hardware and thus this lone Linux server could be formatted and be running Solaris 10 and then crunching numbers.

Also, the best advice you'll get is to start small and work up from there. I managed a c146 on my own in ~3 weeks.... If you don't mind being asked, what is the origin of the c148 under consideration?

Ignorance mostly :-)

Here is what happened.

I have a lot of software to build here and there are some pieces that I want as optimal as possible, or reasonable, and yet still able to run on a very wide platform architecture base. All of the UltraSparc ( or plain old Sparc v8 or even v7 ) software is generally compiled to run on nearly anything with an UltraSparc chip back to the old Ultra1 sparcv9 first generation. That means no fancy VIS opcodes and no fancy cache tweaking. It is very stable and it is very safe. Not very fast however. This is the old FAST || SAFE || CHEAP problem where you can have two, maybe.

So I was compiling the gmp libs and mpfr and thinking "I need a nice long stable run of something to measure my optimization efforts here" and fell into good old MSieve. I was first playing with it back in 2007 because I found a file thus : "Apr 17 2007 msieve119.tar.gz" and there were binaries also. I also saw Jul 20 2009 msieve142.tar.gz on the filesystem so I was not new to this. I simply had neve rdone anything of any real value with it.

I went and fetched the latest msieve147.tar.gz and then compiled it for a very very simple baseline test and was happy to see it factoring numbers in the 80 digit range. This newer rev needed gmp-5.0.1 ( or similar ) and that seemed like a good way to measure my optimization tests. However, I then fell into factoring numbers over and over whilst looking for a few decent sized primes thus :

[titan] ptime ./msieve -s test002.dat -l test002.log -mb 256 -v -t 4 -e 16971908772079236834903829111652969781619450405813156174333622080900140647


Msieve v. 1.47
Sun Oct  3 17:33:36 2010
random seeds: 010f09ca 93a99f5a
factoring 16971908772079236834903829111652969781619450405813156174333622080900140647 (74 digits)
prp74 factor: 16971908772079236834903829111652969781619450405813156174333622080900140647
elapsed time 00:00:00

real        0.527
user        0.078
sys         0.033
[titan]

Well I think a 74 digit prime is nice and large.

Later in the day I ran into this :

[titan] ptime ./msieve -s test003.dat -l test003.log -mb 256 -v -t 4 -e 301563764417881108223217686434844324806337821824798761903845036917932182907


Msieve v. 1.47
Sun Oct  3 17:37:22 2010
random seeds: e59bf5bd 2fce0a46
factoring 301563764417881108223217686434844324806337821824798761903845036917932182907 (75 digits)
prp75 factor: 301563764417881108223217686434844324806337821824798761903845036917932182907
elapsed time 00:00:00

real        0.201
user        0.080
sys         0.021
[titan]

Well I am sure you know what I did next. :-)

Multiply those two big primes together and you get my test case :

5118112698665072812520866447773637877346372738061830362488665585404041331503549909040610381146134652023670197106080332578287665297420147584029320829

=

prp74 ( 16971908772079236834903829111652969781619450405813156174333622080900140647 ) 

 *

prp75 ( 301563764417881108223217686434844324806337821824798761903845036917932182907 )

This, to me, seemed like a good way to test some factoring software. Strangely I have a license of Mathematica which is supposed to be blistering quick at factoring but for reasons unknown I could not find the software box anywhere. I really did look too. I think it may have grown legs in the office and I'll need to purchase another copy. I was left with no commercial software to use as a baseline test datapoint and thus I tossed this large composite at Msieve v. 1.47 and walked away.

A day later I saw this :

# ptime ./msieve -s test001.dat -l test001.log -v -t 4 5118112698665072812520866447773637877346372738061830362488665585404041331503549909040610381146134652023670197106080332578287665297420147584029320829

Msieve v. 1.47
Fri Oct  1 22:48:38 2010
random seeds: 7dfe5dce 69c85b6c
factoring 5118112698665072812520866447773637877346372738061830362488665585404041331503549909040610381146134652023670197106080332578287665297420147584029320829 (148 digits)
no P-1/P+1/ECM available, skipping
commencing quadratic sieve (148-digit input)
using multiplier of 13
using 64kb Opteron sieve core
sieve interval: 153 blocks of size 65536
processing polynomials in batches of 1
using a sieve bound of 36237749 (1109091 primes)
using large prime bound of 4294967295 (31 bits)
using double large prime bound of 218437776016143360 (51-58 bits)
using trial factoring cutoff of 58 bits
polynomial 'A' values have 16 factors

sieving in progress (press Ctrl-C to pause)

The software seemed to be using only one CPU and a bit of memory but there was no sign of progress. After I read your response I stopped the thing. It would be pointless really.

With your input pointing me in the right direction I fetched ggnfs-0.77.1-20060513.tar.bz2 and it looks to be really non-trivial. It may or may not even compile here but I'll give it a try.

Not going to be easy :

[titan] make pentium3
gmake[1]: Entering directory `/export/medusa/dclarke/build/MSieve/GGNFS/ggnfs_sol8_i386_gcc451'
echo "#define GGNFS_VERSION \"0.77.1-20060513-pentium3\"" > include/version.h
gmake[2]: Entering directory `/export/medusa/dclarke/build/MSieve/GGNFS/ggnfs_sol8_i386_gcc451/src'
/opt/csw/gcc4/bin/gcc -I. -I.. -I../include -I/opt/csw/include -IF:/tmp/nfs/tpie/include -DNDEBUG -O3 -ffast-math -funroll-loops -finline-functions -ftracer -fomit-frame-pointer -W -Wall -march=pentium3 -pipe -DMALLOC_REPORTING -o getprimes.o -c getprimes.c
getprimes.c: In function 'pSieve':
getprimes.c:160:24: warning: unused parameter 'Psize'
/opt/csw/gcc4/bin/gcc -I. -I.. -I../include -I/opt/csw/include -IF:/tmp/nfs/tpie/include -DNDEBUG -O3 -ffast-math -funroll-loops -finline-functions -ftracer -fomit-frame-pointer -W -Wall -march=pentium3 -pipe -DMALLOC_REPORTING -o fbmisc.o -c fbmisc.c
In file included from fbmisc.c:31:0:
if.h:70:6: error: conflicting types for '__gmpz_mul_si'
/opt/csw/include/gmp.h:1002:21: note: previous declaration of '__gmpz_mul_si' was here
fbmisc.c: In function 'setLogs':
fbmisc.c:200:47: warning: unused parameter 'b0'
fbmisc.c: In function 'generateAFB':
fbmisc.c:393:5: warning: pointer targets in passing argument 1 of 'root_finder' differ in signedness
../include/ggnfs.h:775:5: note: expected 'uint32_t *' but argument is of type 'int32_t *'
fbmisc.c: In function 'isSmooth_rat_withInfo_par':
fbmisc.c:722:11: warning: comparison of unsigned expression < 0 is always false
fbmisc.c: In function 'isSmooth_alg_withInfo_par':
fbmisc.c:814:11: warning: comparison of unsigned expression < 0 is always false
fbmisc.c:828:39: warning: comparison between signed and unsigned integer expressions
gmake[2]: *** [fbmisc.o] Error 1
gmake[2]: Leaving directory `/export/medusa/dclarke/build/MSieve/GGNFS/ggnfs_sol8_i386_gcc451/src'
gmake[1]: *** [x86common] Error 2
gmake[1]: Leaving directory `/export/medusa/dclarke/build/MSieve/GGNFS/ggnfs_sol8_i386_gcc451'
gmake: *** [pentium3] Error 2
[titan]

Looks like the newer GMP 5.0.1 will not fly and a bucket of other issues. I better roll back a version and see what happens.

I'll be sure to report any progress ... if any.

Dennis

[schickel]

Originally Posted by blastwave

Looks like the newer GMP 5.0.1 will not fly and a bucket of other issues. I better roll back a version and see what happens.

I'll be sure to report any progress ... if any.

Dennis

Sounds good. Depending on how deeply you want to muck about in this, head on over to the factoring forum. There are links to pre-compiled binaries of everything needed to get started with factoring. Or, if it suits you more, that's the place to ask questions related to compiling everything yourself.

Welcome to Mersenneforum and the world of factoring!

Frank

[xilman]

Originally Posted by blastwave

Unfortunately, no, it's still grinding away.

Okay, perhaps I should have started much much smaller.

Yup. Factoring a c148 with MPQS is going to be very difficult. I've experience in this field, having done two of the largest MPQS factorizations recorded. The largest I've done and, afaik, the largest ever done was a c135.

Add to that the observation that the Sparc chips are rather poor at this sort of thing compared with x86, and you really are not going to complete a c148 any time soon. I second the motion that you transfer your affections to gnfs. Further, if you want a test number which is both useful (in some loose sense) and is somewhat easier than a c148 I can provide candidates for you.


Paul

P.S. Just remembered you are running on x86. It was your mention of Sparc systems which confused me.

[blastwave]

Originally Posted by schickel

Sounds good. Depending on how deeply you want to muck about in this...

Well I am certainly game to get a machine here cranking away in its spare cycles.

Originally Posted by schickel

... head on over to the factoring forum. There are links to pre-compiled binaries of everything needed to get started with factoring. Or, if it suits you more, that's the place to ask questions related to compiling everything yourself.

Welcome to Mersenneforum and the world of factoring!

Frank

Thank you very much ... I'll head over there, beg for advance forgiveness for the questions I am about to ask, and then dive in.

Dennis

[blastwave]

Originally Posted by xilman

Yup. Factoring a c148 with MPQS is going to be very difficult. I've experience in this field, having done two of the largest MPQS factorizations recorded. The largest I've done and, afaik, the largest ever done was a c135.

Clearly I was way out in left field playing a game with no clue. A good way to start I Figure.

Originally Posted by xilman

Add to that the observation that the Sparc chips are rather poor at this sort of thing compared with x86, and you really are not going to complete a c148 any time soon. I second the motion that you transfer your affections to gnfs. Further, if you want a test number which is both useful (in some loose sense) and is somewhat easier than a c148 I can provide candidates for you.


Paul

P.S. Just remembered you are running on x86. It was your mention of Sparc systems which confused me.

Well, I have lots of both architectures and some PowerPC also. I am a firm believer that some processors and RISC chips are better at some things than others. The UltraSparc's can become very neatly parallel when you have 16 sockets of quad core. Even if they are only 1.6GHz you are still swimming in throughput. Also, the optimized FFT routines provided in the Sun Performance libs are really well done. Who knows ... I was just doing experiments to see what would happen.

As for x86 there seems to be no shortage of assembly in these code releases. I expect that the x86 processors and the AMD Opteron's in particular to be quite quick at getting the job done.

I'll head on over to the Factoring forum and begin asking my noob questions.

Dennis

sorry about the bold text .. I'm more familiar with an xterm than this forum software.

[jasonp]

Also note that msieve switched to requiring GMP because the end of the number field sieve processing required arbitrary precision arithmetic, but it's not used in the QS code at all. If you want a state-of-the-art long-running test case for GMP, I'd recommend GMP-ECM (which also has its own subforum here, and a lot of people trying to produce optimized binaries).

[10metreh]

Also the -t 4 will only work for the linear algebra stage of GNFS, so that's why only one thread was being used. -mb 256 is only for the filtering stage of GNFS, so that won't work either.