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