1870L : Yield Rate

[R.D. Silverman]

Originally Posted by Batalov

Even KF siever gets strained on quartics above 230. Around 230 is where the 16e siever becomes a good contender (it is a bit slower, but yields not 2 but almost 3 times more, and that allows to sieve in a lesser range and with twice lower FB limits; and given that, it goes on par if not better than 15e). Also around 230, LP limits will have to be doubled (viz. 30/32).

For "normal" numbers, 16e becomes useful only around 270. So there, again, roughly quartics-230 are as hard as sextics-270.

2,1870L is ~225 digits.

[frmky]

Originally Posted by R.D. Silverman

For you inputs: what are the last 4 parameters? mfba, mfbr, alambda, rlambda?

The binary uses MPQS on numbers up to mfba/r in size. I've never fully understood the purpose of lambda, but it likes to be about log(2^mfbr)/log(rlim), and likewise for the algebraic side, in size. In practice, for reasonable parameters about 2.6 for two LP's and 3.6 for three LP's works well.

The relations found are attached in a format hopefully close enough to CWI to be clear.

[R.D. Silverman]

Originally Posted by frmky

The binary uses MPQS on numbers up to mfba/r in size. I've never fully understood the purpose of lambda, but it likes to be about log(2^mfbr)/log(rlim), and likewise for the algebraic side, in size. In practice, for reasonable parameters about 2.6 for two LP's and 3.6 for three LP's works well.

The relations found are attached in a format hopefully close enough to CWI to be clear.

Thanks for the relations. I have found out why my yield was so low.
It was not a code bug, but rather a parameter selection related to
setting the sieve threshold. I changed the parameters and am now getting
close to the yield you reported earlier. "close" means about 7.7 relations
per q for 8k x 16K, rather than the 8.5 you reported. However, the
difference does have me concerned. I played around with varying the
sieve threshold, and this was the best yield I could get. There may still be
a bug in the siever; from my prior experience with debugging sievers,
this can be the worst kind of bug to track down: not finding relations that
it should.

Having your data makes debugging easier. I can determine what relations
were missed by my code, and instrument the code to look at the (c,d)
locations that were missed. This sort of thing is time consuming.....

Other possibilities: The lattice reduction can be done in a variety of
ways. It may be the case that slightly better reductions could be obtained
in my code by a slightly different algorithm.

If indeed there is a bug, I think the most likely place to look is in the
computation of the sieve boundaries for each ideal. In Pollard-style
lattices, we do a reduction on each ideal. Call it v1, v2. (as vectors).
We sieve over a sub-lattice. Let [0,N], [-M, M] be the sieve boundaries.
We sieve over a region (e,f) such that the following inequalities hold:

(0, -M) < e * v1 + f * v2 < (N, M)

The region (e,f) for which this holds is an affine transform of the
rectangular region that is 2M x N. This transform produces a
(skewed) parallelogram. We need to find all (e,f) values inside this
parallelogram. Then we have (c,d) = e*v1 + f*v2. For speed reasons,
I do a good but not guaranteed perfect approximation to this region.
Thus, some lattice points might get missed.

The primary thing that makes GGNFS faster is that it uses a different
approach to finding the lattice points to hit: It does not compute this
skewed region, nor does it do a full lattice reduction on all of the ideals.

I also suspect that it has better memory management. My siever is
not very memory efficient.

Comments/discussion is solicited.

[R.D. Silverman]

Originally Posted by frmky

The binary uses MPQS on numbers up to mfba/r in size. I've never fully understood the purpose of lambda, but it likes to be about log(2^mfbr)/log(rlim), and likewise for the algebraic side, in size. In practice, for reasonable parameters about 2.6 for two LP's and 3.6 for three LP's works well.

The relations found are attached in a format hopefully close enough to CWI to be clear.

I understand the purpose of lambda. My code has the same thing
in a different form.

Suppose LPR is the rational side large prime bound.

Then any cofactor that is bigger than LPR^2 will
be useless. However, any cofactor that is very near to LPR^2 is
unlikely to factor into two primes less than LPR. It will most likely factor
into something smaller than LPR and something bigger than LPR.

Thus, we might want to give a hint to the code saying, in effect,
we will accept LP's up to 'LPR', but don't bother trying to split anything
bigger than some chosen bound which might be selected somewhat
smaller than LPR^2. In GGNFS, this bound appears to be 2^lambda.

Comments solicited.

[R.D. Silverman]

Originally Posted by Batalov

For "normal" numbers, 16e becomes useful only around 270. So there, again, roughly quartics-230 are as hard as sextics-270.

Can others corroborate this? I thought that 230-digit quartics would
be equivalent to somewhere around a C255 to C260 sextic.

270 "seems" to be high. But I could be very wrong.

[R.D. Silverman]

Originally Posted by frmky

Yep, that's low. Using

n: <the number>
skew: 1.41
c4: 1
c3: -2
c2: -6
c1: 12
c0: -4
Y1: 2^93
Y0: -(2^187+1)
alim: 14500000
rlim: 86000000
lpba: 30
lpbr: 31
mfba: 60
mfbr: 62
alambda: 2.6
rlambda: 2.6

