mersenneforum.org Feedback for new MPQS utility sought
 Register FAQ Search Today's Posts Mark Forums Read

 2004-10-25, 01:17 #1 jasonp Tribal Bullet     Oct 2004 2·3·19·31 Posts Feedback for new MPQS utility sought I happen to be working in my spare time on an MPQS factorization utility, and was wondering if folks here could provide feedback. The latest version is at www.boo.net/~jasonp/qs.html although things are a little primitive at the moment. The top few things on the todo list, in order: 1. Add double large prime support 2. Make things resumable, and streamline the logging of intermediate results and data 3. tune for factorizations larger than 80 digits 4. add multiprocessor support(?) 5. switch to block lanczos for the linear algebra Also, the code at present uses a weird hashtable-based sieving technique for bigger factorizations, that I haven't seen described elsewhere. I wonder if it's new, and maybe if NFS programs can benefit from it. One other thing: for big factorizations, should I be working to completely separate the sieving from the postprocessing, as separate applications that could be run on different machines? Or would folks find it more convenient to have everything bundled into a single binary, whose capabilities would be more limited? Thanks in advance, jasonp
2004-10-25, 06:36   #2
JHansen

Apr 2004
Copenhagen, Denmark

22·29 Posts

Quote:
 Originally Posted by jasonp One other thing: for big factorizations, should I be working to completely separate the sieving from the postprocessing, as separate applications that could be run on different machines? Or would folks find it more convenient to have everything bundled into a single binary, whose capabilities would be more limited?
I think you should aim for a single binary. The postprocessing of QS isn't nearly as complicated as in NFS, (where, most notably, the filtering stage often can be highly non-trivial to perform) and the resulting matrix is also smaller.

I havn't read your code, but I am always inpressed, when somebody can produce an efficient QS implementation .

It would be nice though, if one could tell the program only to perform the sieving phase. This way one could use many machines to sieve, and then later one can collect all the relations on one machine to do matrix pruning, linear algebra and square root.

-----
Jes Hansen

Last fiddled with by JHansen on 2004-10-25 at 06:38

2004-10-25, 07:37   #3
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2×3×17×103 Posts

Quote:
 Originally Posted by JHansen It would be nice though, if one could tell the program only to perform the sieving phase. This way one could use many machines to sieve, and then later one can collect all the relations on one machine to do matrix pruning, linear algebra and square root.
Sounds a good suggestion to me.

Arjen Lenstra has a nice implementation of this approach. The first run is the master and it does all stages, including building the factorbases which live in a file. If an additional parameter is given to other instances of the program, it is used as the name of a slave siever which puts its output into a common working directory. Master and slaves signal to each other by the presence of files in the working directory.

Paul

 2004-10-25, 14:03 #4 ET_ Banned     "Luigi" Aug 2002 Team Italia 23×599 Posts Hi Jes, I tried your SIQS and have a question. With very big numbers the program crashes on a 256 MB Athlon. Is it only a matter of installed memory, or there is a limit on the length of the analyzed number? Luigi
2004-10-25, 16:46   #5
jasonp
Tribal Bullet

Oct 2004

2·3·19·31 Posts

Quote:
 Originally Posted by ET_ With very big numbers the program crashes on a 256 MB Athlon. Is it only a matter of installed memory, or there is a limit on the length of the analyzed number?
What's very big? The program includes a homebrew multiple precision
library that is hardwired for 110 digits or less. That being said, an
80-digit factorization requires about 72MB by the end of the linear
algebra stage.

jasonp

2004-10-25, 16:56   #6
ET_
Banned

"Luigi"
Aug 2002
Team Italia

23×599 Posts

Quote:
 Originally Posted by jasonp What's very big? The program includes a homebrew multiple precision library that is hardwired for 110 digits or less. That being said, an 80-digit factorization requires about 72MB by the end of the linear algebra stage. jasonp
I guess "more than 110 digits" is very big, rethinking about SNSF and GNSF... Even if it factorizes trivially. I should start up my brain before writing.

Sorry for last post.

Luigi

2004-10-26, 06:38   #7
BotXXX

