LATRED
 

It is necessary in any NFS implementation to have a fast
lattice reduction routine. Cancel that. A very very fast lattice
reduction routine.

Is anyone interested in a cross-comparison of such? I'd be
willing to post my code if there is any interest. Let's see
who has the fastest routine. mine? msieve? GGNFS? other?

The 2x2 lattice reduction used in the GGNFS lattice siever is [url="http://ggnfs.svn.sourceforge.net/viewvc/ggnfs/trunk/src/lasieve4/redu2.c?view=markup"]here[/url]

The CADO code is in the function reduce_plattice, defined [url="http://gforge.inria.fr/plugins/scmsvn/viewcvs.php/trunk/sieve/las.c?rev=8&root=cado-nfs&view=markup"]here[/url]

Msieve doesn't have a lattice sieve.

Did you ever get a chance to think about modifying the reduction process to somehow salvage special-q that would otherwise generate highly-skewed lattices?

[QUOTE=jasonp;186505]The 2x2 lattice reduction used in the GGNFS lattice siever is [url="http://ggnfs.svn.sourceforge.net/viewvc/ggnfs/trunk/src/lasieve4/redu2.c?view=markup"]here[/url]

The CADO code is in the function reduce_plattice, defined [url="http://gforge.inria.fr/plugins/scmsvn/viewcvs.php/trunk/sieve/las.c?rev=8&root=cado-nfs&view=markup"]here[/url]

Msieve doesn't have a lattice sieve.

Did you ever get a chance to think about modifying the reduction process to somehow salvage special-q that would otherwise generate highly-skewed lattices?[/QUOTE]

Yes, I did. I can change a #define parameter in my code to relax or restrict
requirements on the condition number of the lattice before accepting it.

[QUOTE=R.D. Silverman;186508]Yes, I did. I can change a #define parameter in my code to relax or restrict
requirements on the condition number of the lattice before accepting it.[/QUOTE]

I will do some benchmarks on the lattice routines and report back.
This may take some time, I am busy with real (tm) work.

I need to finish testing it, but I may have a change to make to the ggnfs code. It would only affect certain pathological cases significantly, but I'm curious how it would affect others. If I find some time, I may run some tests to see.

There was a problem with certain special-q and lattices getting into an infinite loop. I've been reading the Franke and Kleinjung paper, and the rounding used by the lattice reduction in ggnfs is wrong. It was rounding to nearest, and getting into a loop where the a sequence (variable k in the code) would calculate to something like .53, rounds to 1, next is -.53, rounds to -1, next is .53, etc. The version of the paper I have says round toward 0.

[QUOTE=joral;186531]I need to finish testing it, but I may have a change to make to the ggnfs code. It would only affect certain pathological cases significantly, but I'm curious how it would affect others. If I find some time, I may run some tests to see.

There was a problem with certain special-q and lattices getting into an infinite loop. I've been reading the Franke and Kleinjung paper, and the rounding used by the lattice reduction in ggnfs is wrong. It was rounding to nearest, and getting into a loop where the a sequence (variable k in the code) would calculate to something like .53, rounds to 1, next is -.53, rounds to -1, next is .53, etc. The version of the paper I have says round toward 0.[/QUOTE]

[CODE]
/************************************************************************/
/* */
/* routine to compute two reduced lattice vectors */
/* borrowed from AKL; which explains stylistic differences in code */
/* this routine is old; I re-wrote it; the new one is much faster */
/* */
/************************************************************************/

reduce_lattice(special_q, root, v1, v2)
int special_q, root;
int *v1, *v2;

