整数立方根
我正在寻找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;
}
没有找到相关结果
已邀请:
5 个回复
豆兢
函数是否“正确” - 它应该是
的参数,而不是
:)(但是相同的方法可以使用
而不是
,尽管不是所有的C数学库都有立方根函数)。
俯乡骚钵皆
单个牛顿步骤应该足够了,但是你可能有一个(或可能更多?)错误。您可以使用最终检查和增量步骤检查/修复这些,如在您的OQ中:
或者其他一些。 (我承认我很懒;正确的方法是仔细检查以确定哪些(如果有的话)支票和增量实际上是必要的......)
瞧叮
过于昂贵,可以使用count-leading-zero指令来获得结果的近似值,然后使用查找表,然后使用一些牛顿步骤来完成它。
给定
和
,您可以使用查找表(在我的代码中,8K条目)找到
的良好近似值。使用一些牛顿步骤(参见暴风雨的答案)来完成它。
掸牛浓疗
我们可以通过观察按位或相当于加法,重构为
,在迭代之间缓存
和
的值,并使用移位而不是乘法来优化
的计算。
械怒等