Aug 2003
Europe

2·97 Posts

I tried out your software (on a number that is just a test number in my collection) and it works perfectly. The only remark is that there is not a visible how long to go, or on what point am i now progress meter/bar. But then again it is also not very needed.

See attached file for results. It waws run on a P4 1.6 with 512 of RAM.
The number put in to SIQS is a part of ((29^9)^9)-3 and had 83-digits
Attached Files
 SIQS_factored.txt (2.3 KB, 320 views)

2004-10-26, 11:59   #8
jasonp
Tribal Bullet

Oct 2004

353410 Posts

Quote:
 Originally Posted by BotXXX I tried out your software (on a number that is just a test number in my collection) and it works perfectly. The only remark is that there is not a visible how long to go, or on what point am i now progress meter/bar. But then again it is also not very needed. See attached file for results. It waws run on a P4 1.6 with 512 of RAM. The number put in to SIQS is a part of ((29^9)^9)-3 and had 83-digits
Great, this is the largest factorization attempted so far. Out of curiosity,
how long does ppsiqs take for this number on your machine?

The next version will overhaul the reporting of progress, but first I want
to get double large primes going.

jasonp

 2004-10-27, 02:30 #9 trilliwig     Oct 2004 tropical Massachusetts 3×23 Posts Works pretty well for me, and it's noticeably faster than Satoshi Tomabechi's PPSIQS for numbers around 65 digits or more. The only flaw I see is if you enter a number that's too small, it gives a rather opaque error message: "fatal error: poly selection failed". Maybe you could print a more helpful warning, or perhaps use an implementation of Pollard rho for these numbers? Here are some times on a Pentium 745 (Pentium-M Dothan 1.8GHz, 32K+32K L1, 2M L2, 1G RAM, WinXP-SP2): Code: Number digits PPSIQS-1.1 SIQS-0.7 ----------------------------------------- (6^67-1)/5 52 0:00:03 0:00:04 (10^59-1)/9 59 0:00:17 0:00:16 (3^137+1)/4 65 0:01:02 0:00:53 (10^71-1)/9 71 0:04:34 0:02:53 (12^71+1)/13 76 0:22:07 0:17:11 (10^83-1)/9 83 1:59:33 1:14:44
2004-10-27, 07:27   #10
BotXXX

Aug 2003
Europe

C216 Posts

Quote:
 Originally Posted by jasonp Great, this is the largest factorization attempted so far. Out of curiosity, how long does ppsiqs take for this number on your machine?
I think it has not much difference. Altho on the machine there are more programs running, but SIQS or ppsiqs take almost 99% idle time. So roughly it should be comparable. SISQ was run at the start of the morning and me also working on the machine, ppsiqs was run at the end of the day with me not more working on the pc. So a little difference there is.

Attached is the output of ppsiqs and it takes cputime 2:39:39 compared to the 2:45:00 that SIQS takes.
Attached Files
 PPSIQS_factored.txt (1.2 KB, 230 views)

2004-10-27, 13:29   #11
jasonp
Tribal Bullet

Oct 2004

2·3·19·31 Posts

Quote:
 Originally Posted by BotXXX Attached is the output of ppsiqs and it takes cputime 2:39:39 compared to the 2:45:00 that SIQS takes.
Ouch, I was prepared for a bad runtime on the P4 but not this bad.
It's pretty clear that the cache blocking needs some kind of command-line
control, since the Athlon and Pentium-M times are pretty good. The alternative
is automatic x86-specific L1 size detection, which would be straightforward
but distasteful.

jasonp

 Similar Threads Thread Thread Starter Forum Replies Last Post jwaltos Other Mathematical Topics 8 2015-05-22 12:20 Antonio Software 5 2013-04-18 14:22 fivemack Hardware 1 2011-12-21 19:26 smoking81 Factoring 10 2007-10-02 12:30 HiddenWarrior Programming 6 2004-11-04 05:21

All times are UTC. The time now is 09:37.

Fri Jan 22 09:37:43 UTC 2021 up 50 days, 5:49, 0 users, load averages: 2.22, 2.38, 2.59