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

[url]www.boo.net/~jasonp/qs.html[/url]

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

[QUOTE=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?[/QUOTE]

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 :bow: .

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

[QUOTE=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.[/QUOTE]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

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

[QUOTE=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?
[/QUOTE]
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

[QUOTE=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[/QUOTE]

I guess "more than 110 digits" is very big, rethinking about SNSF and GNSF... Even if it factorizes trivially. :redface: I should start up my brain before writing.

Sorry for last post.

Luigi

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

[QUOTE=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[/QUOTE]
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

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
[/code]

[QUOTE=jasonp]Great, this is the largest factorization attempted so far. Out of curiosity, how long does ppsiqs take for this number on your machine?
[/QUOTE]

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.

[QUOTE=BotXXX]Attached is the output of ppsiqs and it takes cputime 2:39:39 compared to the 2:45:00 that SIQS takes.[/QUOTE]
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