gmp-devel Digest, Vol 1, Issue 86

Paul Zimmermann Paul.Zimmermann at
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

   Any informed opinions?

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

   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.  */

     /* 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;
       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.


More information about the gmp-devel mailing list