which I believe matches your parameters, and sieving using 14e (which has a slightly smaller sieve area of 16K x 8K), I sieved the range q = 60M to 60M+500. There were 27 special-q in the range, and it found 229 relations at a rate of 0.64 sec/relation on the slow Opteron (a Core 2 would get under 0.4 sec/relation). This is about 8.5 rels/special-q using a smaller sieve region.

Do you think that the factor bases need to be bigger?

[jrk]

Originally Posted by R.D. Silverman

I understand the purpose of lambda. My code has the same thing
in a different form.

Suppose LPR is the rational side large prime bound.

Then any cofactor that is bigger than LPR^2 will
be useless. However, any cofactor that is very near to LPR^2 is
unlikely to factor into two primes less than LPR. It will most likely factor
into something smaller than LPR and something bigger than LPR.

Thus, we might want to give a hint to the code saying, in effect,
we will accept LP's up to 'LPR', but don't bother trying to split anything
bigger than some chosen bound which might be selected somewhat
smaller than LPR^2. In GGNFS, this bound appears to be 2^lambda.

Comments solicited.

That's not what lambda is for. What you are describing is what the mfbX parameters do in GGNFS (specified in bits). So for example a lpb of 30 and mfb of 60 means we allow large primes up to 2^30 and we split cofactors up to 2^60.

The way I understand it (which may well be wrong) is that, since the sieve values are only represented in bytes, we won't know exactly how big the cofactor is until the trial division is actually done. The lambda specifies the threshold for which trial division will be used on the sieve values. The larger the lambda, the more values will be trial-divided, but more of those values will be false hits as well. Experiment shows that a good lambda is slightly larger than log(2^mfbX)/log(Xlim) where mfbX is the cofactor bound in bits and Xlim is the small prime bound. Specifying lambda to be too much larger than this causes too much time to be wasted on false hits, whereas a lambda which is smaller than this throws away too many good relations.

I hope my understanding is accurate.

[bsquared]

Originally Posted by jrk

That's not what lambda is for. What you are describing is what the mfbX parameters do in GGNFS (specified in bits). So for example a lpb of 30 and mfb of 60 means we allow large primes up to 2^30 and we split cofactors up to 2^60.

The way I understand it (which may well be wrong) is that, since the sieve values are only represented in bytes, we won't know exactly how big the cofactor is until the trial division is actually done. The lambda specifies the threshold for which trial division will be used on the sieve values. The larger the lambda, the more values will be trial-divided, but more of those values will be false hits as well. Experiment shows that a good lambda is slightly larger than log(2^mfbX)/log(Xlim) where mfbX is the cofactor bound in bits and Xlim is the small prime bound. Specifying lambda to be too much larger than this causes too much time to be wasted on false hits, whereas a lambda which is smaller than this throws away too many good relations.

I hope my understanding is accurate.

That is the way I understand it as well.

From the file INSTALL.and.USE

Sieve report bound lambda:
# All sieve reports for which the sieve value is at least
# log(abs(polynomial value))-lambda*log(factor base bound)
# will be investigated by the trial division sieve.


The selection of the third field (called lambda) of the last two lines requires
some care. If lambda is too large, then the trial division sieve will dominate
the run time without producing more useful sieve reports than the optimal
value. If it is too small, sieve reports will be lost, and you will be forced
to sieve more special q.

[R.D. Silverman]

Originally Posted by bsquared

That is the way I understand it as well.

From the file INSTALL.and.USE

Ah. My code has the same parameters.. I call them INT_TOL and
ALG_TOL (for tolerance).

[Raman]

Originally Posted by Raman

For 5,415+ I sieved upto 190 million range of special-q upon that rational side, from (110M-300M) with help of gnfs-lasieve4I15e. I presume that was anyway oversieved, 170M range would have been enough in order to build a matrix.

I got matrix of 14332614 rows, it will take upto 11 more days in order to finish off, at this moment. It is 68% done.

For rest of numbers, I only expect around 220 million range of special-q each, upon every number (on the rational side) over that average scale.

Well, let me add that for 2,935- I sieved all special-q from 50M to 150 M (that is 100 million range for that values of special-q), with rlim = 150 million, alim = 25 million.

I sieved upon that rational side; final matrix had got 9.66 million rows,
sieved up entirely with gnfs-lasieve4I15e lattice siever.

Ok, what happened to that number?
2,881+ it is rather made available again?
I would rather like to see up with that number to finish off sometime sooner itself.

[R.D. Silverman]

Originally Posted by jasonp

The KF siever does not explicitly declare the entire rectangular (c,d) plane when sieving by vectors; instead it uses a continued-fraction-based method to determine the approximate region of the (c,d) plane where each factor base entry will hit next, then bucket sorts based on that. While I haven't examined the source closely, it probably fills up a small rectangle of the (c,d) plane at a time.

I don't see how it can do that. Suppose for a given special q, we are
sieving one ideal with norm p. The hits that p takes will be all over the
(c,d) plane. How can one restrict to some subset of the plane?

I assume that as p is sieving, a bucket is filled with the (c,d) values,
along with log(p). When a bucket gets full (whatever its size is),
you sort on the values of c as primary index, followed by a sort on d.
You can then dump the bucket into the sieve array by going accross
a row, in order of increasing d.

An individual bucket is also kept small enough so that it fits in cache
while it is being filled. My buckets use shorts for (c,d) and a single byte
for log(p).

One row of the sieve array is around 8K in length and thus fits in the L2
cache. Thus, emptying the bucket remains in cache.