Converting division by a constant into multiplication

Question

Given a small integer constant $N$, how can I find a fast to compute expression for $\lfloor \frac xN \rfloor$, working for each integer $x \in [-2^{31}, +2^{31})$? Here, "fast to compute" means that

• only integer operations are allowed
• all intermediate results must fit in $[-2^{63}, +2^{63})$
• no division except by a power of two and rounding towards $-\infty$ is allowed
• multiplications are fine, but only one or two
• no branching is allowed

Smart compilers partly do the job, but humans may sometimes do better. Wikipedia has a short paragraph on this topic, but the details omitted can get a bit complicated.

The fastest way to compute $\lfloor \frac x{100} \rfloor$ I've found, is to compute

$$\left\lfloor \frac {p \cdot \lfloor \frac x4 \rfloor + d}{q} \right\rfloor $$

with $q= 2^{36}$, $p = \frac{q}{25} + 1$ and $d = 2^{29}$. Despite the ugly-looking expression it's pretty fast (something like 7 cycles instead of 40 for the division). What bothers me is how to find such an expression in general.

^{This expression was found by some thinking and guessing and the correctness was proved by running through all four billion possible values of $x$. This is not exactly the mathematician's way, so I'm looking for something more profound (ideally some expression for $p$, $q$, and $d$ rather than an algorithm; that's why I'm asking here rather than on SO).}

Answer 1

Warning: Non-elegant proof based on quite a few crude estimates and inequalities; the chance of mistake is non-negligible.

Let $N<2^{31}$ denote the divisor we're interested in. We can assume that $N$ is not a power of $2$, otherwise the problem is trivial.

Let $m=\lfloor\log_2 N\rfloor$ (so that $2^m < N < 2^{m+1}$) and compute the following quantities: $$\begin{eqnarray} a & = & \mathrm{round}\left(\frac{2^{32+m}}{N}\right) \hskip 1cm& (\Rightarrow 2^{31}<a<2^{32})\\ \Delta & = & aN - 2^{32+m} & (\Rightarrow 1\leq |\Delta|<\frac{N}{2})\\ B & = & \left\lfloor\frac{2^{31}}{N}\right\rfloor \\ d & = & B|\Delta| \end{eqnarray}$$

Now, let's prove that for $-2^{31}\leq x < 2^{31}$, we have $$\left\lfloor \frac{x}{N}\right\rfloor = \left\lfloor \frac{ax+d}{2^{32+m}}\right\rfloor$$

First, let's write $x=uN+v$, with $0\leq v\leq (N-1)$, so that the left-hand side of the equality becomes equal to $u$. On the right-hand side, we have $$\frac{ax+d}{2^{32+m}} = \frac{aNu + av+d}{2^{32+m}} = u + \frac{u\Delta+B|\Delta| + av}{2^{32+m}}$$

It's sufficient to prove that numerator of the last fraction is non-negative and strictly smaller than its denominator. The range of allowed values of $x$ implies $-(B+1) \leq u \leq B$ which immediately establishes non-negativity in almost all cases. The only non-trivial one is $u=-(B+1)$ with $\Delta > 0$. The non-negativity condition then reduces to $\Delta \leq av$ and it's not difficult to see that in this case we have $v\not =0$. The inequality $\Delta \leq N < 2^{31} \leq a\leq av$ then finishes the proof.

When it comes to upper bound, we can rewrite the $av$ term slightly to obtain $$u\Delta + B|\Delta| + av = (u+1)\Delta + B|\Delta| + 2^{32+m} - a(N-v)$$ so being smaller than $2^{32+m}$ can be expressed as $$(u+1)\Delta + B|\Delta|<a(N-v)$$

Let's analyse a few cases:

• If $|u+1|\leq B$, we have $(u+1)\Delta + B|\Delta| \leq 2B|\Delta| \leq 2^{31} < a \leq a(N-v)$. Otherwise, we can assume $u=B$.
• If $\Delta<0$, we're done, since the left-hand side is negative. Otherwise, $\Delta > 0$ and the inequality reduces to $(2B+1)\Delta < a(N-v)$.
• We have $2B\Delta + \Delta < 2^{31} + 2^{30} < 2^{32} \leq 2^{31}(N-v) < a(N-v)$ as long as $N-v>1$.

The only remaining case is thus $u=B$, $v=(N-1)$. This is the largest possible value of $x$, so we must have $BN+(N-1)=2^{31}-1$ or, equivalently, $(B+1)N = 2^{31}$. But that is impossible without $N$ being a power of $2$, thus completing the proof.

It's also not too difficult to see that $$ax+d \geq a(-2^{31}) + d > 2^{32}(-2^{31}) = -2^{63}$$ On the other end, $$ax+d\leq a(2^{31}-1)+d\leq 2^{32}(2^{31} - 1) + 2^{30} < 2^{63}$$ Thus, the intermediate results fit into the allotted range.

---

As an example, for $N=100$, we get $m=6$, $a=2748779069$, $\Delta=(-44)$, $B=21474836$ and $d=944892784$, so (for the 32-bit signed integers), we have $$\left\lfloor \frac{x}{100}\right\rfloor=(2748779069x + 944892784) >\!> 38$$ where $>\!>$ denotes arithmetic shift to the right.