Bill Allombert on Mon, 12 Jan 2004 23:44:27 +0100

 some PARI kernel oddities/remarks

```Hello PARI-dev,

While trying to understand why Flx_sqr was so slow,
I found some oddities in the kernel:

1) We have two addshiftw function, one in static in the kernel
but not the other, so it is not really a bug, but probably one is
misnommed

2) level1.h include a adduumod_noofl function biut no prototype
and it seems to not being used anywhere. Do we really want that
function ? If yes we could use it in Flx_addspec if p&HIGHBIT==0

3) sqrispec include the following:

#if 0
c1 = shifti(muliispec(a0,a, n0a,na),1);
#else /* slower !!! */
t = sqrispec(t+2,lgefint(t)-2);
c1= subiispec(t+2, c1+2, lgefint(t)-2, lgefint(c1)-2);
#endif

meaning it is faster to compute (a+b)^2-a^2-b^2 than 2*a*b.
I checked that with my simple benchmark and it really make a large
difference.

Now, It tried to implement the same trick with Flx_sqrspec but there
it make things much slower...

4) In the (a+b)^2-a^2-b^2=2*a*b formula, we can detect high word
cancellation when a and are of different length (which can happen).
Is it wortwhile to implement it for t_INT ? for Flx ?

5) Is floating-point inverse or Montgomery inverse useful in this
context ?
NTL use floating-point inverse:

double ninv=1/(double)n;

/* Compute  a*b%n with 0<= a,b <n */

long MulMod(long a, long b, long n, double ninv)
{
double ab;
long q, res;

ab = ((double) a) * ((double) b);
q  = (long) (ab*ninv);   // q could be off by (+/-) 1
res = (long) (ab - ((double) q)*((double) n));
if (res >= n)
res -= n;
else if (res < 0)
res += n;
return res;
}

I suppose I will test NTL with my benchmark to start with.

Cheers,
Bill.

```