1

I'm trying to implement the n-th root algorithm for large numbers without using any predefined functions in Java. No sqrt, no pow, no abs, nothing.

The limitations are: 1. The number can be up to 17 digits. 2. The root's order can be from 2 to 10. 3. The precision of the result should be around 10 decimal points.

Is this do-able?

I've read a lot of answers on similar questions on nth root algorithm, Newton's method, other iterative methods, but most of them use either pow, abs, sqrt or other pre-defined functions.

What I've got still has predefined functions and is something I came up with after being inspired from other posts:

public static double getRoot3(double number){
    double guess = 2;
    double possibleRoot = Math.abs((guess*guess)-number);
    while(possibleRoot> 0.009 ){
        possibleRoot = Math.abs((guess*guess)-number);
        guess = ((number/guess)+guess)/2.0;
    }
    return guess;
}
public static void main(String[] args) {
    double number = 12;
    double result = getRoot3(number);
    System.out.println("Number: " + number);
    System.out.println("Square root of " + number + ": " +result);
    System.out.println("Test: " + result * result );
}

This uses a hard-coded number for the test: 12 and the results are as follows:

  • Number: 12.0
  • Square root of 12.0: 3.4641016200294548
  • Test: 12.000000033890693

So it's working, I'm getting a precision of 7 float points, but if I try to increase the preciion by adding zeroes into the while condition it breaks.

I tried to troubleshoot it and it appears that, at somepoint "possibleRoot" suddenly contains an E among the digits and the condition evaluates to false.

How can I increase the precision and how can I extend it for other roots like cubic or more? This one works only for square root right now.

1istbesser
  • 127
  • 2
  • 9
  • _suddenly contains an E_....wouldn't that just be scientific notation? [How to express numbers in scientific notation in java?](//stackoverflow.com/q/19984040) – 001 Jan 17 '18 at 21:34
  • 2
    A. you should be using BigDecimal instead of double. B Wikipedia has the answer on how to calculate the nth root of something – ControlAltDel Jan 17 '18 at 21:34

2 Answers2

0

By using BigDecimal you will avoid double/float precision issues, see Square root of BigDecimal in Java .

BluEOS
  • 576
  • 6
  • 13
-1

I don't think you will get it more precise. Java and other languages do have the "Floating Point Problem". It means, that whenever you use floats/doubles it will be slightly different from the original number. That comes from the limitations to represent numbers in memory.

Also, the "E" indicates that the number on the left side of it has to be multiplied by 10^x, where x is the right number of the "E". This will occur when the number has too many digits to display. Example:

125.34E3

= 125.34 * 10^3

= 125.34 * 1000

= 125340.0

ShietStone
  • 1
  • 3
  • Your summary of 'Java and other languages do have the "Floating Point Problem" ... whenever you use -> will be slightly different...' programming languages are not at the root of the issue, and there are absolutely some numbers that floating point can represent absolutely. It is also not true that you cannot be more precise. See BigDecimal – ControlAltDel Jan 17 '18 at 22:08