如何轻松计算C中无符号长long的平方根？

Question

我正在寻找另一个问题(这里),有人正在寻找一种方法来获得x86汇编中64位整数的平方根.

事实证明这很简单.解决方案是转换为浮点数,计算sqrt然后转换回来.

我需要在C中做一些非常相似的事情,但是当我看到等价物时,我会陷入困境.我只能找到一个接收双打的sqrt函数.双精度不具有存储大64位整数的精度而不会引入明显的舍入误差.

是否有一个我可以使用的具有long doublesqrt功能的通用数学库？

Answer 1

没有必要long double; 平方根可以用double(如果它是IEEE-754 64位二进制)计算.转换64位整数时的舍入误差double在此问题中几乎无关紧要.

舍入误差最多为2 ^53中的一部分.这会导致2 ⁵⁴中最多一个部分的平方根出错.的sqrt本身在2小于一个部分的舍入误差⁵³,由于四舍五入的数学结果提供给double格式.这些错误的总和很小; 64位整数的最大可能平方根(舍入为53位)为2 ³²,因此2 ^54中的三个部分的误差小于.00000072.

对于a uint64_t x,考虑一下sqrt(x).我们知道这个值在.00000072的精确平方根内x,但我们不知道它的方向.如果我们调整它sqrt(x) - 0x1p-20,那么我们知道我们有一个小于但非常接近平方根的值x.

然后x,如果操作符合IEEE 754,则此代码计算截断为整数的平方根:

uint64_t y = sqrt(x) - 0x1p-20;
if (2*y < x - y*y)
    ++y;

(2*y < x - y*y相当于(y+1)*(y+1) <= x除了避免包装64位整数,如果y+1是2 ^32.)

Answer 2

函数sqrtl()，取一个long double，是 C99 的一部分。

请注意，您的编译平台不必实现long double为 80 位扩展精度。它只需要和 一样宽double，并且 Visual Studio 实现的是一个普通的double. GCC 和 Clanglong double在 Intel 处理器上编译为 80 位扩展精度。