c - 整数立方根

Question

我正在寻找 64 位(无符号)立方根的快速代码。 (我正在使用 C 并使用 gcc 进行编译，但我想所需的大部分工作将与语言和编译器无关。)我将用 ulong 表示一个 64 位未签名的整数。

给定输入 n 我要求(整数)返回值 r 是这样的

r * r * r <= n && n < (r + 1) * (r + 1) * (r + 1)

也就是说，我想要 n 的立方根，向下舍入。基本代码如

return (ulong)pow(n, 1.0/3);

不正确，因为向范围末尾四舍五入。简单的代码，如

ulong
cuberoot(ulong n)
{
    ulong ret = pow(n + 0.5, 1.0/3);
    if (n < 100000000000001ULL)
        return ret;
    if (n >= 18446724184312856125ULL)
        return 2642245ULL;
    if (ret * ret * ret > n) {
        ret--;
        while (ret * ret * ret > n)
            ret--;
        return ret;
    }
    while ((ret + 1) * (ret + 1) * (ret + 1) <= n)
        ret++;
    return ret;
}

给出了正确的结果，但比需要的要慢。

此代码用于数学库，将被各种函数多次调用。速度很重要，但您不能指望热缓存(因此像 2,642,245 条目二进制搜索这样的建议是正确的)。

为了比较，这里是正确计算整数平方根的代码。

ulong squareroot(ulong a) {
    ulong x = (ulong)sqrt((double)a);
    if (x > 0xFFFFFFFF || x*x > a)
        x--;
    return x;
}

Answer 1

《Hacker's Delight》一书中有解决这个问题和许多其他问题的算法。代码在线here . 编辑:该代码无法与 64 位整数一起正常工作，书中关于如何修复它以用于 64 位的说明有些令人困惑。正确的 64 位实现(包括测试用例)在线 here .

我怀疑您的 squareroot 函数是否“正确”工作 - 它的参数应该是 ulong a，而不是 n :)(但是使用 cbrt 而不是 sqrt 也可以使用相同的方法，尽管并非所有 C 数学库都具有立方根函数)。