7

将除法的结果四舍五入到最接近的整数非常简单。但我正在尝试对除法的结果进行四舍五入，以便后续操作将给出最佳近似值。最好用一个简单的函数来解释：

const int halfbits = std::numeric_limits<unsigned int>::digits / 2;
unsigned x = foo(); // Likely big.
unsigned x_div = x >> halfbits; // Rounded down
unsigned y = x_div * x_div; // Will fit due to division.

我可以x_div通过添加四舍五入到最近1<<(halfbits-1)。但由于 x² 不是线性函数，因此 y 通常没有正确舍入。有(x*x) >> (halfbits*2)没有不使用更大类型的简单和更准确的计算方法？

我认为添加3<<(halfbits-3)到 x_div 可以提高舍入，但不能证明这是最好的解决方案。此外，这可以推广到 xⁿ 吗？

编辑：根据大众的要求，我冒昧地用纯算术术语“翻译”这个问题（这些 C 位移都没有......）。
注意：此后的所有除法都是整数除法，例如 13/3 将是 4。
问题：我们无法计算 x^2，因为 x 很大，所以我们想计算 (x^2)/(2^ N)。
为此，我们计算
x_div = x / sqrt(2^N)
然后平方：
y = x_div * x_div

但是，此结果通常缺少 的确切值，(x^2)/(2^N)并且 OP 建议添加 0.5 * sqrt(2^N) 或 0.375 * sqrt(2^N) 以更好地近似结果...

正如Oli Charlesworth's answer 所暗示的，有一种更好的方法来获得实际值，将其x^2视为 (x_hi + x_lo)^2。

4

2 回答 2

8

而x_div截断最多会导致误差幅度为 1，而x_div*x_div误差可能高达1<<(half_digits+2).

要了解原因，请考虑我们可以将这个平方表示如下（使用长乘法）：

x * x = (x_lo + x_hi) * (x_lo + x_hi)
      = x_lo^2 + x_hi^2 + 2*x_lo*x_hi

其中x_lo和x_hi分别是 的下半部分和上半部分x。有了一些漂亮的 ASCII 艺术，我们可以考虑这些都是如何排列的：

 MSB     :      :      :     LSB
  +------+------+      :      :
  |    x_hi^2   |      :      :
  +-----++-----++-----+:      :
  :     | 2*x_lo*x_hi |:      :
  :     +------++-----++------+
  :      :      |    x_lo^2   |
  :      :      +------+------+
  :<----------->:      :      :
    Our result

正如我们所见，低阶项会影​​响最终结果中的多个位。

但是，这些术语中的每一个都应该适合原始类型而不会溢出。因此，通过适当的移位和掩蔽，我们可以获得所需的结果。

当然，如果你使用更大的类型，编译器/硬件会为你做这一切，所以如果你有选择的话，你应该这样做。

于 2013-04-02T08:12:19.827 回答
-4

将 TYPE int 用于“y”。我想这会解决这个目的。

于 2013-04-02T08:08:48.973 回答