{ /* start; of reduce_lattice */
double stime;
long x1;
long yy1 = 0;
long x2;
long y2 = 1;
long x3;
long y3;
double s2;
double s3;
long q;
long sx2;
long parity = 0;
//int v1a[2], v2a[2];

#if (FEWERDIVLATRED | NODIVLATRED)
double s2_2;
double s2_4;
double s2_8;
double s2_16;
#endif

if (TIME_STATS) stime = get_time();

x1 = special_q;
x2 = root;

s2 = x2 * (double) x2 + y2 * (double) y2;

for (;;)
{
x3 = x1;
y3 = yy1;
sx2 = (x2 << 4);
while (x3 > sx2 )
{
x3 -= sx2;
y3 -= (y2 << 4);
}
sx2 >>= 1;
if (x3 > sx2 )
{
x3 -= sx2;
y3 -= (y2 << 3);
}
sx2 >>= 1;
if (x3 > sx2 )
{
x3 -= sx2;
y3 -= (y2 << 2);
}
sx2 >>= 1;
if (x3 > sx2 )
{
x3 -= sx2;
y3 -= (y2 << 1);
}
if (x3 > x2 )
{
x3 -= x2;
y3 -= y2;
}
if (x3 > (x2 >> 1))
{
x3 -= x2;
y3 -= y2;
}
if (x3 < 0)
{
x3 = -x3;
y3 = -y3;
parity ^= 1;
}

s3 = x3 * (double) x3 + y3 * (double) y3;
if (s3 >= s2) break;
s2 = s3;
x1 = x2;
yy1 = y2;
x2 = x3;
y2 = y3;
parity ^= 1;
}

#if (FEWERDIVLATRED | NODIVLATRED)
s3 = x2 * (double) x3 + y2 * (double) y3;
if (s3 < 0)
{
yy1 = 1;
s3 = -s3;
}
else
{
yy1 = 0;
}
s2_2 = s2 + s2;
s2_4 = s2_2 + s2_2;
s2_8 = s2_4 + s2_4;
s2_16 = s2_8 + s2_8;
q = 0;
#ifdef NODIVLATRED
while (s3 > s2_16)
#else
again:
if (s3 > s2_16)
#endif
{
s3 -= s2_16;
q += 16;
}
if (s3 > s2_8)
{
s3 -= s2_8;
q += 8;
}
if (s3 > s2_4)
{
s3 -= s2_4;
q += 4;
}
if (s3 > s2_2)
{
s3 -= s2_2;
q += 2;
}
if (s3 > s2)
{
s3 -= s2;
q ++;
}
#ifndef NODIVLATRED
if (s3 > s2)
{
if (s3 < (s2_16+s2_16)) goto again;
q += (long)mrint(s3/s2);
}
else
#endif
if ((s3+s3) >= s2) q ++;
if (yy1) q = -q;
#else
q = (long) mrint( (x2 * (double) x3 + y2 * (double) y3) / s2 );
#endif

v2[0] = x2;
v2[1] = y2;
v1[0] = x3 - x2 * q;
v1[1] = y3 - y2 * q;

if (v2[1] < 0) /* make 'b' positive */
{
v2[0] = -v2[0];
v2[1] = -v2[1];
}

if (v1[1] < 0) /* make 'b' positive */
{
v1[0] = -v1[0];
v1[1] = -v1[1];
}

if (TIME_STATS) latred_time += (get_time() - stime);
//qtime = (get_time() - stime);

//time = get_time();
//newest_latred_exp(special_q, root, v1a, v2a);
//ttime = (get_time() - stime);

//printf("old, new = %lf %lf\n", qtime, ttime);
//printf("RATIO: %lf\n", qtime/ttime);
//tot1 += qtime;
//tot2 += ttime;

//cmp_latred(special_q, root, v1,v2, v1a, v2a);

return(parity);
} /* end of reduce_lattice */
[/CODE]

[QUOTE=jasonp;186505]The 2x2 lattice reduction used in the GGNFS lattice siever is [url="http://ggnfs.svn.sourceforge.net/viewvc/ggnfs/trunk/src/lasieve4/redu2.c?view=markup"]here[/url]

The CADO code is in the function reduce_plattice, defined [url="http://gforge.inria.fr/plugins/scmsvn/viewcvs.php/trunk/sieve/las.c?rev=8&root=cado-nfs&view=markup"]here[/url]

Msieve doesn't have a lattice sieve.

Did you ever get a chance to think about modifying the reduction process to somehow salvage special-q that would otherwise generate highly-skewed lattices?[/QUOTE]

Woukdn't be faster the codes by removing the asserts?

[QUOTE=R. Gerbicz;186539]Woukdn't be faster the codes by removing the asserts?[/QUOTE]

Actually, they should not affect the "production" compilation of the code.
assert is usually defined as a macro. In the "production" version, it transforms into nothing and, thus, does not affect the compiled code.

In the "debug" version, the assertion is actually tested. This does slow things down, but also helps catch errors.

Can we verify that the assertions are in fact turned off during production builds of this code? This is not a given, and I've seen production code ship with assertions turned on mistakenly, either because someone forgot to turn them off or because the process of turning them off is so complex (e.g. 8 levels of interlocking preprocessor defines) that nobody can figure out how anymore.

[QUOTE=jasonp;186577]Can we verify that the assertions are in fact turned off during production builds of this code?[/QUOTE]

The easiest way that I can think of to test that assertions are not active is to intentionally insert an assertion that will fail. Then try it and see what happens.

However, like everything else, you really need to try this in every environment. One of the difficulties in working on cross-platform code is that each platform introduces its own "quirks".