由于我们对一些内容进行了四舍五入，您可能会认为我们太懒了，更仔细的分析会得出更严格的上限。但事实上，我们的上限是精确的：N位除法的幻数可能真的需要像N+1位一样大。好消息是，对于特定的除数，可能会有更小的数字适合N位。稍后会详细介绍这一点！在任何情况下，我们现在都有了幻数m。要执行除法，我们需要尽可能高效地计算$\lFloor\frac{mn}{2^k}\rFloor$。M是一个33位的数字，那么32位处理器如何有效地乘以它呢？一种方法是使用bignum库，但那太慢了。更好的方法是乘以低32位，并特殊处理第33位，如下所示：$$\BEGIN{ALIGN}m n&；=(m-2^{32}+2^{32})n\\&；=(m-2^{32})n+2^{32}n\end{Align}$$这看起来非常有希望：m-232绝对是一个32位数字。此外，我们可以很容易地计算出那个232n项：我们甚至不需要移位，只需将n加到乘积的高位字即可。不幸的是，它是不正确的：32位数字乘以33位数字等于65位，因此加法溢出。但我们可以通过以下技巧在分母中分配一个2来防止溢出：$$\Begin{Align}\lFloor\frac{n+q}{2^k}\rFloor&；=\lFloor\frac{n-q+2q}{2^k}\rFloor\\&；=\lFloor(\frac{n-q+2q}2)/{2^{k-1}}\rFloor\\&；=\lFloor(\lFloor\frac{n-q}2\rFloor+q)/{2^{k-1}}\rFloor\end{Align}$$这里q是幻数(减去第33位)乘以n，而n正好是分子n。(所有内容都应该乘以232，但这在某种程度上是隐含的，因为我们是在包含高乘积的寄存器中工作，所以我们可以忽略它。)。减法n-q可以下溢吗？不是，因为q正好是32位幻数的n倍，然后除以232。幻数(现在没有第33位)小于232，所以我们有q<；n，所以n-q不能下溢。那个+Q怎么样？那会溢出吗？不，因为我们只需抛出地板就可以得到$\frac{n+q}2$的上限，这是一个32位的数字。所以我们有一个实用的算法。给定被除数n和固定除数d，其中0<；d<；2 32和0≤n<；2 32：预计算$p=\lceil log_2d\rceil$预计算$m=\lceil\frac{2^{32+p}}d\rceil$。这将是一个33位的数字，因此只保留低32位。
计算$q=(m\x n)\gg 32$。大多数处理器使用一条高乘法指令就可以做到这一点。
COMPUTE$t=((n-q)\gg2)+q$，这是一种溢出安全的计算(n+q)≫1的方法。此额外加法将更正删除m的第33位。
就是这样！我们知道如何有效地用乘法代替除法。我们可以看到所有这些步骤都在起作用。以下是Clang为除以7生成的程序集，以及我的注释：_DIVIDE_BY_7：MOVL$613566757，%ecx 613566757是(2**35)/7的低32位，向上舍入movl%edi，%eax mull%ecx将被除数乘以幻数subl%edx，%edi除以%edx中的被除数减去乘积的高32位(%eax具有低)，srl%edi初始移位为1以防止溢出。%eax将结果移入返回寄存器SHRL$2，%eax最后的楼层右移(log_2(7))ret。
对于一般情况，这个算法是我们所能做的最好的，但是对于某些因子，我们也许能够改进这个算法。关键是e项：我们为得到d的下一个倍数而添加的值。我们推断e小于d，因此我们使用$\frac e d<；1$作为e的上限。但是，d的倍数可能仅略大于2的幂。在这种情况下，e将是小的，如果我们幸运的话，它将小到足以将整个错误项推到$\frac 1 d$以下。例如，让我们尝试除数11。使用常规算法，我们需要$k=32+\lceil log_2 11\rceil=36$。但是如果我们选择k=35呢？235+1是11的倍数，所以我们有e=1，我们计算：$\frac e d\Times\frac n{2^k}=\frac 1d\Times\frac n{2^{35}}<；\frac 1d$所以k=35强制误差项小于$\frac 1d$，因此k=35是一个足够好的近似值。这是个好消息，因为然后$m=\lceil\frac{2^{35}}{11}\rceil=3123612579<；2^{32}$，所以我们的幻数适合32位，我们不需要担心溢出！我们可以避免一般算法中的减法、加法和额外移位。实际上，clang输出：_divide_by_11：movl$-1171354717，%ecx movl%edi，%eax mull%ecx movl%edX，%eax shl$3，%eax ret。
除以11的代码比除以7的代码要短，因为11的倍数恰好非常接近2的幂。这说明了改进算法的方法：我们可以简单地尝试2的连续幂，