将除法的结果舍入到最接近的整数是
pretty simple.但是我试图舍入除法的结果,以便后续操作将给出最佳近似值.最好的解释是一个简单的函数：
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)没有使用更大的类型？
我认为向x_div添加3<<<(halfbits-3)可以改善舍入,但无法证明这是最佳解决方案.此外,这可以推广为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的回答所示,通过将x ^ 2视为(x_hi x_lo)^ 2,有更好的方法来获得实际值.
解决方法
而x_div截断将导致误差幅度至多为1,而x_div * x_div的误差可能高达1 <<(half_digits 2). 要了解原因,请考虑我们可以如下表达此平方(使用
long multplication)：
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
我们可以看到,低阶项会影响最终结果中的多个位.
但是,这些术语中的每一个都应该适合原始类型而不会溢出.因此,通过适当的移位和屏蔽,我们可以获得所需的结果.
当然,如果您使用更大的类型,编译器/硬件会为您完成所有操作,因此如果您有选项,则应该这样做.
