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?

• Ralf Kleberhoff: Regarding the round up vs. round down question: surely printf() rounds to the closest number, up or down. And 2/3 = 0.666666667 is in fact a better approximation for the infinite digits series of 0.666666... than 2/3 = 0.666666666. So, it's not an error, but the best possibility, and I wouldn't change that behaviour.

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);

• mdfst13: Note that this fails if the number ends .9999999995 -- because this rounds first (which would make that number 1.0000000000) and then removes the last digit. Using DecimalFormat with RoundingMode.DOWN avoids that caveat.

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.