20081017, 20:41  #1 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3^{2}×17×61 Posts 
Let's fix the elusive siever bug
Well, many of you heard of this bug. A few probably had it happen to them. It happens rarely but deadly. The siever enters infinite loop (doesn't crash) and can stay in it for hours or days. I've now caught and singled out a particular case. It is very small and that may help debugging.
Description: gnfslasieve4INNe enters infinite loop. Debug case: bug.poly: Code:
n: 75229857442823839063327954585610815916921620664868103784648473223197175129674845956583458783493459542969045721078101701111280306855293361344591 m: 1000000000000000000000000000000000 c5: 1300 c0: 23 skew: 0.45 type: snfs rlim: 3050000 alim: 5500000 lpbr: 27 lpba: 27 mfbr: 54 mfba: 54 rlambda: 2.6 alambda: 2.6 # # here's the commandline to get into infinite loop # # gnfslasieve4I13e r bug.poly f 3089717 c 100 o test.out # gnfslasieve4I12e r bug.poly f 3089717 c 100 o test.out # Greg, Paul, guys? Serge 
20081017, 22:57  #2 
(loop (#_fork))
Feb 2006
Cambridge, England
2·3,191 Posts 
It looks as if the problem's in the 'reduce2' routine; just waiting for it to freeze and breaking in with gdb always gives me a spot in reduce2.
Specifically, it looks as if calling reduce2 with a0=3089729 b0=0 a1=1550102 b1=1 sigma=0.2025 hangs; it gets into a cycle Code:
s=28413.312500 a0sq=34032648.000000 a1sq=56826.562500 s=28413.312500 a0sq=34032648.000000 a1sq=56826.562500 reduce2 is not a routine called very often (once per specialQ) so the right answer is probably to do it in exact mpz_t/mpz_t rational arithmetic; but replacing 'float' with 'double' throughout (except in the function signature) at least gives a version which runs through your bugged case. Thanks very much for the test case! Last fiddled with by fivemack on 20081017 at 22:59 
20081018, 00:54  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3^{2}·17·61 Posts 
P.S. Remarkably, just now, this otherwise uneventful factorization ended with a fiasco (51 failed sqrts), and I am now (short of any other reasons) thinking that any relations that were produced while (or just before) the siever hung were somehow poisonous to the matrix. BL finished in due time with 51 nontrivial dependencies that turned out to be rather trivial (~160 cycles in each). See the log, attached.
Interesting! (maybe a coincidence of course) I am sieving some more and will report if/when I will get to understand it better. Maybe the factors will shed the light on why it is unstable in reduce2 and in later in algebra. 
20081018, 02:59  #4  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10010001110101_{2} Posts 
Quote:
Code:
//replace for(;;) { n_iter++; } //by i32_t iter; for(iter=0; iter<1024; iter++) { } n_iter += iter; This can most possibly be improved (but not with mpz's  because sigma=skew² is not integer anyway). Serge 

20081018, 12:43  #5 
Mar 2008
5·11 Posts 
I've been doing some experimenting with this since last night, and it strikes me that it is basically the extended euclidean algorithm used in some way to find a short vector pair for the lattice. I know when doing this other ways, I've normally rounded down rather than to nearest.
Using rint() causes the calculation to cycle between these two points. Code:
iter a0 b0 a1 b1 k ... 114126, 3149, 10913, 198, 295, 1 114127, 3347, 10618, 198, 295, 1 ... Code:
iter a0 b0 a1 b1 k ... 12, 3347, 10618, 198, 295, 1 ... 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
QS Lattice Siever  R.D. Silverman  Factoring  31  20181008 17:17 
Compiling 64 bit lattice siever on gcc 4.8.5  chris2be8  Factoring  6  20180206 17:22 
Adventures with 16f siever  VBCurtis  Factoring  6  20180124 11:06 
A siever for K (b, n, c fixed)?  pepi37  Software  7  20150710 04:42 
Anyone have any trouble with the 15e ggnfs siever?  schickel  Factoring  12  20100930 08:44 