## Thursday 13 September 2012

### Divisibility and modular multiplication, even divisors

As promised, I will now expand the divisibility testing by modular multiplication algorithm to handle even divisors.

Recall that a number `y` that has a rightmost bit can be written as `y = d * 2n` where `d` is odd. A number `x` is divisible by `y = d * 2n` iff it is divisible by `2n` and by `d`. And both of those problems have already been solved in earlier posts, so:
```bool IsDivisibleBy(uint32_t x, uint32_t divisor)
{
uint32_t poweroftwo = divisor & -divisor;
uint32_t d = divisor >> bsf(divisor);
return (x & (poweroftwo - 1)) == 0 &&
(d == 1 || IsDivisibleByOdd(x, d));
}```

Pretty straightforward. Except perhaps the `d == 1` bit. Recall that `IsDivisibleByOdd` doesn't want the divisor to be one, so that case has to be avoided. And if `d` is one, that means the `divisor` was a power of two. It even works if `divisor` is one; `poweroftwo` would also be one, and `x & 0` is clearly always zero.

And `bsf` is not defined. The implementation would be strongly platform dependent, and not particularly enlightening.

Now, on to the performance part. Does this help? The answer is the same as last time - no, usually not. Except in some select cases, such as when you need to test a whole array for divisibility by the same number, which is not a compile-time constant.

Added on 29 January 2014: as Jasper Neumann pointed out, if right-rotate can be used, the part that tests whether the lower bits are zero can be merged with the other test, as described in, for example, Hacker's Delight chapter 10-16 (Test for Zero Remainder after Division by a Constant) and gmplib.org/~tege/divcnst-pldi94.pdf.

That concludes the divisibility series (for now, anyway). Next post, something completely different.