c - 如何在 C 中轻松计算 unsigned long long 的平方根？

Question

我正在查看另一个问题 ( here )，其中有人正在寻找一种方法来在 x86 程序集中获取 64 位整数的平方根。

事实证明这很简单。解决办法是转成 float ，计算sqrt再转回来。

我需要在 C 中做一些非常相似的事情，但是当我研究等价物时，我有点卡住了。我只能找到一个接受 double 的 sqrt 函数。 double 无法在不引入重大舍入误差的情况下存储大型 64 位整数。

是否有一个我可以使用的通用数学库，它具有 long double sqrt 函数？

Answer 1

不需要 long double ;平方根可以用double计算(如果它是 IEEE-754 64 位二进制文​​件)。将 64 位整数转换为 double 时的舍入误差与这个问题几乎无关。

舍入误差最多为2⁵³中的一部分。这会导致 2⁵⁴ 中至多一个部分的平方根出现错误。 sqrt由于将数学结果四舍五入到 double，它本身的舍入误差小于 2⁵³ 的一部分。格式。这些错误的总和很小； 64 位整数(四舍五入为 53 位)的最大可能平方根是 2³²，因此 2⁵⁴ 中三部分的误差小于 .00000072。

对于 uint64_t x , 考虑 sqrt(x) .我们知道这个值在 x 的精确平方根的 .00000072 以内。 , 但我们不知道它的方向。如果我们将其调整为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，只是如果 y+1 是 2³²，它会避免包装 64 位整数。)