Square roots via Newton's method in Java

Question

This time, one of my labs state that I need to write a complete java program which will calculate the square root of a number via Newton's method. The reason behind using Newton's method, as opposed to Math.sqrt(x) is so that I get to practice the use of simple IO, conditional expressions, loops, and nested loops.

The complete set of instructions are as follows:

Assume you want to compute the square root of x.

First: We always start with a guess/approximation that the square root of any value for x is y = 1.0

Next we compute the average of this y value plus the x value divided by the y value.

This equation → ( y + (x/y) ) / 2.

The result from solving this equation then becomes the new approximation of the square root (the new y value). This new y value will be closer to the actual value for the square root of x than the original y guess of 1.0

Repeat the step above using each new computed value for y as the new guess for the square root of x until the y value is close enough.

For example: suppose we want to compute the square root of 2 then the computation would proceed as follows (all values as double): x = 2.0 and y = 1.0

Iteration     Guess   Quotient                 Average
Number        for y   x/y                      ( y + (x/y) ) / 2

        1       1.0   2.0/1.0 => 2.0           (1.0 + 2.0/1.0)/2.0 => 1.5
        2       1.5   2.0/1.5 => 1.33333       (1.5 + 1.33333)/2.0 => 1.41666
        3   1.41666   2.0/1.41666 => 1.41176   (1.41666 + 1.41176)/2.0 => 1.41421
        4   1.41421   etc...

The solution is achieved when the square of the guess is “same” as the value of x (the definition of square root). Unfortunately, for most numbers the exact solution can never be reached this way so the process continues forever. In order to ensure that the computation process actually stops we must change the stop condition of the loop to be “close enough”. Close enough is the tolerance (a small number) which we accept as being a good approximation of the exact value.

Close enough occurs when the absolute difference between x and (y*y) is less than the tolerance (defined by the user).

In order to see how your program is progressing print out the iteration number and the guess value. Use at least 8 digits after the decimal value and 2 before the decimal. In the example run shown below only 5 digits after the decimal are used.

Example Run:

Square Root approximation program

Enter the value           : 2.0
Enter the tolerance       : 0.00001

Iteration     Guess      Guess     Absolute value
Number        value      Squared       Difference

        1   1.00000      1.00000          1.00000 
        2   1.50000      2.25000          0.25000 
        3   1.41666      2.00693          0.00693 
        4   1.41421      1.99999          0.00001 

Approximated Square root of 2.0 = 1.41422 

The resulting code that I wrote to solve this problem is as follows:

import java.util.Scanner;

/**
 * SRN: 507-147-9
 */
public class Lab8_1 {

    public static void main(String[] args) {

        // new input
        Scanner input = new Scanner(System.in);

        // define vars
        int iteration = 1;
        double x, y, guessSquared = 1, quotient, average, tolerance, absValDiff = 1;

        y = 1.0;

        // program name
        System.out.println("Square Root approximation program");
        System.out.println();

        // prompt variables
        System.out.print("Enter the value           : "); // prompt x value
        x = input.nextDouble(); // store input as "x"
        System.out.print("Enter the tolerance       : "); // prompt tolerance
        tolerance = input.nextDouble(); // store input as "tolerance"
        System.out.println();

        // print formatted header
        System.out.println("Iteration         Guess          Guess         Absolute value");
        System.out.println("Number            value          Squared           Difference");
        System.out.println();

        // print first calculation
        System.out.printf("%9d   %11.8f      %11.8f          %11.8f \n", iteration, y, guessSquared, absValDiff);

        // increment the value of "iteration" by 1
        iteration++;

        while (absValDiff > tolerance) {

            // looped calculations
            quotient = x / y;
            average = (y + quotient) / 2;
            y = average;
            guessSquared = y * y;
            absValDiff = Math.abs(x - guessSquared);

            // print results per iteration
            System.out.printf("%9d   %11.8f      %11.8f          %11.8f \n", iteration, y, guessSquared, absValDiff);

            // increment the value of "iteration" by 1
            iteration++;
        }
        // print results
        System.out.println();
        System.out.printf("Approximated Square root of " + x + " = %11.8f \n", y);
    }
}

