Checking if A - B > D
nisse at lysator.liu.se
Mon Sep 15 11:41:23 CEST 2003
Torbjorn Granlund <tege at swox.com> writes:
> I and Kalle came up a solution that we think will work.
I'm afraid it won't work... See example below.
> The area tmp needs to be dn limbs long, which might be acceptable.
In my context, it's fine to overwrite d, and then we don't need a
separate tmp area.
> 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. */
This exercise is where a lot of the complexity of my code is...
> /* 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;
Consider this counter example: an = bn = 2, dn = 1, a = (0, 17) (least
significant limb first), b = (LIMB_MAX, 18), d = 2. Then a - b == 1 <
2 == d, but the test above will return false.
In the general an == bn case, we can ignore any upper equal limbs of
a and b. But then we need to handle the special case of
a = (dn low limbs), 0, ..., 0, x+1
b = (dn low limbs), LIMB_MAX, ..., LIMB_MAX, x
i.e. a difference of exactly one for the limbs above the dn least
> mpn_sub_n (tmp, a, b, n); /* cannot give carry out */
I use d instead of the tmp area, computing mpn_add_n(dp, dp, bp, n)
and compare the sum (with carry) to a. This case can be applied
whenever bn <= dn, but it is unnecessary if an is large.
More information about the gmp-devel