Typically, all computer math is done modulo 2

^{32}(or 2

^{something}, which the rest of my post trivially generalizes to). This leads to sometimes surprising effects, such as that the sum of

`a`

and `b`

, while both positive, can end up being lower than `min(a, b)`

, which is rather well-known and known as "overflow" (often treated like something bad, which it can be). Less well known is that it also means that some numbers have a multiplicative inverse, ie a number `x`^{-1}

such that `x`^{-1}x=1

.
As mentioned in the wikipedia article, the numbers which have
multiplicative inverses are precisely those coprime to the modulo. The
modulo is a power of two, which means that a number has a multiplicative
inverse iff it is odd.And it turns out to be actually useful, too. One application is, as you might guess from the title, divisibility testing.

Multiplying a number by an odd number is reversible - you can take the multiplicative inverse of the odd number and then multiply by it to get the original number back. Put differently, the function

`f(x) = x * k (for k odd)`

is a bijection. Modular multiplication is associative, so a multiple of

`k`

, say `n * k`

multiplied by `inv(k)`

(the multiplicative inverse of `k`

), is `n`

, because(n * k) * inv(k) = // use associativity n * (k * inv(k)) = // use definition of multiplicative inverse n * 1 = // multiplicative identity nThat means that in

`x * inv(k)`

, the multiples of `k`

"use up" the results from 0 through (2^{32}-1)/

`k`

, they can't be used twice because it's a bijection, leaving just the numbers bigger than (2^{32}-1)/

`k`

for non-multiples-of-k. Which suggest a very simple divisibility test:static bool IsDivisibleByOdd(uint x, uint divisor) { if ((divisor & 1) == 0) throw new ArgumentException("divisor must be odd"); uint d_inv = inv(divisor); uint biggest = uint.MaxValue / divisor; // problem right here return (x * d_inv) <= biggest; } static uint inv(uint d) { // see Hacker's Delight, // Computing the Multiplicative Inverse by Newton's Method // use extra iteration when extending to 64 bits uint x = (d * d) + d - 1; uint t = d * x; x *= 2 - t; t = d * x; x *= 2 - t; t = d * x; x *= 2 - t; return x; }And there is a problem. It didn't avoid the division, it turned it into an other division. So this doesn't actually help - in fact it's slower than the usual way. The left hand side of the division is a constant though, so unlike in the usual

`x % divisor == 0`

, the slow operation (division and modulo are slow relative to multiplication) can be done at compile time. Unfortunately, that doesn't actually help - it's one of the most common optimizations that compilers do, so it already happened automatically.But. And there is a but. If you want to test for a lot of number whether they are divisible by some

*odd number*

^{1}that doesn't vary in that test, you only have one division, one

`inv`

,
and the cost per item is only a multiplication and a test. What's more,
no compiler I know of automatically does this for you, so this can
actually save time.1. Except 1, but why would you test for divisibility by 1? I will extend this method to even numbers

**after**the next post, which will cover some concept (bits again, I haven't forgotten about them) that are necessary for it.

## No comments:

## Post a Comment