将y=x*x四舍五入到最近的数值。

Question

将y=x*x四舍五入到最近的数值。

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.

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

我认为将3<<(halfbits-3)添加到x_div会改善舍入，但无法证明这是最佳解决方案。此外，这可以推广到xⁿ吗？

编辑：应广大要求，我在纯算术术语中“翻译”了问题（没有C位移操作...）。注意：此后所有除法都是整数除法，例如13/3将是4。问题：我们无法计算x²，因为x很大，所以我们想计算(x²)/(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 的回答所建议的那样，有一种更好的方法可以得到实际值，即将 x^2 视为 (x_hi + x_lo)^2。

- MSalters

7

我对位运算不陌生，但你能否用更数学化、少些C语言特有的方式重新表述这些运算？我并不是要钻牛角尖，只是认为这样能够帮助澄清问题并表达你的目标。 - Jake H

有几个尝试的方法：x_div_down*x_div_up，x_div_near*x_div_near。如果你愿意花时间，你可以计算(x_div*x_rest)>>(halfbit-1)并根据结果进行修正。 - Marc Glisse

所以，为了明确起见，您的 (x*x) >> (halfbits*2) 暗示了您实际上想要那个 非舍入 的位精确结果吗？或者您想要正确舍入的数学结果？ - hyde

等等，(x*x) >> (halfbits*2) 不就是 (x*x) >> bits 吗？你的意思是要计算 x^2 / 2^ceil(log2(x)) 吗？ - user541686

@Mehrdad: 实际上是x*x/UINT_MAX。 - MSalters

2个回答

-4

使用 int 类型来表示 "y"。我猜这样就能解决问题了。

- code

注意：在Stack Overflow上删除错误答案是没有问题的，而且快速获得4个踩也通常意味着你的答案是错误的，即使没有任何一个踩的人留下解释。 - hyde

@hyde：嗯，一个解释是这绝对不会“达到目的” ;) - Oliver Charlesworth

@OliCharlesworth，是的，我绝对不是说踩票是错的。我只是倾向于在踩票时留下评论，即使只是“你的答案完全...错误”。 - hyde

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Oliver Charlesworth · Accepted Answer

对于 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

从结果中可以看到，较低级别的项目影响了最终结果的多个位。

然而，这些项中的每一项都应在不溢出的情况下适合原始类型。因此，通过适当的移位和屏蔽，我们可以得到所需的结果。

当然，如果您有选择的话，编译器/硬件会为您完成所有操作，只需使用更大的类型即可。