我正在尝试编写一个在运行时执行以下计算的 C 函数：
分子/分母
在哪里：
分子为先验计算结果，始终为正，且大于分母
和，
分母是这样的（1 <= 分母 <= 64）。
运行时计算必须很快，即最少的周期，所以除法运算符是不可能的。我看过递归减法和按位长除法，但我正在尝试寻找另一种解决方案。
有什么帮助吗？
问问题
182 次
2 回答
1
这是一个想法，它使用一次乘法和一次移位，因此在大多数系统上它会比除法更快。由于您的分子最高为 768,000,000 ~= 30 位，我们在 32 位字中没有多少空间，所以我们必须使用 64 位乘法。
主要思想是利用以下事实：
x / y == (x * k) / (y * k)
除以 2 的幂是一个简单、快速的位移。
所以要选择一个特定的例子，假设x = 700,000,000和y = 47（所以正确的商是 14,893,617）。为了避免舍入错误，我们的移位需要大约是我们最大可能分子的大小 - 30 位。找到k最接近的值y * k = 2^30，k = 22845571在这种情况下。然后x * k = 0x38D08C4CE6F500。将其移动 30 位得到0xE34231 = 14,893,617，我们的预期商。出于舍入目的，您可能需要为分子/分母的某些组合再添加 1-2 位，除非在您的商中减去 1 是可以接受的。
然后，练习变成了为每个可能的分母创建一个带有正确乘数的查找表。
编辑：正如在下面的评论中指出的那样，选择k = (2^30 + y - 1) / y应该比简单地给出更好和更一致的结果k = round(2^30 / y)。
于 2013-06-12T15:52:29.510 回答
0
大 @ss 表适用于小数字：
unsigned int divTable[kMaxNumerator][64] = {...}
你把每个可能的分界线的值放在那里。在特定尺寸之上不是很实用，但它确实适用于包含的情况，并且是当时纹理映射方式的常见解决方案:) 然后我阅读了您的评论，发现您在 768,000,000 范围内，这是因为完全不切实际，除非你可以处理相当多的精度损失。
于 2013-06-12T16:00:40.280 回答