# Part VI: A Most Significant Comparison

25 Aug 2013

As of March 2020, School of Haskell has been switched to read-only mode.

### Sections

I was going to finally get to the point, but I decided it would be good to consolidate our understanding of "the most significant difference" from the previous parts into a single short summary.

The groundhog has seen his shadow and you are in for six more weeks of winter.

# Morton Order Redux

Recall our rather boring definition of a Morton-ordered `Key`.

``````import Data.Word

-- show
data Key = Key {-# UNPACK #-} !Word {-# UNPACK #-} !Word
-- /show
deriving (Show, Read, Eq)

main = putStrLn "It typechecks."``````

I want to refactor the trick for comparing in Morton order from Part 2 that we revisited in Part 4 into a more reusable form.

To that end, let us consider how to compare two unsigned words for how they differ in the placement of their most significant bit.

Logically I want to `on compare msb`, without paying for calculating the position of the most significant bit directly.

To do I first observe that we can first compare our two values `a` and `b`.

If they match, then trivially they agree on the position of their most significant set bit!

If they don't, then either `a < b` or `b < a`.

Without loss of generality, let's assume `a < b`. Then either `a` had the same `msb` as `b` or it doesn't.

If `a` had the same `msb` as `b` then `xor a b` will not have that bit set, so `a < xor a b` will be `False` as `a` as a more significant bit set than `xor a b` does.

If `a` does not have the same `msb` as `b`, and `a < b`, then `b` has it set, and `a` does not, so the more significant bit will be set in `xor a b`, and `a < xor a b` will be `True`.

Putting all of this logic together yields the following combinator:

``````import Data.Bits
import Data.Word

-- show
compares :: Word -> Word -> Ordering
compares a b = case compare a b of
LT | a < xor a b -> LT
GT | b < xor a b -> GT
_ -> EQ

main = print \$ compares 4 7
-- /show``````

We can similarly reason through specialized scenaros to obtain `<`, `<=`, `==`, `/=`, `>=`, `>` restricted to the most significant bit.

``````import Data.Bits
import Data.Word

-- show
lts, les, eqs, nes, ges, gts :: Word -> Word -> Bool
lts a b = a < b && a < xor a b
les a b = a <= b || xor a b <= b
-- /show
eqs a b = a >= min b c && b >= max a c where c = xor a b
nes a b = a <  min b c || b <  min a c where c = xor a b
-- show ...
gts a b = a > b && xor a b > b
ges a b = a >= b || a >= xor a b

main = print \$ les 4 7
-- /show``````

With that we can see our earlier `Ord` instance for `Key` is just:

``````import Data.Bits
import Data.Word

data Key = Key {-# UNPACK #-} !Word {-# UNPACK #-} !Word
deriving (Show, Read, Eq)

lts :: Word -> Word -> Bool
lts a b = a < b && a < xor a b

-- show
instance Ord Key where
Key a b `compare` Key c d
| xor a c `lts` xor b d = compare b d
| otherwise             = compare a c
-- /show

main = putStrLn "It typechecks."``````

Now that is much easier to read:

If the most significant difference betwen `a` and `c` is less significant than the most significant difference between `b` and `d`, then we should just compare `b` and `d`, otherwise we compare `a` with `c`.

# One of these things is not like the others

This makes it clear why we had three uses of `xor` in the original, the first two were to calculate the differences themselves, while the last `xor` was simply to compare by most significant bit!

Switching to these internally made almost a factor of two difference in the performance of the overall multiplier relative to actually performing the masking! This bodes well for the practicality of the as-yet-still-unbenchmarked `IntMap` alternative described in part 4.

August 25 2013

P.S. This also means I effectively just claimed No-Prize #5 for myself. ;)

comments powered by Disqus