Checking if A - B > D

[Niels Möller]

When evaluating Jebelean's criterion for matching partial quotient
sequences (this is in the context of gcd computation), I need to check if

  A - B < D

where A > B.

What's the best way to do this, using mpn functions? A and B are often
much larger than D, and I'd prefer not using temporaries larger than
D. In particular, I'd prefer not having to actually compute the
complete difference A - B.

I'll describe one way of doing this, and I wonder if there's any
better way:

1. If A < D or A < B, return true.

Ok, now A is larger than D, potentially much larger. Let k = size(D),
and let W be 2^{limb size}, e.g W = 2^32.

2. Write A = W^k a + A', B = W^k + B', with all of A', B' and D < W^k

The condition is now equivalent to

  (a - b) W^k < D + B' - A'

On the left hand side, we always have a - b >= 0 (since A >= B). On the
right hand side, we have

  -W^k < D + B' - A' < 2 W^k

3. If a - b >= 2, return 0 (more on this below).

4. Compute D + B', of size k + 1.

5. If D + B' < A', return 0.

6. Compute D + B' - A', of size k + 1.

7. If D + B' - A > W^k, return true.

8. Now, D + B' - A <= W^k. Return true if a == b, otherwise false.

The most crucial operation here is step 3. What's the most efficient
way of checking if a - b >= x, where x is a one limb value? One way
might be as follows:

Locate the most significant limb where a and b differ, say it's limb
l. Compute the one limb difference y = a[l] - b[l] (this is almost
what mpn_cmp does). If l = 0 (least significant), then check if y >=
x.

If l != 0, check if y >= 2, if it is, then surely a - b > x. Remaining
case is y = 1. In this case, compute a[0..l-1] - b[0..l-1] + x, but
keep only the carry.

So some function that would help doing this test efficiently is

  * variants of mpn_add_n and mpn_sub_n which take the input
    carry/borrow as an argument, and

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

  * a one-limb subtraction function that computes a - b and returns

    UNDERFLOW if a < b
    OVERFLOW if a - b is larger than one limb
    a-b, if it fits in one limb.

Ah, and one more thing, I often find that I often do

  if (a >= b)
    { compute and use a - b }

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? 

Comments?

/Niels