mersenneforum.org MSieve oddities....
 Register FAQ Search Today's Posts Mark Forums Read

 2007-04-09, 07:51 #1 schickel     "Frank <^>" Dec 2004 CDP Janesville 2·1,061 Posts MSieve oddities.... Jason, what are the odds of this happening: Code: Sat Mar 31 09:18:21 2007 Msieve v. 1.17 Sat Mar 31 09:18:21 2007 random seeds: 5b81797a 53bf75dc Sat Mar 31 09:18:21 2007 factoring 32200965083893482185326001147284472219899155920246951448410850906541174123992621173 (83 digits) Sat Mar 31 09:18:22 2007 commencing quadratic sieve (83-digit input) {.... } Sat Mar 31 13:17:55 2007 matrix is 52647 x 52770 with weight 1669376 (avg 31.63/col) Sat Mar 31 13:17:59 2007 filtering completed in 4 passes Sat Mar 31 13:18:00 2007 matrix is 44740 x 44804 with weight 1384785 (avg 30.91/col) Sat Mar 31 13:18:03 2007 saving the first 48 matrix rows for later Sat Mar 31 13:18:03 2007 matrix is 44692 x 44804 with weight 1007923 (avg 22.50/col) Sat Mar 31 13:18:03 2007 matrix includes 32 packed rows Sat Mar 31 13:22:31 2007 lanczos error: not all columns used Sat Mar 31 13:22:31 2007 lanczos halted after 707 iterations Sat Mar 31 13:22:31 2007 linear algebra failed; retrying... Sat Mar 31 13:22:31 2007 saving the first 48 matrix rows for later Sat Mar 31 13:22:31 2007 matrix is 44692 x 44804 with weight 777029 (avg 17.34/col) Sat Mar 31 13:22:31 2007 matrix includes 32 packed rows Sat Mar 31 13:26:42 2007 lanczos halted after 707 iterations Sat Mar 31 13:26:44 2007 recovered 11 nontrivial dependencies Sat Mar 31 13:26:50 2007 c83 factor: 32200965083893482185326001147284472219899155920246951448410850906541174123992621173 Sat Mar 31 13:26:50 2007 elapsed time 04:08:29 Twice? Code: Tue Apr 03 08:48:16 2007 Msieve v. 1.17 Tue Apr 03 08:48:16 2007 random seeds: a454aaf0 9f297949 Tue Apr 03 08:48:16 2007 factoring 21075296035900797161789357280557082902659396333534601045084652691867815920371245259118887103 (92 digits) Tue Apr 03 08:48:17 2007 commencing quadratic sieve (92-digit input) { .... } Tue Apr 03 11:17:28 2007 matrix is 67059 x 67459 with weight 3806940 (avg 56.43/col) Tue Apr 03 11:17:28 2007 filtering completed in 4 passes Tue Apr 03 11:17:28 2007 matrix is 65281 x 65345 with weight 3618563 (avg 55.38/col) Tue Apr 03 11:17:29 2007 saving the first 48 matrix rows for later Tue Apr 03 11:17:29 2007 matrix is 65233 x 65345 with weight 2683532 (avg 41.07/col) Tue Apr 03 11:17:29 2007 matrix includes 32 packed rows Tue Apr 03 11:20:54 2007 lanczos error: not all columns used Tue Apr 03 11:20:54 2007 lanczos halted after 1033 iterations Tue Apr 03 11:20:54 2007 linear algebra failed; retrying... Tue Apr 03 11:20:54 2007 saving the first 48 matrix rows for later Tue Apr 03 11:20:54 2007 matrix is 65233 x 65345 with weight 1932698 (avg 29.58/col) Tue Apr 03 11:20:54 2007 matrix includes 32 packed rows Tue Apr 03 11:24:01 2007 lanczos halted after 1032 iterations Tue Apr 03 11:24:01 2007 recovered 11 nontrivial dependencies Tue Apr 03 11:24:06 2007 c92 factor: 21075296035900797161789357280557082902659396333534601045084652691867815920371245259118887103 Tue Apr 03 11:24:06 2007 elapsed time 02:35:50 Luckily, they both factored out just by rerunning MSieve again on the same dat file. Code: Sat Mar 31 20:39:13 2007 matrix is 52647 x 52770 with weight 1669376 (avg 31.63/col) Sat Mar 31 20:39:18 2007 filtering completed in 4 passes Sat Mar 31 20:39:18 2007 matrix is 44740 x 44804 with weight 1384785 (avg 30.91/col) Sat Mar 31 20:39:21 2007 saving the first 48 matrix rows for later Sat Mar 31 20:39:22 2007 matrix is 44692 x 44804 with weight 1007923 (avg 22.50/col) Sat Mar 31 20:39:22 2007 matrix includes 32 packed rows Sat Mar 31 20:44:15 2007 lanczos halted after 708 iterations Sat Mar 31 20:44:17 2007 recovered 12 nontrivial dependencies Sat Mar 31 20:44:18 2007 prp41 factor: 32921344246694627905159036248848172735383 Sat Mar 31 20:44:18 2007 prp42 factor: 978118172897102362382329280406398275442131 Tue Apr 03 11:50:27 2007 matrix is 67059 x 67459 with weight 3806940 (avg 56.43/col) Tue Apr 03 11:50:28 2007 filtering completed in 4 passes Tue Apr 03 11:50:28 2007 matrix is 65281 x 65345 with weight 3618563 (avg 55.38/col) Tue Apr 03 11:50:29 2007 saving the first 48 matrix rows for later Tue Apr 03 11:50:29 2007 matrix is 65233 x 65345 with weight 2683532 (avg 41.07/col) Tue Apr 03 11:50:29 2007 matrix includes 32 packed rows Tue Apr 03 11:54:01 2007 lanczos halted after 1033 iterations Tue Apr 03 11:54:02 2007 recovered 17 nontrivial dependencies Tue Apr 03 11:54:04 2007 prp46 factor: 1155662819900477340596743106963448902784338557 Tue Apr 03 11:54:04 2007 prp47 factor: 18236544148504964911628354017925440534379782379 Later, Frank
