# Converting division by a constant into multiplication

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).

• You may have a look at a newer paper by Torbjörn Granlund: gmplib.org/~tege/division-paper.pdf Feb 6, 2014 at 8:33
• I presume you meant $-2^{31}$ and $-2^{63}$ rather than $2^{-31}$ and $2^{-63}$? What is the expected behaviour of $\lfloor\rfloor$ for negative numbers? Do they round towards zero, or towards $-\infty$? In particular, is $\lfloor\frac{-1}{100}\rfloor$ expected to be equal to $0$ or to $(-1)$? Feb 8, 2014 at 0:06
• @PeterKošinár: Thanks, fixed. Always rounding towards negative infinity, this is what's mostly needed, but what programming languages and HW rarely support. $\lfloor\frac{-1}{100}\rfloor = -1$. A typical example when you need floorDiv is the linked SO question, similarly you need floorMod for accessing tables. Feb 8, 2014 at 0:29
• Would this question fit better on a computing website than here on this mathematics website? Feb 8, 2014 at 0:51
• @GerryMyerson: Initially I thought no as I was expecting some simple formula and a proof, but it doesn't look like this. The problem is probably pretty complicated and has no "mathematical" answer. I'd suggest to wait a bit longer and if it doesn't get any answer, I'll ask you to move it (it's no practical problem of mine, just curious). Feb 8, 2014 at 0:57

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.

• That's pretty cool. I'm not through the proof yet, but I've tested it on a few billion cases and it works. Feb 20, 2014 at 8:22