Thread: Parameter Underestimation View Single Post
2010-09-29, 03:38   #3
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by R.D. Silverman I just found an interesting bug in my siever. I discovered it while making some improvements, including a larger sieve region. Here is one instance. For special_q = 256300217 with root 137499035, my lattice reduction routine returned (36738082, 6593) (137499035, 1) This is not correct. The problem, of course is integer overflow. The routine uses signed ints. Of course, since the reduced lattice is wrong, everything that follows is wrong and no relations get produced. I had been getting a very low relation yield rate for the larger special q's on my current factorization. This explains it. I've been losing valid relations. I am going to have to change the latred routine to use 64 bit ints.
I just realized that there are other problms as well.

We hope that norm(c + d alpha) is smooth. Let v1, v2 be the reduced
lattice row vectors for some special_q. Then (c,d) = i*v1 + j*v2
where (i,j) is a point in the reduced lattice. i and j are bounded by
the size of the sieve region, but for large special_q, it is possible that
eiither i*v1 or j*v2 (or both) may overflow, giving a wrong value for
c and/or d when they are defined as signed 32-bit ints.

I will need to deal with this as well.

Does anyone know if GGNFS uses 64-bits for any/all of these variables?

For 2,2166L, I am now sieving special_q near 250 million. The average yield
is now only about 3 relations/q. A fair fraction of the q's produce no relation
at all. I may need to fix my code, and go back and RESIEVE a large
set of q's that I have already done.