Checking if A - B > D

Kevin Ryde user42 at
Tue Sep 16 08:34:39 CEST 2003

Paul.Zimmermann at (Paul Zimmermann) writes:
> This is O(n) while on average only O(1) work is required.
> Since we know a > b, it would be better to compute an
> approximation of a-b from left to right (which may be at
> most one bit wrong) and compare it to d.

Yep.  Probably a little tricky, but it'd be one those "almost always"
things getting an answer in just one or two limbs.

There's a tasks list entry to do something vaguely similar for
mpq_cmp_ui, where n1*d2 <=> n2*d1 must be compared, which can be done
by working from high to low allowing for carries from the as-yet
uncalculated part.

More information about the gmp-devel mailing list