c++ - double - pow()

Question

我想计算 [n^(1/k)] 其中 n是long long和 2 <= k <= lg(n) ; k为整数。

我想也许我可以用这个:

long long d = pow(n,1.0/k)-1;
while(power(d,k) < n)
    d++;
d--;

但它可能会溢出long long在最后一步。

是否保证d pow(n,1.0/k) 如果我写:

long long d = long long(pow(n,1.0/k));

如果不是，计算floor(pow(n,1.0/k)) 的简单安全方法是什么？

Answer 1

不知道 pow 的执行情况在你的 stdlib 中，你不能绝对确定

floor(pow(n,1.0/k)) or (long long)pow(n,1.0/k)

返回正确的结果。 1.0/k引入了一个小的不准确性，加上 pow 的不准确性(由于 double 的表示而不可避免)可能只是移动 pow() 的结果如果 n 超过整数阈值是 k ^th 次方或非常接近 1 次方。

一个使用 Haskell 的 (**) 的例子, 与 pow() 的作用相同来自 math.h ，但它可能有不同的实现:

Prelude> 3^37-1 :: Int
450283905890997362
Prelude> fromIntegral it ** (1.0/37)
3.0000000000000004

然而，它总是至少非常接近正确的结果，因此您可以在必要时将其用作快速更正的起点。

// assumes k > 2
long long r = (long long)pow(n,1.0/k);
while (n/power(r+1,k-k/2) >= power(r+1,k/2)) ++r;
while (n/power(r,k-k/2) < power(r,k/2)) --r;

哪里power(a,b)是整数幂函数(例如可以是 round(pow(a,b))，或者通过重复平方求幂)。通过提高 r回复 r+1只到 k-1 ^th 次幂，避免了溢出(如果 r 为 1 可能除外，如有必要，您可以通过测试 k < 64 && n < (1ull << k) 轻松处理这种特殊情况)。

当然，针对特殊情况的测试和修复会花费时间，而且几乎在所有情况下都不会执行上述 floor(pow(n,1.0/k)) ，所以它可能不值得。