Iteration

Multiple Assignments

It's legal to assign a new value to an existing variable. A new assignment makes an existing variable refer to a new value (and stop referring to the old value).


In [2]:
bruce = 5
print(bruce)
bruce = 7
print(bruce)


5
7

With multiple assignment it is especially important to distinguish between an assignment operation and a statement of equality. Because Python uses the equal sign (=) for assignment, it is tempting to interpret a statement like a = b as a statement of equality. It is not!

First, equality is a symmetric relation and assignment is not. For example, in mathematics, if a = 7 then 7 = a. But in Python, the statement a = 7 is legal and 7 = a is not.

Furthermore, in mathematics, a statement of equality is either true or false, for all time. If a = b now, then a will always equal b. In Python, an assignment statement can make two variables equal, but they don’t have to stay that way:


In [4]:
a = 5
print("a is: ", a)
b = a # a and b are now equal
print("b is: ", b)
a = 3 # a and b are no longer equal
print("a is: ", a)


a is:  5
b is:  5
a is:  3

Updating Variables

One of the most common forms of multiple assignment is an update, where the new value of the variable depends on the old.

x = x + 1

This means “get the current value of x, add one, and then update x with the new value.”

If you try to update a variable that doesn’t exist, you get an error, because Python evaluates the right side before it assigns a value to x:


In [5]:
x = x + 1


---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-5-f2b128a9dd19> in <module>()
----> 1 x = x + 1

NameError: name 'x' is not defined

Before you can update a variable, you have to initialize it, usually with a simple assignment:

x = 0
x = x + 1

Updating a variable by adding 1 is called an increment; subtracting 1 is called a decrement.

The while Statements

Computers are often used to automate repetitive tasks. Repeating identical or similar tasks without making errors is something that computers do well and people do poorly.

We have seen recursion to perform repetition, which is also called iteration. Because iteration is so common, Python provides several language features to make it easier, like for loops which we will cover later.

Another is the while statement. Here is a version of countdown that uses a while statement:


In [6]:
def countdown(n):
    while n > 0:
        print(n)
        n = n - 1
    print('Blastoff!')
countdown(10)


10
9
8
7
6
5
4
3
2
1
Blastoff!

You can almost read the while statement as if it were English. It means, “While n is greater than 0, display the value of n and then reduce the value of n by 1. When you get to 0, display the word Blastoff!

Here is the flow of execution for a while statement:

  1. Evaluate the condition, yielding True or False.
  2. If the condition is false, exit the while statement and continue execution at the next statement.
  3. If the condition is true, execute the body and then go back to step 1.

This type of flow is called a loop because the third step loops back around to the top.


break

Sometimes you don’t know it’s time to end a loop until you get half way through the body. In that case you can use the break statement to jump out of the loop.

For example, suppose you want to take input from the user until they type done. You could write:


In [8]:
while True:
    line = input('> ')
    if line == 'done':
        break
    print(line)

print('Done!')


> Enes
Enes
> This is cool
This is cool
> done
Done!

The loop condition is True, which is always true, so the loop runs until it hits the break statement.

Each time through, it prompts the user with an angle bracket. If the user types done, the break statement exits the loop. Otherwise the program echoes whatever the user types and goes back to the top of the loop.

This way of writing while loops is common because you can check the condition anywhere in the loop (not just at the top) and you can express the stop condition affirmatively (“stop when this happens”) rather than negatively (“keep going until that happens.”).

Square Roots

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 Newton’s method. Suppose that you want to know the square root of a. If you start with almost any estimate, x, you can compute a better estimate with the following formula:

$$ y = \frac{x + a/x}{2} $$

For example, if a is 4 and x is 3:


In [9]:
a = 4
x = 3
y = (x + a/x)/2
print(y)


2.1666666666666665

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


In [10]:
x = y 
y = (x + a/x)/2
print(y)


2.0064102564102564

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


In [11]:
x = y 
y = (x + a/x)/2
print(y)


2.0000102400262145

In [12]:
x = y 
y = (x + a/x)/2
print(y)


2.0000000000262146

In general we don’t know ahead of time how many steps it takes to get to the right answer, but we know when we get there because the estimate stops changing.

When y == x, we can stop. Here is a loop that starts with an initial estimate, x, and improves it until it stops changing:


In [14]:
a = 4
x = 3
while True:
    print(x)
    y = (x + a/x) / 2
    if y == x:
        break
    x = y


3
2.1666666666666665
2.0064102564102564
2.0000102400262145
2.0000000000262146
2.0

For most values of a this works fine, but in general it is dangerous to test float equality. 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 x and y 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:


In [15]:
a = 2
x = 0.1
epsilon = 0.0000001
while True:
    print(x)
    y = (x + a/x) / 2
    if abs(y-x) < epsilon:
        break
    x = y


0.1
10.05
5.124502487562189
2.7573921384195743
1.741357580449592
1.444943381958916
1.414540330128693
1.4142136001158034

Try Yourself!

Encapsulate this loop in a function called square_root that takes a as a parameter, chooses a reasonable value of x, and returns an estimate of the square root of a.


In [ ]:

Algorithms

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

It is not easy to define an algorithm. 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 probably cheated by learning 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 in which each step follows from the last according to a simple set of rules.

In my opinion, it is embarrassing that humans spend so much time in school learning to execute algorithms that, quite literally, require no intelligence. On the other hand, the process of designing algorithms is interesting, intellectually challenging, and a central part of what we call programming.

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.

Exercises

Exercise 1: The built-in function eval takes a string and evaluates it using the Python interpreter. For example:

eval('1 + 2 * 3') # Result -> 7
import math
eval('math.sqrt(5)') # Result -> 2.2360679774997898
eval('type(math.pi)') # Result -> <type 'float'>

Write a function called eval_loop that iteratively prompts the user, takes the resulting input and evaluates it using eval, and prints the result.

It should continue until the user enters 'done', and then return the value of the last expression it evaluated.


In [ ]:

Exercise 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_{k=0}^{\infty} \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.

Solution Link


In [ ]: