The Babylonian Algorithm for Square Root Approximation

Perhaps the first algorithm used for approximating the square root of S is known as the "Babylonian method", named after the Babylonians, or "Heron's method", named after the first-century Greek mathematician Heron of Alexandria who gave the first explicit description of the method. It can be derived from (but predates by 16 centuries) Newton's method.

The basic idea is that if x is an overestimate to the square root of a non-negative real number S then S/x will be an underestimate and so the average of these two numbers may reasonably be expected to provide a better approximation. More precisely, assuming S is a positive number:

Make a guess at the answer (you can pick S/2 as your initial guess).

Compute r = S / guess.

Set new guess = (guess + r) / 2

Go back to step 2 until the last two guess values are within 1% of each other1.

To complete this lab project:

Complete the method definitions for the following methods in CPS150_Lab19.java:

static double getInput(double min)

static double sqrt(double S)

/* * CPS 150 * Algorithms & Programming I * * Section *** enter your section number here *** * Spring 2017 */ package cps150_lab19;

import java.io.*; import java.util.*;

/** * Lab Project 19 * The Babylonian Algorithm * * @author *** enter your name here *** */ public class CPS150_Lab19 { // *** global variables for input and output objects *** static Scanner kbd = new Scanner( System.in ); static PrintStream out = System.out; static PrintStream err = System.err; /** * getInput(double) -> double * * method repeatedly prompts and gets user input until an double value * is entered that is at least as large as the given minimum value * method returns the first input that meets this requirement * * method prompts user with message: * "Enter a number greater or equal to m: ", where m is the * given minimum (parameter) value * method rejects all non-double input with error message: * "Invalid data type (not numeric)" * method rejects all invalid input (i.e., less than m) with error message: * "Invalid value (too small)" * * ex: getInput(1.0) -> 15.000000 * * *** TO DO: ADD getInput METHOD DEFINITION IMMEDIATELY BELOW THIS LINE ****/

/** * sqrt(double) -> double * * method implements the Babylonian Algorithm to estimate * the square root of the given number: * * 1. Make a guess at the answer (you can pick S/2 as your initial guess). * 2. Compute r = S / guess. * 3. Set new guess = (guess + r) / 2 * 4. Go back to step 2 until the last two guess values are within 1% of each other * * ex1: sqrt(4.0) -> 2.000000 * ex2: sqrt(7.5) -> 2.738615 * ex3: sqrt(9.0) -> 3.000015 * * *** TO DO: ADD sqrt METHOD DEFINITION IMMEDIATELY BELOW THIS LINE ****/

/* *** YOU ARE NOT ALLOWED TO MODIFY ANY CODE BELOW THIS LINE. *** */ /* *** DOING SO WILL RESULT IN A GRADE OF 0 FOR THIS LAB PROJECT. *** */ /** * CPS150_Lab19 : double ; double * * program is given a positive number S as user input * program uses the Babylonian Algorithm to estimate * and output the square root of S * * ex1: user inputs 4.0; program outputs 2.00 * ex2: user inputs 7.5; program outputs 2.74 * ex3: user inputs 9.0; program outputs 3.00 */ public static void main(String[] args) { double S; // input var double result; // output var (square root of S) // 1. get a positive number S from the user S = getInput(1); // 2. estimate the square root of S result = sqrt(S); // 3. output the square root of S out.printf("\tThe square root of %.2f is %.2f ", S, result); } // end main method } // end CPS150_Lab19

Sample Run (user input highlighted: run Enter a number greater or equal to 1.0 hello Invalid data type (not numeric) Enter a number greater or equal to 1.0 -6 Invalid value (too small) Enter a number greater or equal to 1.0 0 Invalid value (too small) Enter a number greater or equal to 1.0 10 The square root of 10.00 is 3.16 BUILD SUCCESSFUL (total time 12 seconds)