|
The top four logic sources are the first number and the bottom four are the second number. The most significant bit is on top. Orange means the top number is less than the bottom number. Light blue (or cyan if you prefer) means the top number is greater than the bottom number. Green means they’re equal.
The first step this does is a bitwise comparison. A comparison is then done between the most significant bit of each number, or if they’re equal the next bit pair down, or if they’re equal, the next bit pair down, and so on, and if all bit pairs are equal then the result is that the numbers are equal. But in a naïve implementation this has the same problem as the ripple carry adder. If all bit pairs are equal except the least significant bit of each number then the comparison will have to ripple up through every bit pair comparison stage above it, which is slow. I get around that here by using a recursive strategy so that the worst case time is reduced from O(n) to O(log n) where n is the number of bits (you may look up “big O notation” if you don’t understand what O(n) and O(log n) mean). Furthermore, by using this recursive strategy the comparison time is equal regardless of which bit pairs are and aren’t different. On the other hand, the ripple comparator compares very fast when the most significant bit of each number is different and very slow when all bit pairs except the least significant bit of each number is different.
For very low numbers of bits such as 4 as I’ve shown here, there’s very little benefit. With ripple comparison the worst case is 3 stages of propagation and for recursive it’s always exactly 2 stages. For more bits there can be much greater advantages. For 64 bits the ripple comparator’s worst case is 63 stages, but with the recursive comparator it’s always exactly 6 stages.
|
