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](https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication/) into a single short summary.

The [groundhog](http://en.wikipedia.org/wiki/Punxsutawney_Phil) 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`.

```active haskell
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](http://en.wikipedia.org/wiki/Z-order_curve) from [Part 2](https://www.fpcomplete.com/tutorial-edit/revisiting-matrix-multiplication/part-2) that we revisited in [Part 4](https://www.fpcomplete.com/tutorial-edit/revisiting-matrix-multiplication/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:

```active haskell
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.

```active haskell
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:
  
```active haskell
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](http://www.youtube.com/watch?v=FClGhto1vIg&t=11s)
==========================================

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](https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication/part-4).

-[Edward Kmett](mailto:ekmett@gmail.com)

August 25 2013

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