fast integer division

[David Hough]

There are lots of fascinating possibilities here, to the extent that I
lost sight of my most important constraint, that in converting between
base 10**4 and base 2**16, the long unsigned
dividend can be almost as large as (2**16)*(10**4), and so none of
the methods Mike Powell (the one at Sun, not Cambridge) or Tim suggested
are applicable.  Tim was right, I was thinking in terms of an upper bound
on the dividend of 2**16.

> They're exactly the same "binary search" algorithm, just written in
> ways that are likely to work faster under different kinds of
> optimizers and architectures.

Conditionals are bad news, so putting in a switch statement in my code
or a binary search in Tim's may be an ephemeral advantage.  You can
make multiplies faster with a bigger hardware array but conditional branches
are just getting (relatively) slower.

Earl Killian pointed out that there's an interesting discussion of this
stuff in section 4.4 in volume 2 of Knuth, especially exercise 9.