仅使用整数算术即可找到整数平方根的方法有两种。例如这个。它为有趣的阅读和非常有趣的理论提供了帮助，特别是对于我们这一代不再有用的技术。
最主要的是它不能使用浮点算法，因此排除了牛顿法及其派生方法。我知道的唯一找到根的方法是二项式展开，但这也需要浮点运算。
有什么技术/算法可以仅使用整数算术来计算整数第n个根？
编辑：感谢到目前为止的所有答案。它们似乎都是更加明智的尝试和改进。有没有更好的办法？
Edit2：好的，因此，似乎没有试行/改进和牛顿方法或二进制搜索的方法都没有明智的方法。谁能提供 理论上 两者的比较？我在两者之间运行了许多基准，发现它们非常相似。
您可以使用仅使用整数算术的牛顿方法，该步骤与浮点算术相同，不同之处在于，您必须用相应的整数运算符替换浮点运算符，而相应的整数运算符的语言具有不同的运算符。
比方说，你要查找的整数k个根a > 0，这应该是最大的整数r这样r^k <= a。您可以从任何正整数开始（当然，一个好的起点会有所帮助）。
a > 0
r
r^k <= a
int_type step(int_type k, int_type a, int_type x) { return ((k-1)*x + a/x^(k-1))/k; } int_type root(int_type k, int_type a) { int_type x = 1, y = step(k,a,x); do { x = y; y = step(k,a,x); }while(y < x); return x; }
除了第一步之外，您还有x == r <==> step(k,a,x) >= x。
x == r <==> step(k,a,x) >= x
