Waldir Pimenta asked me whether it is possible to test the condition
max(a,b) / min(a,b) < r
without computing max(a, b) or min(a, b). Here a> 0, b> 0, and r > 1. (If r ≤ 1, the condition is always false.) The inequality has to be evaluated in an inner loop of a real-time image processing application and so the time saved by avoiding computing the max and min might matter.
We can multiply the original inequality by min(a, b) since a and b are positive. The condition becomes
max(a, b) < r min(a, b) = min(ra, rb).
We then expand this inequality into four simple inequalities:
a < ra
b < ra
a < rb
b < rb
Since r > 1, we know that a < ra and b < rb and so we only need to check a < rb and b < ra. In C notation we would evaluate
( a < r*b && b < r*a )
rather than
( max(a,b) / min(a,b) < r )
Whether this saves any time depends on context, though it’s plausible that the former might be more efficient. Some portion of the time the condition a < r*b will evaluate to false and the second half of the condition will not be evaluated.
(C evaluates an expression like (p && q) from left to right. If p is false, q is not evaluated since it is known at that point that the expression (p && q) will evaluate to false regardless of the value of q.)
Challenge: How often will the condition a < r*b evaluate to false? What are your assumptions? Leave your answers below.
Update: Combining the ideas of Carlos Santos and Christian Oudard in the comments below, you could implement the inequality as
a < b ? (b < r*a) : (a < r*b)
There are too many other good ideas in the comments for me to keep editing the blog post so I’ll just ask that you scroll down. I’m surprised at all the ideas that came out of evaluating a simple expression.
