Think Python for CS114 12 The while statement 14 Strings

Chapter 13 Introducing algorithms

Loops are often used in programs that compute numerical results by starting with an approximate answer and iteratively improving it.

For example, one way of computing square roots is the Babylonian method. Suppose that you want to know the square root of $a$ . If you start with almost any estimate, $g$ , you can compute a better estimate with the following formula:

y=\dfrac{g+a/g}{2}

For example, if $a$ is 4 and $g$ is 3:

⬇

>>> a = 4

>>> g = 3

>>> g = (g + a/g) / 2

>>> print(g)

2.16666666667

The result is closer to the correct answer ( $\sqrt{4}=2$ ). If we repeat the process with the new estimate, it gets even closer:

⬇

>>> g = (g + a/g) / 2

>>> print(g)

2.00641025641

After a few more updates, the estimate is almost exact:

⬇

>>> g = (g + a/g) / 2

>>> print(g)

2.00001024003

>>> g = (g + a/g) / 2

>>> print(g)

2.00000000003

In general we don’t know ahead of time how many steps it takes to get to the right answer. But we can tell when it gets there, because the square of $g$ is $a$

⬇

>>> g = (g + a/g) / 2

>>> print(g)

2.0

>>> print(g**2)

4.0

When g**2 == a, we can stop. But another way, we continue while g͡**2 is not a. Here is a loop that starts with an initial estimate, x, and improves it until it stops changing:

⬇

g = 1

while g**2 != a:

print(g)

g = (g + a/g) / 2

For most values of a this works fine, but in general it is dangerous to test float equality. For example, this code snippet will not work when $a=2.4$ . Floating-point values are only approximately right: most rational numbers, like $1/3$ , and irrational numbers, like $\sqrt{2}$ , can’t be represented exactly with a float.

Rather than checking whether g**2 and a are exactly equal, it is safer to use the built-in function abs to compute the absolute value, or magnitude, of the difference between them. Here we repeat while the “error” is greater than some constant epsilon.

⬇

while abs(g**2 - a) > epsilon:

print(g)

g = (g + a/g) / 2

Where epsilon has a value like 0.0000001 that determines how close is close enough.

13.1 Algorithms

The Babylonian method is an example of an algorithm: it is a mechanical process for solving a category of problems (in this case, computing square roots).

To understand what an algorithm is, it might help to start with something that is not an algorithm. When you learned to multiply single-digit numbers, you probably memorized the multiplication table. In effect, you memorized 100 specific solutions. That kind of knowledge is not algorithmic.

But if you were “lazy”, you might have learned a few tricks. For example, to find the product of $n$ and 9, you can write $n-1$ as the first digit and $10-n$ as the second digit. This trick is a general solution for multiplying any single-digit number by 9. That’s an algorithm!

Similarly, the techniques you learned for addition with carrying, subtraction with borrowing, and long division are all algorithms. One of the characteristics of algorithms is that they do not require any intelligence to carry out. They are mechanical processes where each step follows from the last according to a simple set of rules.

Executing algorithms is boring, but designing them is interesting, intellectually challenging, and a central part of computer science.

Some of the things that people do naturally, without difficulty or conscious thought, are the hardest to express algorithmically. Understanding natural language is a good example. We all do it, but so far no one has been able to explain how we do it, at least not in the form of an algorithm.

13.2 Debugging

As you start writing bigger programs, you might find yourself spending more time debugging. More code means more chances to make an error and more places for bugs to hide.

One way to cut your debugging time is “debugging by bisection”. For example, if there are 100 lines in your program and you check them one at a time, it would take 100 steps.

Instead, try to break the problem in half. Look at the middle of the program, or near it, for an intermediate value you can check. Add a print statement (or something else that has a verifiable effect) and run the program.

If the mid-point check is incorrect, there must be a problem in the first half of the program. If it is correct, the problem is in the second half.

Every time you perform a check like this, you halve the number of lines you have to search. After six steps (which is fewer than 100), you would be down to one or two lines of code, at least in theory.

In practice it is not always clear what the “middle of the program” is and not always possible to check it. It doesn’t make sense to count lines and find the exact midpoint. Instead, think about places in the program where there might be errors and places where it is easy to put a check. Then choose a spot where you think the chances are about the same that the bug is before or after the check.

13.3 Glossary

reassignment:: Assigning a new value to a variable that already exists.
update:: An assignment where the new value of the variable depends on the old.
initialization:: An assignment that gives an initial value to a variable that will be updated.
increment:: An update that increases the value of a variable (often by one).
decrement:: An update that decreases the value of a variable.
iteration:: Repeated execution of a set of statements using either a recursive function call or a loop.
infinite loop:: A loop in which the terminating condition is never satisfied.
algorithm:: A general process for solving a category of problems.

13.4 Exercises

Exercise 13.1.

Copy the loop from Section 13 and encapsulate it in a function called mysqrt that takes a as a parameter, chooses a reasonable value of x, and returns an estimate of the square root of a.

To test it, write a function named test_square_root that prints a table like this:

⬇

a mysqrt(a) math.sqrt(a) diff

- ——— ———— —-

1.0 1.0 1.0 0.0

2.0 1.41421356237 1.41421356237 2.22044604925e-16

3.0 1.73205080757 1.73205080757 0.0

4.0 2.0 2.0 0.0

5.0 2.2360679775 2.2360679775 0.0

6.0 2.44948974278 2.44948974278 0.0

7.0 2.64575131106 2.64575131106 0.0

8.0 2.82842712475 2.82842712475 4.4408920985e-16

9.0 3.0 3.0 0.0

The first column is a number, $a$ ; the second column is the square root of $a$ computed with mysqrt; the third column is the square root computed by math.sqrt; the fourth column is the absolute value of the difference between the two estimates.

Exercise 13.2.

The mathematician Srinivasa Ramanujan found an infinite series that can be used to generate a numerical approximation of $1/\pi$ :

\frac{1}{\pi}=\frac{2\sqrt{2}}{9801}\sum^{\infty}_{k=0}\frac{(4k)!(1103+26390k% )}{(k!)^{4}396^{4k}}

Write a function called estimate_pi that uses this formula to compute and return an estimate of $\pi$ . It should use a while loop to compute terms of the summation until the last term is smaller than 1e-15 (which is Python notation for $10^{-15}$ ). You can check the result by comparing it to math.pi.