58 CHAPTER 1 Sets, Proof Templates, and Induction
1.8.2 An Algorithm to Generate Perfect Squares
We now demonstrate how you can generate all the perfect squares. A perfect square is any
integer n that is equal to k^2 for some integer k. For example, 1 is a perfect square, because
it is equal to 12. In addition 9 is a perfect square, because 9 equals 32. For the Perfect
Squares algorithm, we give an intuitive argument that the program is correct.INPUT:
OUTPUT: List of perfect squaresCounter = 0
while (TRUE) /* repeat forever */
Counter = Counter + 1
print Counter. CounterTo understand the Perfect Squares algorithm, trace its execution for the first few values
of Counter. The algorithm starts with Counter equal to 0 and then repeats the last two in-
structions forever. The first time through, the algorithm adds 1 to Counter, giving Counter
the value of 1, and prints 1 • 1. The second time through, it adds 1 to Counter, increas-
ing Counter from 1 to 2, and prints 2. 2. The third time, it adds 1 to Counter, increasing
Counter from 2 to 3, and prints out 3 .3. And so forth. It is obvious that the algorithm
works. In fact, for any natural number k, after the kth time through the loop, Counter is set
to k and the first k perfect squares have been printed.1.8.3 Two Algorithms for Computing Square Roots
There are many algorithms for finding the square root of an integer. The two algorithms
presented here use different strategies for finding a better and better approximation of a
square root. The first was found on ancient Babylonian cuneiform tablets. The second is a
variant of one that has been taught in schools. A fundamental problem with any approxi-
mation algorithm is to have a bound on how far an approximation is from the true value.
For both algorithms presented here, we can prove a result about the bound using induction.Square Root I
The Square Root I algorithm provides a method of finding an approximation to the square
root of an integer. In this case, the first approximation is a value less than the desired result.
Each iteration of the procedure gives a larger value than the previous one.