查找数字的第n个根的算法

本文介绍了查找数字的第n个根的算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在寻找一种有效的算法来查找数字的第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.