整数的n次方根

Question

如果x'是最大的整数，使得x^n <= y，则x'是y的第n个根。其中x、x'和y都是整数。是否有一种高效的方法来计算这样的n次根？我知道通常使用nth root algorithm来完成此操作，但问题在于我正在使用嵌入式系统，其中所有内容都是整数。顺便说一句，我甚至尝试了从1到y的二进制搜索，以识别最大的x，使得x^n <= y，但是它不起作用，因为当n很大时，x^n很容易溢出。

- sinoTrinity

---

如果 x^n 溢出了，你会如何存储 y？ - Thomas

我不确定我完全理解这个问题，给定n和y，您要找到x和x'，使得x^n <= y <= x'^n？（其中x和x'分别是最大和最小的整数） - Ricky Bobby

@Thomas 我正在处理最大为4个字节的无符号整数。比如说y等于2 ^ 10，n等于4。我的天真算法尝试所有从1到2 ^ 10的数字。当x等于2 ^ 8时，糟糕了，(2 ^ 8) ^ 4 = 2 ^ 32，发生了溢出！ - sinoTrinity

@Ricky Bobby 我正在寻找最大的整数 x，使得 x^n <= y。 - sinoTrinity

Answer 1

存储给定 y 的最大 x 表，使得 x^y 不会溢出。使用这些值进行二分查找；这样，不会再有溢出问题，并且可以得到一个漂亮的算法，只要 x 和 n 具有相同的（整数）类型即可工作。对吗？

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

- Patrick87

---

优秀的解决方案。内存占用稀少，效率极高。 - Thomas Ahle

@Patrick87，你的解决方案可能不可行，因为对于给定的n，要找到最大的x使得x^n不会溢出，就像你所建议的那样，等价于让y为(2^32 - 1)，并解决我提出的原始问题。（我正在使用4字节无符号整数） - sinoTrinity

@sinoTrinity：不确定你在说什么。对于4字节（例如无符号）整数，表格看起来像这样2->2^16 3->2^11, 4->~2^8, ..., 32->2^1, >33->1... 然后进行二分查找，直到达到上限。只要n是有效的32位无符号整数，选择小于给定x的上限将确保x^y不会溢出。也许我误解了你的问题。 - Patrick87

另外，您需要预先计算此表。如果一开始没有说明清楚，我很抱歉。也就是说，在程序中将它们设置为常量。 - Patrick87

另外，看起来我正在调用你称之为N的Y，反之亦然...如果这让你感到困惑，对不起。 - Patrick87

Answer 2

你是只寻找整数根吗？或者你想知道34的五次方根是2.024...吗？还是“2”作为答案就足够了？如果你需要小数位数，你需要进行浮点数或定点数运算。

你应该阅读计算主根，并注意它关于第一牛顿近似的内容。如果误差在0.03%左右可以接受，我建议你采用这种方法。你可能需要建立一个表格来进行初始逼近。这个表格并没有听起来那么大。2^32的立方根只有约1626。你可以轻松地计算平方，如果你能计算出x^2和x^3，生成x^n也很容易。因此，进行逼近相当容易。

另一种可能性是建立一个根的表格，并使用某种插值方法。同样，如果将平方根视为特殊情况，那么这个表格不必很大。2^32的五次方根小于100，因此你可以得到一个相当小的表格来获得相当大的根范围。

- Jim Mischel

Answer 3

我认为最好的方法是使用维基百科文章中的牛顿-拉弗森方法。

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

您必须小心避免溢出。正如其他答案所说，您可以使用n < bit size的最大根表来解决这个问题（对于更大的n，答案总是1，除非y = 0）。

- starblue