查找数字的第n个根的算法 [英] Algorithm to find nth root of a number

问题描述

我正在寻找一种有效的算法来查找数字的第n个根.答案必须是整数.我发现牛顿法和二等分法是流行的方法.有没有有效且简单的整数输出方法?

I am looking for an efficient algorithm to find nth root of a number. The answer must be an integer. I have found that newtons method and bisection method are popular methods. Are there any efficient and simple methods for integer output?

推荐答案

#include <math.h>
inline int root(int input, int n)
{
  return round(pow(input, 1./n));
}

这几乎适用于整个整数范围(因为IEEE754 8字节 double 可以准确表示整个32位 int 范围，它们是表示形式和几乎在每个系统上使用的大小).而且我怀疑在非古代硬件上，任何基于整数的算法是否速度更快.包括ARM.嵌入式控制器(微波炉洗衣机类型)可能没有浮点硬件.但是问题的那一部分没有得到明确说明.

This works for pretty much the whole integer range (as IEEE754 8-byte doubles can represent the whole 32-bit int range exactly, which are the representations and sizes that are used on pretty much every system). And I doubt any integer based algorithm is faster on non-ancient hardware. Including ARM. Embedded controllers (the microwave washing machine kind) might not have floating point hardware though. But that part of the question was underspecified.

这篇关于查找数字的第n个根的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！