algorithm - 整数次根

Question

x' 是 y 的第 n 个根，如果 x' 是满足 x^n <= y 的最大整数。 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...换句话说，您的表的大小将与您的系统理解的整数位数大致相同。