计算n次方根与整数运算 [英] Calculate Nth root with integer arithmetic

问题描述

有几个方法可以找到整数平方根只用整数运算。例如这个。它使有趣的阅读，也是一个非常有趣的理论，特别是对于我这一代在哪里这样的技术不是那么有用了。

There are a couple of ways to find integer square roots using only integer arithmetic. For example this one. It makes for interesting reading and also a very interesting theory, particularly for my generation where such techniques aren't so useful any more.

最主要的是，它不能使用浮点运算，所以排除了牛顿方法，它的推导。唯一的其他办法，我知道找根源是二项展开，但也需要浮点运算。

The main thing is that it can't use floating point arithmetic, so that rules out newtons method and it's derivations. The only other way I know of to find roots is binomial expansion, but that also requires floating point arithmetic.

什么技术/算法有计算积分第n根只用整数运算？

What techniques/algorithms are there for computing integral nth roots using only integer arithmetic?

编辑：感谢所有的答案为止。他们似乎都稍微更智能的试验和改进。有没有更好的办法？

Thanks for all the answers so far. They all seem to be slightly more intelligent trial and improvement. Is there no better way?

EDIT2：好的，所以它似乎没有聪明的办法做到这一点不经审判/改进，要么牛顿法或二进制搜索。任何人都可以提供两个在理论上的比较？我已经运行了一些两者之间的基准，发现它们非常相似。

Ok, so it would seem there is no smart way to do this without trial/improvement and either newtons method or a binary search. Can anyone provide a comparison of the two in theory? I have run a number of benchmarks between the two and found them quite similar.

推荐答案

您只能使用整数运算用牛顿的方法，步骤是一样的浮点运算，但你必须更换浮点运算符与相应的整数在具有不同的运营商对这些语言的操作员。

You can use Newton's method using only integer arithmetic, the step is the same as for floating point arithmetic, except you have to replace floating point operators with the corresponding integer operators in languages which have different operators for these.

比方说，你想找到 A＆GT的整数k个根; 0 ，这应该是最大的整数研究，使得 R 2 K＆LT = A 。你开始用任意正整数（当然是一个很好的起点帮助）。

Let's say you want to find the integer-k-th root of a > 0, which should be the largest integer r such that r^k <= a. You start with any positive integer (of course a good starting point helps).

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 ==＆GT;步骤（K，A，X）＆GT;。= X

这篇关于计算n次方根与整数运算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！