整数立方根 [英] Integer cube root

问题描述

我在寻找快速code为64位（无符号）立方根。 （我使用C和用gcc编译，但我想大多数人会是语言和编译器无关的。工作需要的），我将通过ULONG 64位unisgned整数表示。

给定输入n个I所需要的（积分）返回值r为使得

  R * R *为r = N＆放大器;＆安培; N'LT; （R + 1）*（R + 1）*（R + 1）
 

这就是我想要n的立方根，四舍五入。基本code像

 收益率（ULONG）POW（N，1.0 / 3）;
 

不正确，因为朝向范围的结束四舍五入。性格单纯code像

  ULONG
cuberoot（ULONG N）
{
    ULONG RET = POW（N + 0.5，1.0 / 3）;
    如果（N＆LT; 100000000000001ULL）
        返回RET;
    如果（N＆GT; = 18446724184312856125ULL）
        返回2642245ULL;
    如果（RET * RET * RET＆GT; N）{
        ret--;
        而（RET * RET * RET＆GT; N）
            ret--;
        返回RET;
    }
    而（（保留+ 1）*（保留+ 1）*（保留+ 1） - ; = n）的
        RET ++;
    返回RET;
}
 

给出正确的结果，但是慢于它需要

这code是一个数学库，它会从各种功能调用多次。速度是重要的，但你不能在一个温暖的高速缓存数（所以像2642245入境二进制搜索建议是正确的了）。

为了便于比较，这里是code，它的正确的计算整数的平方根。

  ULONG平方根（ULONG一）{
    ULONG X =（ULONG）的sqrt（（双）一）;
    如果（X GT; 0xFFFFFFFF的|| X * X＆gt;一种）
        X - ;
    返回X;
}
 

解决方案

这本书黑客的喜悦对这一算法和许多其他问题。在code是在线 rel=\"nofollow\">。的修改的：那code不能与64位整数的正常工作，并在书中对如何解决它的64位指令是有些混乱。一个适当的64位实现（包括测试用例）在线 rel=\"nofollow\">。

我怀疑你的平方根函数是正确的 - 它应该是 ULONG一个的说法，不 N :)（但同样的方法将工作中使用 CBRT 而不是开方，虽然不是所有的C数学库有立方根函数）。

I'm looking for fast code for 64-bit (unsigned) cube roots. (I'm using C and compiling with gcc, but I imagine most of the work required will be language- and compiler-agnostic.) I will denote by ulong a 64-bit unisgned integer.

Given an input n I require the (integral) return value r to be such that

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

That is, I want the cube root of n, rounded down. Basic code like

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

is incorrect because of rounding toward the end of the range. Unsophisticated code like

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;
}

gives the correct result, but is slower than it needs to be.

This code is for a math library and it will be called many times from various functions. Speed is important, but you can't count on a warm cache (so suggestions like a 2,642,245-entry binary search are right out).

For comparison, here is code that correctly calculates the integer square root.

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

解决方案

The book "Hacker's Delight" has algorithms for this and many other problems. The code is online here. EDIT: That code doesn't work properly with 64-bit ints, and the instructions in the book on how to fix it for 64-bit are somewhat confusing. A proper 64-bit implementation (including test case) is online here.

I doubt that your squareroot function works "correctly" - it should be ulong a for the argument, not n :) (but the same approach would work using cbrt instead of sqrt, although not all C math libraries have cube root functions).

这篇关于整数立方根的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！