Previous page Next page Navigation bar

Calculator Programming Tutorial

Programming Building Blocks I

Exercises

Square Roots

Background Information

Squaring a number means multiplying it by itself, and is denoted by a superscript 2. For example, 22 = 2×2 = 4, 32 = 3×3 = 9, and 52 = 5×5 = 25. The square root of a number is a number which, when squared, results in the original number, and is denoted by a radical sign (√). For example, √25 = 5. Similarly, cubing a number means multiplying it by itself twice: 33 = 3×3×3 = 27, and the cube root of 27 is 3.

The square root of numbers which are not perfect squares can be computed approximately; for example, √2 is approximately 1.414213562. There is an algorithm similar to the long division algorithm that can be used to compute square roots. However, this algorithm is laborious.

A much faster procedure based on Newton’s method is frequently used to extract square roots on computers.

Newton’s method is a root-finding procedure: it finds places where a function f(x) is equal to zero. It approximates f(x) near a value x0 by a line passing through the point (x0, f(x0)) and having the same slope as the graph of the function itself at that point. The graph of the function has the slope f(x0), the derivative of f at x0. The root of f(x) is approximated by the point at which this line has a root. This point is generally a better approximation to the root of the function than is x0, and is called x1. The approximation by a line process is repeated at x1, yielding a better approximation x2, and so on.

The equation of the approximating line is:

Y sub i of x equals f of x sub 0 plus (x minus x sub 0) times f prime of x sub 0

Letting xi+1 be the point where this is equal to zero, we have:

x sub i+1 equals x sub i minus f at x sub i divided by f prime at x sub i

This works for any differentiable function f(x).

Now, suppose we want to compute the square root x of a value a. We need to define a function which has a zero when x is the square root of a. The function x2-a serves nicely: when x is equal to the square root of a, x2-a = (√a)2a = a-a = 0. Applying Newton’s method, we have:

x sub i+1 equals one-half of (x sub i plus a divided by x sub i)

As it happens, this process converges for all positive a with any positive initial value x0: for any positive value a, there will come a time when successive xi values are arbitrarily close together, and they will be arbitrarily close to the actual value of the square root. We can detect this convergence by noting when successive xi values differ by only the amount we are willing for the answer to be wrong. Suppose we want the answer we get to be accurate to 10 digits: then we want

absolute value of (x sub i+1 minux x sub i) less than or equal to 10 to the minus 10th times x sub i

So the flowchart of the square root extraction process would be:

Flowchart of square root by Newton's method, click for text algorithm

Part 1

Why does this algorithm initialize x0 to be (a+1)/2? (Hint: If it initialized x0 to be 1, what would the first value of x1 be?) In your estimation, is it worth modifying the algorithm to initialize x0 to (a+1)/4 + a/(a+1)? Why or why not? If you cannot decide whether this modification is worthwhile, what further information would you need in order to be able to decide?

Why does this algorithm assign x1 to x0? Explain your answer in terms of xi and xi+1. What names for the variables in the algorithm would be more descriptive of their function than x0 and x1?

Flowcharts use separate boxes to indicate the sequencing of computations. Computations in the same box can be carried out in any order, but computations in different boxes must be carried out in the order in which the boxes appear. Can the process (rectangular) boxes in this flowchart be rearranged without changing the results? Why or why not? Is there a computation that can be moved to a different box without changing the results? Why or why not?

This algorithm uses a test in the middle of the loop to determine when the algorithm can exit the loop. Many programmers feel a test at the beginning or end of a loop is preferable to a test in the middle of the loop, and many programmers feel a test at the beginning of the loop is most preferable. Can the computations and test in the loop be rearranged to have the test at the end of the loop, without changing the results? How could the algorithm be restructured to use a test at the beginning of the loop?

Part 2

Write an interface definition for a square root subroutine. Write a subroutine using the interface that computes the square root according to the flow chart above. Write a program that calls the square root function and displays the results for the values 1, 2, 3, 4, and 5.

In JavaScript, the function Math.abs(x) computes the absolute value of the value x. In Visual Basic for Applications, the function Abs(x) computes the absolute value of the value x. In the calculator, the operator Abs (OPTN F6 [next] F4 [NUM] F1 [ABS] on the 9850, OPTN next F1 [NUM] F1 [ABS] on the 7400) x computes the absolute value of the value x.

Part 3

Write a program to compare the square root subroutine you wrote in part 1 and the calculator’s or language’s square root built-in function. Have the program accept the value used as an argument to the routines from the user. Compare your routine and the calculator’s or language’s square root built-in function for the values 1, 2, 4, 10, and 100.

In JavaScript, the function Math.sqrt(x) computes the square root of the value x. In Visual Basic for Applications, the function sqr(x) computes the square root of the value x. In the calculator, the operator √ (SHIFT x2) x computes the square root of the value x.

Part 4

Try the following extreme values for a using the program you wrote in part 3: 1×10-99, 1×10-50, 1×1050, 9.999999999×1099, and 0. Does your square root subroutine work for all of these? (The actual square roots are approximately 3.16227766×10-50, 1×10-25, 1×1025, approximately 1×1050, and 0, respectively.) Is this an error in your implementation of the algorithm, an error in the algorithm itself, an error in problem analysis, an error in the problem statement, or an error in use? What can you do about it?

What happens if a is negative? What can you do about it?

Part 5

Modify your program to extract cube roots instead of square roots. The relevant approximation is:

x sub i+1 equals one-third (2 x sub i plus (a divided by (x sub i squared)))

What should your initial value be? How does this program behave when presented with negative numbers? With zero?

[ Previous page | Top of page | Next page ]

Previous page Top of page Next page Navigation bar

Copyright © 2001 Brian Hetrick
Page last updated 30 December 2001.

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Preface

Introduction

Fundamentals

Building Blocks I

Introduction

Comments

Data Types

Numbers

Variables

Expressions

Control Flow I

Control Flow II

Subprograms

Basic I/O

Algorithms

A First Program

Examples

Exercises

Square Roots

Clock Hands

Answers

Modularization

Data Structures I

Recursion

Program Attributes

Building Blocks II

Algorithm Analysis

Structuring

Data Structures II

Abstract Types

Objects

Problem Analysis

Reference Card

References

Puzzles

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data