# gmp-devel Digest, Vol 1, Issue 86

Paul Zimmermann Paul.Zimmermann at loria.fr
Mon Sep 15 15:27:17 CEST 2003

```Two answers to today's digest:

To accomodate vector machines, we might want to put mpn_mul_n,
mpn_sqr_n, mpn_mul, and the various karatsuba and toom routines
in a single file.  Or, we might want to move mpn_sqr_n to
mul_n.c.

Any informed opinions?

Perhaps we could put all squaring functions in sqr_n.c, while still
including them in mul_n.c...

int
nisse (mp_srcptr ap, mp_size_t an, mp_srcptr bp, mp_size_t bn, mp_srcptr dp, mp_size_t dn)
{
/* Check an, bn, dn for trivial cases where the sizes of these alone
can determine A - B < D.  Left as an exercise to the user.  */
foo;

/* Here assume that an = bn, dn < an.  */
for (i = dn; i < an; i++)
{
if (ap[i] != bp[i])
{
/* We found a difference at higher significance that MSB of D.  */
return NO;
}
}

This could be replaced by mpn_cmp (ap + dn, bp + dn, an - dn), isn't it?

mpn_sub_n (tmp, a, b, n);	/* cannot give carry out */
if (mpn_cmp (tmp, dp, n) < 0)
return YES;
else
return NO;
}

This is O(n) while on average only O(1) work is required.
Since we know a > b, it would be better to compute an
approximation of a-b from left to right (which may be at
most one bit wrong) and compare it to d.

Paul
```