x' 是 y 的第 n 个根,如果 x' 是满足 x^n <= y 的最大整数。 x、x'和y都是整数。有什么有效的方法来计算这样的 n 次根吗?我知道这通常由 nth root algorithm 完成,但这里的困难在于一切都是整数,因为我正在使用嵌入式系统。
顺便说一句,我什至尝试过从 1 到 y 的二进制搜索来确定最大的 x,使得 x^n <= y,但它不起作用,因为 x^n 很容易溢出,尤其是当 n 很大时。
最佳答案
为给定的最大 x 的 y 存储一个表,使得 x^y 不会溢出。使用这些值进行二进制搜索;这样,就不会再有溢出,只要 x 和 n 具有相同的(整数)类型,就会有一个简洁的算法。对吧?
注意:对于 y > 32,对于 32 位整数,x 的最大值为 2...换句话说,您的表的大小将与您的系统理解的整数位数大致相同。
关于algorithm - 整数次根,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7407752/