Checking if A - B > D

Kevin Ryde user42 at
Tue Sep 16 08:36:18 CEST 2003

nisse at (Niels Möller) writes:
>   * variants of mpn_add_n and mpn_sub_n which take the input
>     carry/borrow as an argument, and

mpn_add_nc and mpn_sub_nc exist for some chips (the x86s mainly),
otherwise it's a case of using plain mpn_add_n then mpn_add_1.

>   * returns the output carry, without storing the rest of the result.

Oh, well, I guess the sub in that case is the same as mpn_cmp.  The
add could no doubt be done as another high to low limb examining

> I believe this is a little more efficent, as mpn_cmp usually only
> needs to look at a few of the most significant limbs, and it seems
> liek a waste to compute the complete difference, find that it is
> negative (the borrow returned from mpn_sub*), and throw away the
> computed value. Is there a better way of doing this, i.e. computing a
> difference only if it is non-negative? 

A compare before subtracting is about right.

I guess the compare loop could give the location of the highest limb
difference as well as the comparison result.  That might occasionally
reduce the work for the subtract.  All compares should be done inline,
so the limb location would be available immediately, no extra cost.

More information about the gmp-devel mailing list