gmp-devel Digest, Vol 1, Issue 86

[Paul Zimmermann]

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