Ch 6 Lab: Calculating Square Root

Ch 6 Lab: Newton's Method for Calculating Square Root

Authors: Ralph Morelli and Bronzell Dinkins
Trinity College, Hartford, CT
For use with Chapter 6

Brief description

This is a lab that is suitable for Chapter 6. It requires a conditional loop. It uses a simple applet interface, including TextArea and TextField components. This lab requires students to take more of a role in designing their solution. It asks that they prepare a design document -- including UML diagrams and pseudocode descriptions of the key algorithms involved -- before beginning to code.

Objectives

The objectives of this lab are:

To give practice designing an object-oriented program.
To give practice using simple conditional loop constructs.

Problem Statement

Newton's method for calculating the square root of N starts by making a (non zero) guess at the square root. It then uses the original guess to calculate a new guess, according to the following formula:

    
       guess = (( N / guess) + guess) / 2 ;

No matter how wild the original guess is, if we repeat this calculation the algorithm will eventually find the square root of N.

Design a Java applet that let's the user input a number N, a maximum error that determines how close Newton's method should come to the square root calculated by Math.sqrt(), and the user's initial guess. Then calculate the square root using Newton's method and report both the square root and the number of guesses required to calculate it.

Before Lab

Read Chapter 6 of Java, Java, Java, 3E and carefully read this lab writeup.

Object Oriented Design

Before creating your Codewarrier project and before beginning to code your solution, you must hand in, for approval, a design document containing the elements described below. This should be done within the first hour of lab, and must be approved before you can start writing code

GUI Design

Follow the GUI design shown in the demo program. This involves three input TextFields and an output TextArea. The TextFields should all be associated with ActionListeners.

Object Decomposition and Class Design

What objects will your solution use? Follow the design shown on pages 314-318, which utilizes two objects, an applet that serves as a user interface and a computational object, which handles the computation of the square root. Let's call the computational object NewtonTester. For each object, draw its UML class diagram showing its name, instance variables, and its public and private methods.

One public method that your NewtonTester class should have is the sqrt() method. This is the method that the applet will call to calculate the square root of N.

Don't forget that your NewtonTester object must not only be able to calculate the square root of a number that it is given, it must also remember how many iterations it took to calculate the square root. It must also "know" what the tolerance is and what the initial guess is in order to perform its calculation. How will you handle these parts of the problem?? HINT: What additional instance variables and instance methods will you need for these tasks?

Method Design

For this project your applet methods, such as init() and actionPerformed() can be modeled after the applets you designed in previous labs. The init() method should instantiate the GUI components used by the applet and add them to the applet. The actionPerformed() method should input the values that the user typed into the TextFields and pass them to the NewtonTester object to perform the calculation.

For the NewtonTester you'll need methods to set and get the values of certain instance variables -- e.g., the number of iterations used -- as well as the method to calculate the square root.

Algorithm Design

There are two algorithms that you need to think about in detail before you begin coding. One is the algorithm for the applet's actionPerformed() method. The other is the algorithm for the NewtonTester object's sqrt() method. Write out pseudocode descriptions of both of these algorithms. Remember, in addition to calculating the square root, the square root method should also keep track of how many iterations were required. How are you going to handle this?

Implementation

After your design documents have been approved, you may create your CodeWarrier project and begin coding your solution. Your code should closely follow your design.

Use the stepwise refinement approach as you develop your code, compiling and testing short segments of your code at each stage. Here are some appropriate steps:

Create the applet's layout, up through init(). Compile and Test.
Create the applet's event handling, initially just echoing the user's input in the TextArea. Compile and Test.
Create the NewtonTester object and test passing a value between the applet and its sqrt() method. The sqrt() method can just return the value it is passed for this stage. Compile and Test.
Develop and test the square root algorithm.

Optional

The applet should require the first guess to be greater than zero. Division by zero will cause the applet to hang up. Modify the applet to display the error message "First Guess must be Greater Than Zero" in the TextArea if the initial guess is zero.
Newton's method for calculating the square root of a number requires an initial guess. If we compute sqrt(10), using the not-very-good guess of 1.0 and carrying 8 digits accuracy, the results are as follows.
(10.0/1.0 + 1.0)/2 = 5.5
(10.0/5.5 + 5.5)/2 = 3.6590909
(10.0/3.6590909 + 3.6590909)/2 = 3.1960051
(10.0/3.1960051 + 3.1960051)/2 = 3.1624556
(10.0/3.1624556 + 3.1624556)/2 = 3.1622777
(10.0/3.1622777 + 3.1622777)/2 = 3.1622777
The last two results are the same, so we stop. The result is correct to all digits shown.
Modify the applet so that the terminating condition is NOT based on the results obtained from the square root calculated by Math.sqrt(), but rather on whenever TWO SUCCESSIVE guesses are within the accuracy specified.

Hand in

Hand in your appropriately documented source code. For documentation guidelines, see Documentation Specifications.