Sep 4

Lists and loops

Lists

The list tutorial contains the main features, so I won't repeat it.

In addition, there are a large number of list methods. Note that some of these methods modify the list in place. This differs from string methods like upper which do not modify the string.

For loops

For loops are similar to while loops, but execute a block of code once for each element in a list.

L = [1, 6, 12, -3]
for x in L:
    print(x + 5)

For loops are great for processing data: the list can contain lines in a file, moves in a chess program, buttons to draw on the screen, and many, many other types of data. Using the for loop, we can process each of these items one by one.

Loop Counters

In some situations, the data we want to process is not natuarally in a list. In this case, we instead use a loop counter. This is just an integer variable that counts/controls the loop execution. An example:

Leibniz's formula for computing pi is

pi = 4 - 4/3 + 4/5 - 4/7 + 4/9 - ...

We notice that the numerator is always 4, the denominators are the odd numbers, and the sign alternates between one and minus one. Since this is an infinite series with terms getting smaller and smaller, we can approximate pi by taking the first few terms. Say we want to compute the first 100 terms. What we need to do is compute each term, add it into the running total, and move to the next term. A loop is perfect for this, except there is no natural list since we have not yet computed any terms. Instead, since we want to execute a block of code 100 times, we just make up a list of length 100. The list we will use is [0,1,2,3,4,...,99]. We can now use a for loop on this list we just created to compute an approximation to pi. In python, creating lists like this is so common there is a function to do it for us, range.

n = 1000 # The number of terms to compute
pi = 0.0

for i in range(n):
    denom = i * 2 + 1
    pi = pi + 4.0/denom * (-1)**i
print(pi)

Range

Try running the following code

print(list(range(4)))
print(list(range(1, 7)))
print(list(range(4, 9, 2)))
print(list(range(4, 10, 2)))
print(list(range(0, 20, 3)))

In python, whenever we have some computation or data which is not naturally in a list, we create a loop counter by using some form of range.

Monte Carlo

Here is another way of approximating pi using the Monte Carlo method (see also this page) The idea is to generate a lot of random points in the coordinate plane with 0 <= x <= 1 and 0 <= y <= 1 (so a box of side length one in the first quadrant). We then count the number of points which are within distance one of the origin. These are the points that are within a circle of radius one.

See this image

The area of the square is 1 since the sides are length 1. The area of the part of the circle in this quadrant is pi/4 since the whole area of a circle is pi r2 with radius one and this is one-fourth of the circle. To approximate pi, we use the number of points as an estimate of this area. The ratio of points inside the circle to the total number of points should be the same as the ratio of the area of the circle to the area of the box. Thus

    points inside circle     area of quarter circle   pi/4
    --------------------  =  ---------------------- = ----
    total # of points        area of box               1

Here is code which does this, using the random module.

import random
import math

numPoints = 100000
numInside = 0.0

for i in range(numPoints):
    # generate a random point in the first quadrant
    x = random.random()
    y = random.random()
    # compute distance to the origin
    dist = math.sqrt(x**2 + y**2)

    if dist <= 1:
        numInside += 1

piover4 = numInside / numPoints
print("Pi is approx ", piover4 * 4)

Notice how we create a list of length numPoints using range and loop over it, but never use the loop variable i. We created the list just so we would have something to loop over.

Exercises