Checking if A - B > D

[Niels Möller]

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.

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

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
significant.

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

/Niels