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. ;)