gmp-devel Digest, Vol 1, Issue 86
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
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. */
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)
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