使用幂法计算Java中的第n个根
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/32553108/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Calculating nth root in Java using power method
提问by Sara Alaa Khodeir
I was trying to get a cubic root in java using Math.pow(n, 1.0/3)but because it divides doubles, it doesn't return the exact answer. For example, with 125, this gives 4.9999999999. Is there a work-around for this? I know there is a cubic root function but I'd like to fix this so I can calculate higher roots.
我试图在 java 中使用三次方根，Math.pow(n, 1.0/3)但因为它除以双打，所以它没有返回确切的答案。例如，对于 125，这给出了 4.9999999999。有解决方法吗？我知道有一个三次根函数，但我想解决这个问题，这样我就可以计算更高的根。
I would not like to round because I want to know whether a number has an integer root by doing something like this: Math.pow(n, 1.0 / 3) % ((int) Math.pow(n, 1.0 / 3)).
我不希望因为圆我想知道一个数目是否已做这样的事情的整数根：Math.pow(n, 1.0 / 3) % ((int) Math.pow(n, 1.0 / 3))。
回答by Manos Nikolaidis
The Math.roundfunction will round to the nearest long value that can be stored to a double. You could compare the 2 results to see if the number has an integer cubic root.
该Math.round功能将全面到可以存储到双最接近的长期价值。您可以比较 2 个结果以查看该数字是否具有整数三次根。
double dres = Math.pow(125, 1.0 / 3.0);
double ires = Math.round(dres);
double diff = Math.abs(dres - ires);
if (diff < Math.ulp(10.0)) {
// has cubic root
}
If that's inadequate you can try implementing thisalgorithm and stop early if the result doesn't seem to be an integer.
如果这还不够，您可以尝试实施此算法并在结果似乎不是整数时提前停止。
回答by Tunaki
Since it is not possible to have arbitrary-precision calculus with double, you have three choices:
由于不可能使用 进行任意精度的微积分double，因此您有以下三种选择：
- Define a precision for which you decide whether a
doublevalue is an integer or not. - Test whether the rounded value of the
doubleyou have is a correct result. - Do calculus on a
BigDecimalobject, which supports arbitrary-precision double values.
- 定义一个精度，您决定一个
double值是否为整数。 - 测试
double您所拥有的舍入值是否为正确结果。 - 对
BigDecimal支持任意精度双精度值的对象进行微积分。
Option 1
选项1
private static boolean isNthRoot(int value, int n, double precision) {
double a = Math.pow(value, 1.0 / n);
return Math.abs(a - Math.round(a)) < precision; // if a and round(a) are "close enough" then we're good
}
The problem with this approach is how to define "close enough". This is a subjective question and it depends on your requirements.
这种方法的问题是如何定义“足够接近”。这是一个主观问题，取决于您的要求。
Option 2
选项 2
private static boolean isNthRoot(int value, int n) {
double a = Math.pow(value, 1.0 / n);
return Math.pow(Math.round(a), n) == value;
}
The advantage of this method is that there is no need to define a precision. However, we need to perform another powoperation so this will affect performance.
这种方法的优点是不需要定义精度。但是，我们需要执行另一个pow操作，因此这会影响性能。
Option 3
选项 3
There is no built-in method to calculate a double power of a BigDecimal. This questionwill give you insight on how to do it.
没有计算 BigDecimal 的两倍幂的内置方法。这个问题会让你深入了解如何做到这一点。
回答by dimplex
回答by Paul Boddington
I wrote this method to compute floor(x^(1/n))where xis a non-negative BigIntegerand nis a positive integer. It was a while ago now so I can't explain why it works, but I'm reasonably confident that when I wrote it I was happy that it's guaranteed to give the correct answer reasonably quickly.
我写了这个方法来计算floor(x^(1/n))wherex是一个非负数BigInteger并且n是一个正整数。这是不久前的事了，所以我无法解释它为什么有效，但我有理由相信，当我写它时，我很高兴它可以保证相当快地给出正确的答案。
To see if xis an exact n-thpower you can check if the result raised to the power ngives you exactly xback again.
要查看是否x是一个精确的n-th幂，您可以检查提高到该幂的结果n是否x再次准确地返回给您。
public static BigInteger floorOfNthRoot(BigInteger x, int n) {
int sign = x.signum();
if (n <= 0 || (sign < 0))
throw new IllegalArgumentException();
if (sign == 0)
return BigInteger.ZERO;
if (n == 1)
return x;
BigInteger a;
BigInteger bigN = BigInteger.valueOf(n);
BigInteger bigNMinusOne = BigInteger.valueOf(n - 1);
BigInteger b = BigInteger.ZERO.setBit(1 + x.bitLength() / n);
do {
a = b;
b = a.multiply(bigNMinusOne).add(x.divide(a.pow(n - 1))).divide(bigN);
} while (b.compareTo(a) == -1);
return a;
}
To use it:
要使用它：
System.out.println(floorOfNthRoot(new BigInteger("125"), 3));
EditHaving read the comments above I now remember that this is the Newton-Raphson method for n-th roots. The Newton-Raphson method has quadratic convergence (which in everyday language means it's fast). You can try it on numbers which have dozens of digits and you should get the answer in a fraction of a second.
编辑阅读了上面的评论后，我现在记得这是第 n 个根的 Newton-Raphson 方法。Newton-Raphson 方法具有二次收敛性（这在日常语言中意味着它很快）。您可以在具有数十位数字的数字上进行尝试，您应该会在几分之一秒内得到答案。
You can adapt the method to work with other number types, but doubleand BigDecimalare in my view not suited for this kind of thing.
您可以调整方法与其他数字类型的工作，但double和BigDecimal在我看来不适合这种事情。
回答by Avneesh Singh
Well this is a good option to choose in this situation. You can rely on this-
那么在这种情况下这是一个不错的选择。你可以依靠这个——
System.out.println(" ");
System.out.println(" Enter a base and then nth root");
while(true)
{
a=Double.parseDouble(br.readLine());
b=Double.parseDouble(br.readLine());
double negodd=-(Math.pow((Math.abs(a)),(1.0/b)));
double poseve=Math.pow(a,(1.0/b));
double posodd=Math.pow(a,(1.0/b));
if(a<0 && b%2==0)
{
String io="\u03AF";
double negeve=Math.pow((Math.abs(a)),(1.0/b));
System.out.println(" Root is imaginary and value= "+negeve+" "+io);
}
else if(a<0 && b%2==1)
System.out.println(" Value= "+negodd);
else if(a>0 && b%2==0)
System.out.println(" Value= "+poseve);
else if(a>0 && b%2==1)
System.out.println(" Value= "+posodd);
System.out.println(" ");
System.out.print(" Enter '0' to come back or press any number to continue- ");
con=Integer.parseInt(br.readLine());
if(con==0)
break;
else
{
System.out.println(" Enter a base and then nth root");
continue;
}
}
回答by Avneesh Singh
It's a pretty ugly hack, but you could reach a few of them through indenting.
这是一个非常丑陋的 hack，但是您可以通过缩进来访问其中的一些。
System.out.println(Math.sqrt(Math.sqrt(256)));
System.out.println(Math.pow(4, 4));
System.out.println(Math.pow(4, 9));
System.out.println(Math.cbrt(Math.cbrt(262144)));
Result:
4.0
256.0
262144.0
4.0
Which will give you every n^3th cube and every n^2th root.
这将为您提供每个 n^3th 立方体和每个 n^2th 根。
回答by Grigoris Dimopoulos
You can use some tricks come from mathematics field, to havemore accuracy. Like this one x^(1/n) = e^(lnx/n).
您可以使用一些来自数学领域的技巧，以获得更高的准确性。像这样一个 x^(1/n) = e^(lnx/n)。
Check the implementation here: https://www.baeldung.com/java-nth-root
在此处检查实施：https: //www.baeldung.com/java-nth-root
回答by Vpn_talent
Here is the solution without using Java's Math.pow function. It will give you nearly nth root
这是不使用 Java 的 Math.pow 函数的解决方案。它会给你几乎第 n 个根
public class NthRoot {
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int testcases = scanner.nextInt();
while (testcases-- > 0) {
int root = scanner.nextInt();
int number = scanner.nextInt();
double rootValue = compute(number, root) * 1000.0 / 1000.0;
System.out.println((int) rootValue);
}
} catch (Exception e) {
e.printStackTrace();
}
}
private static double compute(int number, int root) {
double xPre = Math.random() % 10;
double error = 0.0000001;
double delX = 2147483647;
double current = 0.0;
while (delX > error) {
current = ((root - 1.0) * xPre + (double) number / Math.pow(xPre, root - 1)) / (double) root;
delX = Math.abs(current - xPre);
xPre = current;
}
return current;
}
回答by Vpn_talent
Find nth root Using binary search method.Here is the way to find nth root with any precision according to your requirements.
使用二分查找法找到第 n 个根。这是根据您的要求以任何精度找到第 n 个根的方法。
import java.util.Scanner;
public class FindRoot {
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int testCase = scanner.nextInt();
while (testCase-- > 0) {
double number = scanner.nextDouble();
int root = scanner.nextInt();
double precision = scanner.nextDouble();
double result = findRoot(number, root, precision);
System.out.println(result);
}
}
}
private static double findRoot(double number, int root, double precision) {
double start = 0;
double end = number / 2;
double mid = end;
while (true) {
if (precision >= diff(number, mid, root)) {
return mid;
}
if (pow(mid, root) > number) {
end = mid;
} else {
start = mid;
}
mid = (start + end) / 2;
}
}
private static double diff(double number, double mid, int n) {
double power = pow(mid, n);
return number > power ? number - power : power - number;
}
private static double pow(double number, int pow) {
double result = number;
while (pow-- > 1) {
result *= number;
}
return result;
}
}