With this, I do have a question regarding the accuracy of my responses as opposed to the ones in the example. Even though mathematically, the correct floating point numbers are stored in my variables, when the results are printed to the console, the last digit of my floating point is always rounded up. From my perspective, this feels similar to the round-off errors one would get on a calculator, where the result of the calculations performed are only approximate representations of the actual numbers, since only fixed point rational numbers can be represented exactly within the machine.

An example of this kind of error would be: 2/3 = 0.666666667

Is there a way that I could capture a set length for my variables using the printf format without allowing the number to be round up when it is printed to the console?

Answer 1

Is there a way that I could capture a set length for my variables using the printf format without allowing the number to be round up when it is printed to the console?

You can use a "trick"

String output = String.format("%12.9f", doubleValue);
System.out.println(output.substring(0, output.length() - 1);

Answer 2

Your program looks pretty good so far. Here are some things I noticed:

• There's a logical error for your first iteration when you calculate absValDiff. You always initialise absValDiff to 1 and don't recalculate it for the first iteration, so if you put in a value such as x = 5, it will say the difference between your first guess (y = 1) squared and x is only 1, when in fact it should be 4.

• As a result of the above, this also means that asking for any tolerance greater than or equal to 1 doesn't work correctly, and the program ends immediately. Asking for a tolerance of 2 for example doesn't work correctly.

• You might be able to write your comments to be more useful to other readers. Unless you've been told otherwise on your course, you can assume that the person reading your code understands what the language does, and is more interested in why your code is taking the steps that it does. For example:

  // define vars
  int iteration = 1;
  double x, y, guessSquared = 1, quotient, average, tolerance, absValDiff = 1;
  

  It's clear that you're defining variables here, so you could try explaining what you're doing instead. Why not try telling the reader what the variables are for?

• It's usually easier to declare your variables as you need them, rather than all at the top of the method. For a further reference, see the section on Declarations here. As mentioned in that source, while it was tradition in older programming languages to declare all your variables upfront, it's generally not considered best practice to do that now.

Changing all of this, your code might look something more like so:

import java.util.Scanner;

/**
 * SRN: 507-147-9
 */
public class Lab8_1 {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int iteration = 1; // Counts the current iteration number at each step.
        double y = 1.0; // Initial guess for the square root of the number x.
        double guessSquared = y * y; // The value y^2 which we want to be close to x.

        System.out.println("Square Root approximation program");
        System.out.println();

        System.out.print("Enter the value           : ");
        // The number we intend to approximate the square root of.
        double x = input.nextDouble(); 
        System.out.print("Enter the tolerance       : ");
        // The tolerance so that we terminate if |y^2 - x| < tolerance.
        double tolerance = input.nextDouble();
        System.out.println();
        
        // Compute the initial difference between x and the square of
        // the approximate square root.
        double absValDiff = Math.abs(x - guessSquared);

        // Print formatted header.
        System.out.println("Iteration         Guess          Guess         Absolute value");
        System.out.println("Number            value          Squared           Difference");
        System.out.println();

        // Print the results for the first iterate
        System.out.printf("%9d   %11.8f      %11.8f          %11.8f \n", iteration, y, guessSquared, absValDiff);
        iteration++;

        // Iterate using Newton's method until we obtain a value within tolerance of
        // the true square root.
        while (absValDiff > tolerance) {
            // Calculate the new approximation for x using 
            // Newton's method, where given the previous approximation y,
            // the next approximation is given by (y + (x / y)) / 2.
            double quotient = x / y;
            y = (y + quotient) / 2;
            guessSquared = y * y;
            // Compute the new difference between the square of our approximation and x.
            absValDiff = Math.abs(x - guessSquared);

            // Print results per iteration.
            System.out.printf("%9d   %11.8f      %11.8f          %11.8f \n", iteration, y, guessSquared, absValDiff);
            iteration++;
        }
        // Print results for the final iteration which was in tolerance.
        System.out.println();
        System.out.printf("Approximated Square root of " + x + " = %11.8f \n", y);
    }
}

In order to avoid the rounding (and instead truncate the number), you could use DecimalFormat, as explained here if you wanted an alternative approach to Gilbert Le Blanc's method. After importing java.text.DecimalFormat and java.math.RoundingMode, you can use it as follows:

DecimalFormat df = new DecimalFormat("#.##");
df.setRoundingMode(RoundingMode.DOWN);
System.out.println(df.format(0.66999f));

which would output 0.66.