2007-04-09, 12:14   #2
jasonp
Tribal Bullet

Oct 2004

67168 Posts

Quote:
 Originally Posted by schickel Jason, what are the odds of this happening:
Restarting the linear algebra can happen once in a while; the factorization not working afterwards is a bug that should be fixed in v1.18

jasonp

 2007-04-09, 14:57 #3 schickel     "Frank <^>" Dec 2004 CDP Janesville 2×1,061 Posts Jason, Cool. I updated to 1.18 on one of my PCs, although I'll have to check the other one now, since I'm not sure I did that one. It was odd that it failed twice pretty close together like that. In ~100 factorizations, that's only twice that I've ever seen that... Later, Frank
2007-04-09, 15:01   #4
jasonp
Tribal Bullet

Oct 2004

2×3×19×31 Posts

Quote:
 Originally Posted by schickel Jason, Cool. I updated to 1.18 on one of my PCs, although I'll have to check the other one now, since I'm not sure I did that one. It was odd that it failed twice pretty close together like that. In ~100 factorizations, that's only twice that I've ever seen that...
There's nothing preventing it from happening during any factorization, it just amounts to a (randomly) bad choice of starting solution to the linear algebra. Linear algebra failure is more likely at the smaller problem sizes; I've seen 40-digit factorizations have three failures in a row before the linear algebra succeeds. I suppose it also is more likely now that QS finds fewer dependencies by default, in order to make the linear algebra complete faster.

I actually just received a report that factorizations also fail after a linear algebra restart when using the latest version too; the next version will include structural changes to the linear algebra that will hopefully remove the possibility of these kinds of problems in the future. For now, restarting msieve should allow the factors to get found.

jasonp

Last fiddled with by jasonp on 2007-04-09 at 15:05

2007-04-15, 21:42   #5
jasong

"Jason Goatcher"
Mar 2005

5·701 Posts

Quote:
 Originally Posted by schickel Jason, what are the odds of this happening:
I knew this wasn't aimed at me a split second after I read it, but the experience is still rather peculiar. Kind of makes me wonder why anyone would even want to show up at a John Smith convention when their name is John Smith.(Yes, there ARE conventions of this sort. They're probably even more popular now that communication over the Internet is possible.)

Carry on.

 Similar Threads Thread Thread Starter Forum Replies Last Post clowns789 Lone Mersenne Hunters 2 2019-06-08 17:20 pxp Msieve 1 2013-02-28 14:56 Christenson PrimeNet 2 2011-03-29 02:11 em99010pepe Msieve 23 2009-09-27 16:13 kwstone Soap Box 3 2004-02-01 19:03

All times are UTC. The time now is 13:20.

Thu Mar 4 13:20:17 UTC 2021 up 91 days, 9:31, 1 user, load averages: 4.08, 3.40, 2.95