$$ \newcommand{\Oof}[1]{\mathcal{O}(#1)} \newcommand{\F}{\boldsymbol{F}} \newcommand{\J}{\boldsymbol{J}} \newcommand{\x}{\boldsymbol{x}} \renewcommand{\c}{\boldsymbol{c}} $$




For loops

Many computations are repetitive by nature and programming languages have certain loop structures to deal with this. Here we will present what is referred to as a for loop (another kind of loop is a while loop, to be presented afterwards). Assume you want to calculate the square of each integer from 3 to 7. This could be done with the following two-line program.

for i in [3, 4, 5, 6, 7]:
    print i**2

Note the colon and indentation again!

What happens when Python interprets your code here? First of all, the word for is a reserved word signalling to Python that a for loop is wanted. Python then sticks to the rules covering such constructions and understands that, in the present example, the loop should run 5 successive times (i.e., 5 iterations should be done), letting the variable i take on the numbers \( 3, 4, 5, 6, 7 \) in turn. During each iteration, the statement inside the loop (i.e. print i**2) is carried out. After each iteration, i is automatically (behind the scene) updated. When the last number is reached, the last iteration is performed and the loop is finished. When executed, the program will therefore print out \( 9, 16, 25, 36 \) and \( 49 \). The variable i is often referred to as a loop index, and its name (here i) is a choice of the programmer.

Note that, had there been several statements within the loop, they would all be executed with the same value of i (before i changed in the next iteration). Make sure you understand how program execution flows here, it is important.

In Python, integer values specified for the loop variable are often produced by the built-in function range. The function range may be called in different ways, that either explicitly, or implicitly, specify the start, stop and step (i.e., change) of the loop variable. Generally, a call to range reads

range(start, stop, step)

This call makes range return the integers from (and including) start, up to (but excluding!) stop, in steps of step. Note here that stop-1 is that last integer included. With range, the previous example would rather read

for i in range(3, 8, 1):
    print i**2

By default, if range is called with only two parameters, these are taken to be start and stop, in which case a step of 1 is understood. If only a single parameter is used in the call to range, this parameter is taken to be stop. The default step of 1 is then used (combined with the starting at 0). Thus, calling range, for example, as


would return the integers 0, 1, 2, 3, 4, 5.

Note that decreasing integers may be produced by letting start > stop combined with a negative step. This makes it easy to, e.g., traverse arrays in either direction.

Let us modify ball_plot.py from the chapter A Python program with vectorization and plotting to illustrate how useful for loops are if you need to traverse arrays. In that example we computed the height of the ball at every milli-second during the first second of its (vertical) flight and plotted the height versus time.

Assume we want to find the maximum height during that time, how can we do it with a computer program? One alternative may be to compute all the thousand heights, store them in an array, and then run through the array to pick out the maximum. The program, named ball_max_height.py, may look as follows.

import matplotlib.pyplot as plt

v0 = 5                    # Initial velocity
g = 9.81                  # Acceleration of gravity
t = linspace(0, 1, 1000)  # 1000 points in time interval
y = v0*t - 0.5*g*t**2     # Generate all heights

# At this point, the array y with all the heights is ready.
# Now we need to find the largest value within y.

largest_height = y[0]          # Starting value for search
for i in range(1, 1000):
    if y[i] > largest_height:
        largest_height = y[i]

print "The largest height achieved was %f m" % (largest_height)

# We might also like to plot the path again just to compare
plt.xlabel('Time (s)')
plt.ylabel('Height (m)')

There is nothing new here, except the for loop construction, so let us look at it in more detail. As explained above, Python understands that a for loop is desired when it sees the word for. The range() function will produce integers from, and including, \( 1 \), up to, and including, \( 999 \), i.e. \( 1000 - 1 \). The value in y[0] is used as the preliminary largest height, so that, e.g., the very first check that is made is testing whether y[1] is larger than this height. If so, y[1] is stored as the largest height. The for loop then updates i to 2, and continues to check y[2], and so on. Each time we find a larger number, we store it. When finished, largest_height will contain the largest number from the array y. When you run the program, you get

The largest height achieved was 1.274210 m

which compares favorably to the plot that pops up.

To implement the traversing of arrays with loops and indices, is sometimes challenging to get right. You need to understand the start, stop and step length choices for an index, and also how the index should enter expressions inside the loop. At the same time, however, it is something that programmers do often, so it is important to develop the right skills on these matters.

Having one loop inside another, referred to as a double loop, is sometimes useful, e.g., when doing linear algebra. Say we want to find the maximum among the numbers stored in a \( 4 \times 4 \) matrix A. The code fragment could look like

largest_number = A[0][0]

for i in range(4):
    for j in range(4):
        if A[i][j] > largest_number:
            largest_number = A[i][j]

Here, all the j indices (0 - 3) will be covered for each value of index i. First, i stays fixed at i = 0, while j runs over all its indices. Then, i stays fixed at i = 1 while j runs over all its indices again, and so on. Sketch A on a piece of paper and follow the first few loop iterations by hand, then you will realize how the double loop construction works. Using two loops is just a special case of using multiple or nested loops, and utilizing more than two loops is just a straightforward extension of what was shown here. Note, however, that the loop index name in multiple loops must be unique to each of the nested loops. Note also that each nested loop may have as many code lines as desired, both before and after the next inner loop.

The vectorized computation of heights that we did in ball_plot.py (the chapter A Python program with vectorization and plotting) could alternatively have been done by traversing the time array (t) and, for each t element, computing the height according to the formula \( y = v_0t - \frac{1}{2}gt^2 \). However, it is important to know that vectorization goes much quicker. So when speed is important, vectorization is valuable.

Use loops to compute sums.

One important use of loops, is to calculate sums. As a simple example, assume some variable \( x \) given by the mathematical expression $$ \begin{equation*} x = \sum_{i=1}^{N}2\cdot i , \nonumber \end{equation*} $$ i.e., summing up the \( N \) first even numbers. For some given \( N \), say \( N = 5 \), \( x \) would typically be computed in a computer program as:

N = 5
x = 0
for i in range(1, N+1):
    x += 2*i
print x

Executing this code will print the number 30 to the screen. Note in particular how the accumulation variable x is initialized to zero. The value of x then gets updated with each iteration of the loop, and not until the loop is finished will x have the correct value. This way of building up the value is very common in programming, so make sure you understand it by simulating the code segment above by hand. It is a technique used with loops in any programming language.