mersenneforum.org GNFS estimates
 Register FAQ Search Today's Posts Mark Forums Read

 2009-04-07, 23:18 #45 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 1005410 Posts Even smaller, which are for example 98-105 digit SNFS jobs. Don't forget SNFS jobs. They are fun, and a good excercise for the mind (to build a polynomial in some cases; in most cases of course - it's a boring excercise for boring polynomials). Some Fibonacci numbers have very nice polynomials, and so do e.g. numbers of form a^13n+-b^13n, and Aurifeuillians and so on, and so on. In those 98-105 digit SNFS jobs, if you will have oversieved (using 0.4 or 0.5), the filtering will fail to converge and the script will stop (it's fixable, too, - check the similar threads). If you use 0.2 with those jobs, you will converge in a ridiculously short time, like 5 or 10 minutes for the whole factorization. Like this one: Code:  n: 142636039930449499515055724706069369122952024169034908419840194033346894320140545970889557 c4: 7 c0: 11 Y1: 1 Y0: -10000000000000000000000000 skew: 1.12 type: snfs lss: 1 rlim: 400000 alim: 400000 lpbr: 25 lpba: 25 mfbr: 45 mfba: 45 rlambda: 2.2 alambda: 2.2 Note: it will choke with 0.4. (And it will choke, too, if you use double qintsize jumps with 4 threads in factMsieve.pl.) Compare that to the times of mpqs or gnfs.
 2009-04-07, 23:26 #46 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·11·457 Posts ...or take this one for example (someone couldn't quite finish it)... Code: n: 7126956154329172964190407581733579595542753084022720093873577878288167714232922899398415101 m: 200000000000000000000000000 deg: 4 c4: 13 c0: 44 skew: 1.36 type: snfs lss: 1 rlim: 410000 alim: 410000 lpbr: 25 lpba: 25 mfbr: 45 mfba: 45 rlambda: 2.2 alambda: 2.2 It's a 10 minute job, man. 10 minutes, tops! Last fiddled with by Batalov on 2009-04-07 at 23:36
2009-04-08, 00:11   #47
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

186916 Posts

Quote:
 Originally Posted by Batalov ...or take this one for example (someone couldn't quite finish it)... Code: n: 7126956154329172964190407581733579595542753084022720093873577878288167714232922899398415101 m: 200000000000000000000000000 deg: 4 c4: 13 c0: 44 skew: 1.36 type: snfs lss: 1 rlim: 410000 alim: 410000 lpbr: 25 lpba: 25 mfbr: 45 mfba: 45 rlambda: 2.2 alambda: 2.2 It's a 10 minute job, man. 10 minutes, tops!
Ah, seems that "someone" sent me that one as well. I reserved it at the near-repdigit website shortly afterwards and finished it in...hmm, come to think of it, I forgot to take note of how much time it took and have since deleted the log. Oh well, the log will show up on the near-repdigit website's progress update tomorrow at 5 P.M. GMT.

I ended up finishing it with factLat.pl after postprocessing with msieve just wouldn't work no matter how much relations I limited it to. I got the window between "filtering wants more relations" and "matrix not dense enough" down to a window of 100 relations, and it still wouldn't work, so I gave up and did it with factLat.pl.

(Note: this was done with an unmodified factMsieve.pl, downloaded a month or so ago. I really should update to the latest new-and-improved one some time soon...not sure if it would help in this particular instance though.)

Last fiddled with by mdettweiler on 2009-04-08 at 00:12

2009-04-08, 00:30   #48
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100111010001102 Posts

Quote:
 Originally Posted by mdettweiler I ended up finishing it with factLat.pl after postprocessing with msieve just wouldn't work no matter how much relations I limited it to. I got the window between "filtering wants more relations" and "matrix not dense enough" down to a window of 100 relations, and it still wouldn't work, so I gave up and did it with factLat.pl
Right. That shows that maybe 0.2 should have been changed to 0.15 for this one.

You know what could have happened with your trimming? msieve adds "free" rels. if you trim these away, nothing will change in the next filtering run - they will be simply added back in.
Ok, and here's a trick from the bottom of my sack. 1. trim .dat file and also 2. edit the .job file! decrease by 10 the "q0" that's there. This is necessary to deceive the siever not to sieve, because otherwise it will sieve a bunch again and you will have trimmed in vain.

This necessary number of relations (MINRELS) is so tricky that no one really wants to touch this 0.2 parameter in the downloadable script! At the very least 0.2 works almost always (if only not for this number).
Here's the necessary magic to finish fiascos like this (trimming extra relations from the bottom of the .dat file... but not too many ... how many is not too many? nobody really knows!) -
and bits of the same advice in three or four more threads... This does plague little numbers and not medium and large numbers. If you are working on a day-week scale jobs, then 0.5 is the coefficient you almost always need.

the MINRELS.txt patch was supposed to help (mostly for larger numbers); but if the number is tiny, then put 1 in the MINRELS.txt file -- that shouldn't hurt.

Last fiddled with by Batalov on 2009-04-08 at 00:48

2009-04-08, 01:54   #49
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

3·2,083 Posts

Quote:
 Originally Posted by Batalov You know what could have happened with your trimming? msieve adds "free" rels. if you trim these away, nothing will change in the next filtering run - they will be simply added back in. Ok, and here's a trick from the bottom of my sack. 1. trim .dat file and also 2. edit the .job file! decrease by 10 the "q0" that's there. This is necessary to deceive the siever not to sieve, because otherwise it will sieve a bunch again and you will have trimmed in vain.
Regarding the "free" relations: hmm, interesting. I hadn't thought of that. Next time I'll be sure to pay closer attention to that when I need to trim relations.

Regarding the little trick of "fooling" factMsieve.pl into not sieving any more: yes, I've used that a few times. However, in this case it wasn't necessary since, in reality, I was simply running msieve directly (though with the exact same command line that factMsieve.pl had originally tried to feed to it, with modifications where necessary to make it chop off additional relations).

 Similar Threads Thread Thread Starter Forum Replies Last Post henryzz GMP-ECM 8 2009-12-31 17:51 Andi47 Msieve 5 2009-01-26 18:19 brownkenny Math 2 2009-01-22 17:21 henryzz Msieve 27 2009-01-21 18:37 kdq Software 4 2008-10-04 05:02

All times are UTC. The time now is 21:22.

Wed Feb 1 21:22:41 UTC 2023 up 167 days, 18:51, 0 users, load averages: 0.75, 0.85, 0.92