Checking if A - B > D
Niels Möller
nisse at lysator.liu.se
Fri Sep 12 13:31:57 CEST 2003
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
More information about the gmp-devel
mailing list