mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2004-10-25, 01:17   #1
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default 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
jasonp is offline   Reply With Quote
Old 2004-10-25, 06:36   #2
JHansen
 
JHansen's Avatar
 
Apr 2004
Copenhagen, Denmark

22·29 Posts
Thumbs up

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
JHansen is offline   Reply With Quote
Old 2004-10-25, 07:37   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×3×17×103 Posts
Default

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
xilman is online now   Reply With Quote
Old 2004-10-25, 14:03   #4
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

23×599 Posts
Default

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
ET_ is offline   Reply With Quote
Old 2004-10-25, 16:46   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2004-10-25, 16:56   #6
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

23×599 Posts
Default

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
ET_ is offline   Reply With Quote
Old 2004-10-26, 06:38   #7
BotXXX
 
BotXXX's Avatar
 
Aug 2003
Europe

2·97 Posts
Default

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
File Type: txt SIQS_factored.txt (2.3 KB, 320 views)
BotXXX is offline   Reply With Quote
Old 2004-10-26, 11:59   #8
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

353410 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2004-10-27, 02:30   #9
trilliwig
 
trilliwig's Avatar
 
Oct 2004
tropical Massachusetts

3×23 Posts
Talking

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
trilliwig is offline   Reply With Quote
Old 2004-10-27, 07:27   #10
BotXXX
 
BotXXX's Avatar
 
Aug 2003
Europe

C216 Posts
Default

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
File Type: txt PPSIQS_factored.txt (1.2 KB, 230 views)
BotXXX is offline   Reply With Quote
Old 2004-10-27, 13:29   #11
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

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
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Utility of integer factorization. jwaltos Other Mathematical Topics 8 2015-05-22 12:20
File Splitting Utility Antonio Software 5 2013-04-18 14:22
Low-powered motherboard of adequate capability sought fivemack Hardware 1 2011-12-21 19:26
Implementing MPQS: SOS! smoking81 Factoring 10 2007-10-02 12:30
Prime Shuffle Utility 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.