## 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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.94044816,"math_prob":0.9142512,"size":1555,"snap":"2022-40-2023-06","text_gpt3_token_len":417,"char_repetition_ratio":0.10444874,"word_repetition_ratio":0.0072727273,"special_character_ratio":0.25916398,"punctuation_ratio":0.1341853,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9744087,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-10-05T10:59:19Z\",\"WARC-Record-ID\":\"<urn:uuid:15ae66c2-5312-4c6a-9547-d92dcfa6008a>\",\"Content-Length\":\"53831\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:4760154a-6662-4516-880d-17451187d439>\",\"WARC-Concurrent-To\":\"<urn:uuid:e534281d-5efa-43c7-a590-f4845fe17487>\",\"WARC-IP-Address\":\"142.251.163.132\",\"WARC-Target-URI\":\"http://bitmath.blogspot.com/2012/09/divisibility-and-modular-multiplication_13.html\",\"WARC-Payload-Digest\":\"sha1:YTKJTBJT4DWDVYG4VCEVQNQPBVHYCBO7\",\"WARC-Block-Digest\":\"sha1:E5YB2EHEIUV7DTNEVJPVCNI6OOMMJBO4\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-40/CC-MAIN-2022-40_segments_1664030337625.5_warc_CC-MAIN-20221005105356-20221005135356-00201.warc.gz\"}"}