Say you’re given two numbers in the following representation:
x / y × 10 ^ a
u / v × 10 ^ b
with all the variables being integers and, in particular, y and v being always positive. How would you compare these two numbers efficiently in software? For sufficiently small numbers, it’s not a problem since we can rely on floating-point hardware. But what about exact, arbitrarily large numbers?
You could convert them both into fractions with the same denominator and then compare the integers, but that can be rather inefficient if a and b are wildly different. (Similarly, addition and subtraction can be quite expensive if a and b differ greatly, but sadly there’s no way to get around that.)
The algorithm
We can write this in the form of an inequality:
x / y × 10 ^ a ~ u / v × 10 ^ b
where the “unknown variable” to be solved is ~ and can be >, =, or <. We can manipulate this just like an equation, but with one caveat: we mustn’t multiply or divide by a number unless we are absolutely sure that it’s positive.
Since y and v are both positive, we can safely multiply by those to obtain:
x × v × 10 ^ a ~ u × y × 10 ^ b
Now let’s define some variables to clean up the inequality:
m ≡ x × v
n ≡ u × y
It’s helpful to split the variables m and n into their signs and moduli:
σ ≡ sgn m
τ ≡ sgn n
M ≡ |m|
N ≡ |n|
The inequality then becomes:
σ × M × 10 ^ a ~ τ × N × 10 ^ b
The signs σ and τ can already be used to determine the ordering in 7 out of the 9 cases:
σ τ ~
---------
−1 −1 ?
−1 0 <
−1 +1 <
0 −1 >
0 0 =
0 +1 <
+1 −1 >
+1 0 >
+1 +1 ?
That leaves us with the two nontrivial cases where both signs are positive or both signs are negative. In these cases:
σ = τ = +1 ⟹ M × 10 ^ a ~ N × 10 ^ b
σ = τ = −1 ⟹ N × 10 ^ b ~ M × 10 ^ a
We’ll consider only the first case. The second case is identical, just reversed.
The trick to making the comparisons more efficient is to use logarithms: since the logarithmic function is monotonic, they preserve the ordering and can be safely applied to both sides of the inequality:
log M + a ~ log N + b
The problem is that logarithms aren’t that easy to compute. But we can substitute this by computing floored logarithms (ilog) and its fractional part (rlog), which satisfy the following for any positive z:
log z ≡ ilog z + rlog z
0 ≤ rlog z < 1
ilog z ∈ ℕ
Floored logarithms are easy to calculate: simply combine trial division with exponential search. Here is an example of such in Haskell, based on the implementation of integerLogBase in section 14.4 of The Haskell 98 Language Report:
Applying ilog and rlog to the inequality, we obtain:
ilog M + rlog M + a ~ ilog N + rlog N + b
Notice that the fractional parts of the inequality satisfies:
|rlog N − rlog M| < 1
thus, as long as the integral parts of the inequality differ, the comparison can be done without even worrying about the the fractional parts:
ilog M + a ~ ilog N + b
Lastly, what about the situation where the integral parts are equal? We could use the fractional part of the logarithm somehow but that would introduce unnecessary complexities here. Instead, we can consult the previous equation:
M × 10 ^ a ~ N × 10 ^ b
To perform this comparison without using rational arithmetic, we can divide both sides by 10 ^ min (a, b) to make the exponent nonnegative:
M × 10 ^ (a − min(a, b)) ~ N × 10 ^ (b − min(a, b))
Now, this comparison can be computed directly using only integer arithmetic.
Algorithmic complexity
The algorithm involves performing some integer arithmetic and comparisons, as well as handling several subcases. Let
X = max(|x|, |u|)
Y = max(y, v)
A = max(|a|, |b|)
The complexity of this algorithm has no “unexpected surprises”: in the worst case, one would need to calculate the floored logarithm, which is roughly O(max (log X, log Y)). Therefore, the overall complexity is roughly:
O(max(log X, log Y, log A))
Compare this to the naive technique that involves converting both numbers into fractions, which in the worst case could be as bad as O(A).