Mod­ulo and di­vi­sion with a power of two right hand side

$a \mod 2^k$ and $\frac{a}{2^k}$, can be re­writ­ten as $a \land (2^k - 1)$ and $a \gg k$ re­spect­ively. This ex­ploits the bin­ary rep­res­ent­a­tion of un­signed in­tegers and will com­plete in one or two cycles, com­pared to a few dozen for the ori­ginal op­er­a­tion.

For the sake of ex­ample con­sider a 4-bit in­teger with bits $b_3$, $b_2$, $b_1$ and $b_0$ di­vided by $2^k$:

$$\frac{b_3 \times 2^3 + b_2 \times 2 ^ 2 + b_1 \times 2 ^ 1 + b_0 \times 2 ^ 0}{2^k} = b_3 \times 2^{3-k} + b_2 \times 2 ^ {2 - k} + b_1 \times 2 ^ {1 - k} + b_0 \times 2 ^ {0 - k}$$

Know­ing that a 4-bit in­tegers can­not rep­res­ent any di­gits other than $b_3$ to $b_0$ and that all the other di­gits are dropped (or “trun­cated”), it be­comes fairly easy to see why di­vi­sion by $2^k$ and right shift by $k$ po­s­i­tions are equi­val­ent. This trivi­ally ex­tends to un­signed in­tegers of any width.

In or­der to see why a num­ber mod­ulo $2^k$ is equi­val­ent to a num­ber masked by $(2^k - 1)$, first con­sider that $2^k - 1$ will have k low­est bits set to $1$. For ex­ample:

$$2^3 - 1 = 7 = 111_2$$ $$2^8 - 1 = 255 = 1111\ 1111_2$$ $$2^16 - 1 = 65535 = 1111\ 1111\ 1111\ 1111_2$$

An un­signed in­teger, masked with a mask like this will be able to rep­res­ent num­bers from 0 to $2^k-1$, in­clus­ive. This hap­pens to ex­actly match the range of rep­res­ent­able in­tegers mod­ulo $2 ^ k$. This, much like the di­vi­sion op­tim­isa­tion, comes out from how the in­tegers are rep­res­en­ted in bin­ary.

The com­piler will usu­ally re­write these op­er­a­tions to a more ef­fi­cient ver­sion by it­self, how­ever it can only do so when it has the know­ledge about val­ues be­ing spe­cial. In our case, the com­piler would not ne­ces­sar­ily have this in­form­a­tion at its dis­pos­al, so it was ne­ces­sary to ap­ply this trans­form­a­tion manu­ally in many cases.

$\operatorname{gcd}$ and $\operatorname{lcd}$ when one of the op­er­ands is a power of two

$\operatorname{gcd}(a, b)$ where either one of $a$ or $b$ is a power of two will it­self be $2^k$ for some $k$. The num­ber of $2$ mul­tiples in an in­teger can be found by count­ing the num­ber of con­sec­ut­ive un­set bits start­ing from the least sig­ni­fic­ant bit. This use­ful prop­erty comes from the bin­ary rep­res­ent­a­tion of un­signed in­tegers. Fur­ther­more $\operatorname{lcd}(a, b) = \frac{ab}{\operatorname{gcd}\left(a, b\right)}$. To cal­cu­late both $\operatorname{gcd}(a, b)$ and $\operatorname{lcd}(a, b)$:

let k = a.trailing_zeros().min(b.trailing_zeros());
let gcd = 1 << k;
let lcd = (a * b) >> k;

Un­like the na­ive al­gorithms, this can get the job done in just a few cycles. Even some un­com­mon tar­get ma­chine with no nat­ive in­struc­tion for trailing_zeros will man­age to ex­ecute this in 40 cycles or so. Still some­what faster than a single in­teger di­vi­sion op­er­a­tion, which would be ne­ces­sary to im­ple­ment other al­gorithms.

Mod­u­lar mul­ti­plic­at­ive in­verse when the mod­ulo is a power of two

The high­light: a trick to ef­fi­ciently com­pute $a^{-1} \mod 2^k$. Nor­mally, mod­u­lar mul­ti­plic­at­ive in­verse re­quires an it­er­at­ive al­gorithm such as the ex­ten­ded Eu­c­lidean al­gorithm. Such al­gorithms in­volve at least a di­vi­sion and a mod­ulo op­er­a­tion in their in­ner loop and re­quire com­par­at­ively many it­er­a­tions to com­plete. As a spe­cial case, $a^{-1} \mod 2^k$ can be com­puted in $\operatorname{O}(\log_2\log_2k)$ by us­ing a fairly un­known tech­nique de­scribed in this sci.crypt post. To sum­mar­ize the fi­nal al­gorithm:

1. Start at a small mod­ulo such as $2^i = 2^4$ for which it is cheap to either store the table of in­verses or com­pute them;
2. Look up in a table (or com­pute) the in­verse $g = a^{-1} \mod 2^i$;
3. Com­pute $g' = a^{-1} \mod 2^{i^2} = g \left(2 - ag\right) \mod 2^{i^2}$;
4. If $i^2 > k$, $a^{-1} \mod 2^k = g' \mod 2^k$, oth­er­wise re­peat step 3 with $g \leftarrow g'$ and $i \leftarrow i^2$.

Start­ing with $i = 4$, com­pu­ta­tion of $a ^ {-1} \mod 2^256$ needs 2 it­er­a­tions only. Since mag­nitude of align­ments is usu­ally low, for the pur­poses of [T]::align_to at most one it­er­a­tion will usu­ally be ne­ces­sary. Without this al­gorithm [T]::align_to would most likely ended up be­ing en­tirely use­less!