Checking if A - B > D
user42 at zip.com.au
Tue Sep 16 08:34:39 CEST 2003
Paul.Zimmermann at loria.fr (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
More information about the gmp-devel