用整数运算计算第N个根

Question

有两种方法可以仅使用整数运算来查找整数平方根.例如这一个.它有趣的阅读和一个非常有趣的理论,特别是对于我这一代,这些技术不再那么有用.

主要的是它不能使用浮点运算,因此排除了牛顿方法及其推导.我知道找到根的另一种方法是二项式扩展,但这也需要浮点运算.

有什么技术/算法可以仅使用整数运算来计算整数n个根？

编辑:感谢目前为止的所有答案.他们似乎都更加智能的试验和改进.有没有更好的方法？

编辑2:好的,所以没有试用/改进和牛顿方法或二进制搜索似乎没有聪明的方法来做到这一点.任何人都可以在理论上提供两者的比较吗？我在两者之间运行了一些基准测试,发现它们非常相似.

Answer 1

您可以仅使用整数运算来使用牛顿方法,该步骤与浮点运算相同,除了您必须使用具有不同运算符的语言中的相应整数运算符替换浮点运算符.

比方说,你想找到的整数-K次方根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.

Answer 2

一种显而易见的方法是通过平方使用二进制搜索和取幂.这将让你找到nthRoot(x, n)的O(log (x + n)):在二进制搜索[0, x]的最大整数k这样k^n <= x.对于某些人来说k,如果k^n <= x,减少搜索[k + 1, x],否则将其减少到[0, k].

你需要更聪明或更快的东西吗？