algorithm - 整数除以 7

Question

我的答案来源:

Is this expression correct in C preprocessor

我在这里有点力不从心，我正在尝试了解这种特殊优化的工作原理。

如答案中所述，gcc 将整数除以 7 优化为:

mov edx, -1840700269
mov eax, edi
imul    edx
lea eax, [rdx+rdi]
sar eax, 2
sar edi, 31
sub eax, edi

转换回 C 为:

int32_t divideBySeven(int32_t num) {
    int32_t temp = ((int64_t)num * -015555555555) >> 32;
    temp = (temp + num) >> 2;
    return (temp - (num >> 31));
}

我们先来看第一部分:

int32_t temp = ((int64_t)num * -015555555555) >> 32;

为什么是这个数字？

好吧，让我们用 2^64 除以 7，看看会弹出什么。

2^64 / 7 = 2635249153387078802.28571428571428571429

这看起来很乱，如果我们将它转​​换成八进制呢？

0222222222222222222222.22222222222222222222222

这是一个非常漂亮的重复模式，这肯定不是巧合。我的意思是我们记得 7 是 0b111 并且我们知道，当我们除以 99 时，我们往往会在基数 10 中得到重复模式。因此，当我们在基数 8 中得到重复模式时，这是有道理的我们除以 7。

那么我们的号码从何而来？

(int32_t)-1840700269 等同于(uint_32t)2454267027

* 7 = 17179869189

最后 17179869184 是 2^34

这意味着 17179869189 是 7 2^34 的最接近倍数。或者换句话说，2454267027 是适合 uint32_t 的最大数字，乘以 7 非常接近 2 的幂

这个八进制数是多少？

0222222222223

为什么这很重要？好吧，我们想除以 7。这个数字大约是 2^34/7...。所以如果我们乘以它，然后左移 34 次，我们应该得到一个非常接近精确数字的数字。

最后两行看起来像是为了修补近似误差而设计的。

也许在此领域拥有更多知识和/或专业知识的人可以插话。

>>> magic = 2454267027
>>> def div7(a):
...   if (int(magic * a >> 34) != a // 7):
...     return 0
...   return 1
... 
>>> for a in xrange(2**31, 2**32):
...   if (not div7(a)):
...     print "%s fails" % a
... 

失败从 3435973841 开始，有趣的是 0b11001100110011001100110011010001

对近似失败的原因进行分类有点超出我的理解范围，而补丁修复它的原因也是如此。有谁知道魔法是如何运作的？

Answer 1

算法的第一部分是乘以 7 的倒数的近似值。在本例中，我们通过整数乘法和右位移来近似计算倒数。

首先，我们将值 -1840700269(八进制 -015555555555)视为 32 位整数。如果将其作为无符号 32 位整数读取，则其值为 2454267027(八进制 22222222223)。事实证明，2454267027/2^34 是一个非常接近 1/7 的整数近似值。

为什么我们选择这个数字和 2 的特定次方？我们使用的整数越大，近似值就越接近。在这种情况下，2454267027 似乎是最大的整数(满足上述属性)，您可以将其与带符号的 32 位 int 相乘而不会溢出 64 位 int。

接下来，如果我们用 >> 34 立即右移并将结果存储在 32 位 int 中，我们将失去两个最低位的精度。这些位对于确定整数除法的正确底数是必需的。

我不确定第二行是否从 x86 代码翻译正确。那时，temp 大约是 num * 4/7，所以 num * 4/7 + num 到那个位置，位移就开始了给你大约 num * 1/7 + num * 1/4，这是一个相当大的错误。

例如，输入 57，其中 57//7 = 8。我也在代码中验证了以下内容:

• 57 * 2454267027 = 139893220539
• 139893220539 >> 32 = 32(此时大约 57 * 4/7 = 32.5714...)
• 32 + 57 = 89
• 89 >> 2 = 22(哈？？此时离 8 还很远。)

不管怎么说，最后一行，是我们这样计算有符号整数除法后做的调整。我引用 Hacker's delight on signed division 的部分:

The code most naturally computes the floor division result, so we need a correction to make it compute the conventional truncated toward 0 result. This can be done with three computational instructions by adding to the dividend if the dividend is negative.

在这种情况下(引用你的另一篇文章)你似乎在做一个有符号的转变，所以它会在负数的情况下减去 -1;给出 +1 的结果。

这甚至不是您能做的全部；这是一个更疯狂的blog post about how to divide by 7 with just a single multiplication .