在 c 中使用 pow() 找到第 n 个根的正确方法

Question

我必须找到可以大到 10^18 的数字的第 n 个根，其中 n 大到 10^4。

我知道使用 pow() 我们可以找到第 n 个根，

 x = (long int)(1e-7 + pow(number, 1.0 / n))

但这对在线编程评委给出了错误的答案，但在我所接受的所有案例中，它给出了正确的结果。对于给定的约束，此方法是否有问题

注意：这里的n次根是指n次方小于或等于给定数的最大整数，即x^n <= number的最大’x’。

按照答案，我知道这种方法是错误的，那么我应该怎么做呢？

原文由 Ankur Mishra 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

你可以使用

x = (long int)pow(number, 1.0 / n)

鉴于 n 的高值，大多数答案将是 1。

更新：

在 OP 评论之后，这种方法确实存在缺陷，因为在大多数情况下 1/n 没有精确的浮点表示，并且 1/n 次幂的下限可以减一。

并且四舍五入并不是更好的解决方案，它可以使根过长。

另一个问题是高达 10^18 的值不能使用双精度精确表示，而 64 位整数可以。

我的建议：

1）在（隐式）强制转换之前将数字的 11 个低位截断为双精度，以避免被 FP 单元四舍五入（不确定这是否有用）。

1. 使用 pow 函数来获得第 n 个根的下级估计，让 r 。

2. 仅使用整数运算（通过重复平方）计算 r+1 的 n 次方。

4）解决方案是 r+1 而不是 r 以防第n次幂适合。

FP 单位在计算 1/n 时仍有可能四舍五入，导致结果略大。我怀疑这个“太大”在最终结果中会变成一个单位，但这应该检查一下。

原文由 Yves Daoust 发布，翻译遵循 CC BY-SA 3.0 许可协议