algorithm - 整数 n 次根

Question

如果 x' 是满足 x^n <= y 的最大整数，则 x' 是 y 的第 n 个根。x、x' 和 y 都是整数。有没有有效的方法来计算这样的第 n 个根？我知道这通常是由nth root algorithm完成的，但这里的困难是一切都是整数，因为我正在使用嵌入式系统。

顺便说一句，我什至尝试从 1 到 y 进行二进制搜索来识别最大的 x，使得 x^n <= y，但它不起作用，因为 x^n 很容易溢出，尤其是当 n 很大时。

Answer 1

为最大 x 的给定 y 存储一个表，以使 x^y 不会溢出。使用这些值进行二分搜索；这样，只要 x 和 n 具有相同的（整数）类型，就不会再出现溢出和简洁的算法。正确的？

注意：对于 y > 32，对于 32 位整数，x 的最大值为 2...换句话说，您的表格将与您的系统理解的整数位数大致相同。

Answer 2

您是否仅在寻找整数根？或者你想知道 34 的 5 次方根是 2.024...？或者“2”是一个足够的答案？如果您想要小数位，则必须进行某种浮点或定点数学运算。

您应该阅读Computing principal roots，并注意它对第一个牛顿近似的说法。如果大约 0.03% 的误差足够接近，我建议你这样做。您可能想要构建一个可用于进行初始近似的表。这张桌子并不像听起来那么大。2^32 的立方根只有大约 1,626。您可以轻松计算平方，如果您可以生成 x^2 和 x^3，则很容易生成 x^n。所以做近似是很容易的。

另一种可能性是自己建立一个根表并使用某种插值。同样，如果您将平方根视为特殊情况，则该表不必非常大。2^32 的第 5 个根小于 100，所以你说的是一个很小的表来获得很大范围的根。

Answer 3

我认为最好的方法是使用 Wikipedia 文章中的 Newton-Raphson 方法。

可以从输入的位长度除以 来计算一个好的起始值n。在每次迭代中，您都使用向下舍入的整数除法。迭代，直到找到x这样的值x^n <= y < (x+1)^n。

你必须小心避免溢出。正如另一个答案所说，您可以使用最大根表n < bit size来做到这一点（对于更大n的答案总是1，除了y = 0）。