1.3 Conditionals and Loops

We use the term flow of control to refer to the sequence of statements that are executed in a program. All of the programs that we have examined to this point have a simple flow of control: the statements are executed one after the other in the order given. Most programs have a more complicated structure where statements may or may not be executed depending on certain conditions (conditionals), or where groups of statements are executed multiple times (loops).

`if` Statements

Most computations require different actions for different inputs. Program flip.py uses an if-else statement to write the results of a coin flip. The table below summarizes some typical situations where you might need to use an if or if-else statement.

Note that in Python indentation is meaningful. For example, consider these two code fragments:

if x >= 0:                      if x >= 0:
    stdio.write('not ')             stdio.write('not ')
stdio.writeln('negative')           stdio.writeln('negative')

If x is greater than or equal to 0, then both fragments write 'not negative'. If x is less than 0, then the code on the left writes 'negative' but the code on the right writes nothing at all.

`while` Statements

Many computations are inherently repetitive. The while statement enables us to perform a group of statements many times. This enables us to express lengthy computations without composing lots of code. The program tenhellos.py writes "Hello, World" ten times. The program powersoftwo.py accepts a command-line argument n and writes all of the powers of 2 less than or equal to n.

Incidentally, in Python we can abbreviate an assignment statement of the form i = i + 1 with the shorthand notation i += 1. The same notation works for other binary operators, including -, *, and /. For example, most programmers would use power *= 2 instead of power = 2 * power in powersoftwo.py.

`for` Statements

Many loops follow the same basic scheme: initialize an index variable to some value and then use a while loop to test an exit condition involving the index variable, using the last statement in the while loop to modify the index variable. Python's for statement is a direct way to express such loops. For example, the following two lines of code are equivalent to the corresponding lines of code in tenhellos.py:

for i in range(4, 11):
    stdio.writeln(str(i) + 'th Hello')

If range() has only one argument, then the start value of the range value defaults to 0. For example, the following for loop is an improvement over the while loop in powersoftwo.py:

power = 1
for i in range(n+1):
    stdio.writeln(str(i) + ' ' + str(power))
    power *= 2

The table below summarizes some typical situations where you might need to use a while or for statement.

Nesting

We can nest if, while, or for statements within other if, while, or for statements. As an example, divisorpattern.py has a for loop whose nested statements are a for loop (whose nested statement is an if statement) and a stdio.writeln() statement.

As a second example of nesting, consider a tax preparation program that contains this code:

if income < 0.0:
    rate = 0.00
else:
    if income < 8925:
        rate = 0.10
    else:
        if income < 36250:
            rate = 0.15
        else:
            if income < 87850:
               rate = 0.25
            ...

Python allows an if statement to contain elif ("else if") clauses. Using elif clauses yields this more compact code:

if   income < 0:      rate = 0.00
elif income < 8925:   rate = 0.10
elif income < 36250:  rate = 0.15
elif income < 87850:  rate = 0.23
elif income < 183250: rate = 0.28
elif income < 398350: rate = 0.33
elif income < 400000: rate = 0.35
else:                 rate = 0.396

Applications

The ability to program with conditionals and loops immediately opens up the world of computation to us.

Finite sum.

The computational paradigm used by powersoftwo.py is one that you will use frequently. It uses two variables — one as an index that controls a loop and the other to accumulate a computational result. The program harmonic.py uses the same paradigm to evaluate the finite sum H_n = 1 + 1/2 + 1/3 + ... + 1/n. These numbers are known as the harmonic numbers.

Computing the square root.

How is the math.sqrt() function implemented? The program sqrt.py illustrates one technique. It uses a special case of a general computational technique that was developed by Isaac Newton and Joseph Raphson and is widely known as Newton's method. To compute the square root of a positive number t, start with the estimate t = c. If t is equal to c / t, then t is equal to the square root of c, so the computation is complete. If not, refine the estimate by replacing t with the average of t and c / t. Each time we perform this update, we get closer to the desired answer.

Number conversion.

The program binary.py writes the binary (base 2) representation of the decimal number typed as the command line argument. It is based on decomposing the number into a sum of powers of two. For example, the binary representation of 106 is 1101010, which is the same as saying that 106 = 64 + 32 + 8 + 2, or in binary, 1101010 = 1000000 + 100000 + 1000 + 10. To compute the binary representation of n, we consider the powers of 2 less than or equal to n in decreasing order to determine which belong in the binary decomposition (and therefore correspond to a 1 bit in the binary representation).

Monte Carlo simulation.

Our next example is representative of a widely used class of programs, where we use computers to simulate what might happen in the real world, so that we can make informed decisions in all kinds of complicated situations. Suppose a gambler makes a series of fair $1 bets, starting with $50, and continue to play until she either goes broke or has $250. What are the chances that she will go home with $250, and how many bets might she expect to make before winning or losing? Program gambler.py is a simulation that can help answer these questions. It accepts three command-line arguments, the initial stake ($50), the goal amount ($250), and the number of times we want to simulate the game.

Factoring.

A prime is an integer greater than 1 whose only positive divisors are 1 and itself. The prime factorization of an integer is the multiset of primes whose product is the integer. For example, 3757208 = 2*2*2*7*13*13*397. The factors.py program computes the prime factorization of any given positive integer. We can stop looking for factors when factor*factor is greater than n because if an integer n has a factor, it has one less than or equal to the square root of n.

Loop and a Half

Suppose we want a loop that repeatedly does the following: execute some sequence of statements, exit the loop if some loop-termination condition is satisfied, and execute some other sequence of statements. That is, we want to position the loop-control condition in the middle of the loop, not at the beginning. This is known as a loop and a half because you must go partway through the loop before reaching the loop-termination test. Python provides the break statement for this purpose. When Python executes a break statement, it immediately exits the (innermost) loop.

For example, consider the problem of generating a point that is randomly distributed in the unit disk. Since we always want to generate at least one point, we compose a while loop whose loop-continuation condition is always satisfied, generate the random point (x, y) in the 2-by-2 square, and use a break statement to terminate the loop if (x, y) is in the unit disk.

while True:
    x = -1.0 + 2.0*random.random()
    y = -1.0 + 2.0*random.random()
    if x*x + y*y <= 1.0:
        break

Q & A

Q. What is the difference between = and ==?

A. We repeat this question here to remind you that you should not use = when you really mean == in a conditional expression. The statement x = y assigns y to x, whereas the expression x == y tests whether the two variables currently are equal. In some programming languages, this difference can wreak havoc in a program and be difficult to detect. In Python, assignment statements are not expressions. For example, if we were to make the mistake of typing cash = goal instead of cash == goal in gambler.py, the compiler would find the bug for us:

% python gambler.py 10 20 1000
File "gambler.py", line 21
  if cash = goal:
          ^
SyntaxError: invalid syntax

Q. What happens if I leave out the colon in an if, while, or for statement?

A. Python raises a SyntaxError at compile time.

Q. What are the rules for indenting statement blocks?

A. Each statement in a block must have the same indentation; if it does not, Python will raise an IndentationError at compile time. Python programmers commonly use a four-space indentation scheme, which we follow throughout this book.

Q. Should I use tab characters to indent my code?

A. No, you should avoid placing tab characters in your .py files. Many editors, however, offer the option of automatically placing a sequence of spaces into your program when you type the <Tab> key; it's appropriate to use that option when composing Python programs.

Q. Can I spread a long statement over multiple lines?

A. Yes, but some care is needed because of the way Python treats indentation. If the expression that spans multiple lines is enclosed inside parentheses (or square brackets or curly braces), then there is no need to do anything special. For example, this is a single statement that is spread over three lines:

stdio.write(a0 + a1 + a2 + a3 +
            a4 + a5 + a6 + a7 +
            a8 + a9)

However, if there is no implied line continuation, you must use the backslash character at the end of each line to be continued.

total = a0 + a1 + a2 + a3 + \
        a4 + a5 + a6 + a7 + \
        a8 + a9

Q. Suppose I want to skip over some of code in a loop in some cases, or suppose that I want the body of a conditional statement to be empty, so that no statement is executed. Does Python have language support for such things?

A. Yes, Python provides the continue and pass statements, respectively, for these conditions. However, situations in which they are really necessary are rare, and we do not use them in this booksite. Also, there is no switch statement in Python (for mutually exclusive alternatives), though one is commonly found in other languages, and no goto statement (for unstructured control flow).

Q. Can I use a non-boolean expression in an if or while statement?

A. Yes, but this is probably not a good idea. Expressions that evaluate to zero or the empty string are considered False; all other numeric and string expressions are considered True.

Q. Are there cases where I must use a for statement but not a while statement, or vice versa?

A. You can use a while statement to implement any kind of loop, but, as defined here, you can use a for statement only for the kind of loop that iterates over a finite sequence of integers. Later (Sections 1.4, 3.3, and 4.4), we will consider other ways to use the for statement.

Q. Can I use the built-in range() function to create a sequence of integers with a step size of some value other than 1?

A. Yes, range() supports an optional third argument step, which defaults to 1. That is, range(start, stop, step) produces the sequence of integers start, start + step, start + 2 * step, and so forth. If step is a positive integer, the sequence continues as long as start + i * step is less than stop; if step is a negative integer, the sequence continues as long as start + i * step is greater than stop. For example, range(0, -100, -1) returns the integer sequence 0, -1, -2, ..., -99.

Q. Can I use floats as arguments to range()?

A. No, all arguments must be integers.

Q. Can I change the loop-index variable within a for loop?

A. Yes, but it will not affect the sequence of integers produced by range(). For example, the following loop writes the 100 integers from 0 to 99:

for i in range(100):
    stdio.writeln(i)
    i += 10

Q. In a for loop, what is the value of the loop-control variable after the loop terminates?

A. It is the last value of the loop-control variable during the loop. Upon termination of the for loop above, i refers to the integer 109. Using the loop-control variable after the termination of a for loop is generally considered poor style, so we do not do so in any of our programs.

Q. My program is stuck in an infinite loop. How do I stop it?

A. Type Ctrl-c. That is, hold down the key labeled Ctrl or control and press the c key. For Windows Command Prompt type Ctrl-z.

Q. Is there an example for when the following for and while loops are not equivalent?

for variable in range(start, stop):
    statement1
    statement2
    ...

variable = start
while variable < stop:
    statement1
    statement2
    ...
    variable += 1

A. Yes. Hint: Use a continue statement.

Exercises

Compose a program that takes three integer command-line arguments and writes 'equal' if all three are equal, and 'not equal' otherwise.
Compose a more general and robust version of quadratic.py (from Section 1.2) that writes the roots of the polynomial ax²bx + c, writes an appropriate error message if the discriminant is negative, and behaves appropriately (avoiding division by zero) if a is zero.
Write a code fragment that takes two float command-line arguments, and writes True if both are strictly between 0 and 1 and False otherwise.
Improve your solution to the "wind chill" exercise from Section 1.2 by adding code to check that the values of the command-line arguments fall within the ranges of validity of the formula, and also adding code to write an error message if that is not the case.

What is the value of j after each of the following code fragments is executed?

a. j = 0
   for i in range(0, 10):
       j += i

b. j = 1
   for i in range(0, 10):
       j += j

c. for j in range(0, 10):
       j += j

Redesign tenhellos.py to compose a program that accepts the number of lines to write as a command-line argument. You may assume that the argument is less than 1000. Hint: consider using i % 10 and i % 100 to determine whether to use st, nd, rd, or th for writing the ith Hello.
Compose a program that, using one for loop and one if statement, writes the integers from 1000 (inclusive) to 2000 (exclusive) with five integers per line. Hint: use the % operator.

Solution: See fiveperline.py.
Generalizing the "uniform random numbers" exercise from Section 1.2, compose a program that accepts an integer n as a command-line argument, uses random.random() to write n uniform random numbers between 0 and 1, and then writes their average value, their minimum value, and their maximum value.
Describe what happens when you invoke rulern.py with an argument that is too large. For example, try executing the command python rulern 100.
Compose a program that writes a table of the values of log n, n, n log n, n², and n³ for n = 2, 4, 8, 16, 32, 64, 128. Use tabs ('\t' characters) to line up columns.

Solution: See functiongrowth.py.

What are m and n after the following code is executed?
n = 123456789 m = 0 while n != 0: m = (10 * m) + (n % 10) n //= 10
Solution: Run the program digitreverser.py.

What does this code write?

f = 0
g = 1
for i in range(0, 16):
    f = f + g
    g = f - g
    stdio.writeln(f)

Solution: Run the program fibonacci.py.

Compose a program that takes a command-line argument n and writes all the positive powers of 2 less than or equal to n. Make sure that your program works properly for all values of n. (Your program should write nothing if n is negative or zero.)
Expand your solution to the "Continuously compounded interest" exercise from Secction 1.2 to write a table giving the total amount paid and the remaining principal after each monthly payment.
Compose a version of divisorpattern.py that uses while loops instead of for loops.

Unlike the harmonic numbers, the sum 1/1² + 1/2² + ... + 1/n² does converge to a constant as n grows to infinity. (Indeed, the constant is π²/6, so this formula can be used to estimate the value of π.) Which of the following for loops computes this sum? Assume that n is the integer 1000000 and total is a float initialized to 0.0.

a. for i in range(1, n+1):
       total += 1 / (i*i)

b. for i in range(1, n+1):
       total += 1.0 / i*i

c. for i in range(1, n+1):
       total += 1.0 / (i*i)

d. for i in range(1, n+1):
       total += 1 / (1.0*i*i)

Show that sqrt.py implements Newton's method for finding the square root of c. Hint: Use the fact that the slope of the tangent to a (differentiable) function f(x) at x = t is f'(t) to find the equation of the tangent line and then use that equation to find the point where the tangent line intersects the x-axis to show that you can use Newton's method to find a root of any function as follows: at each iteration, replace the estimate t by t - f(t) / f'(t).
Using Newton's method, develop a program that takes integers n and k as command-line arguments and writes the kth root of n (Hint: See the previous exercise.)
Modify binary.py to create a program that takes i and k as command-line arguments and converts i to base k. Assume that k is an integer between 2 and 16. For bases greater than 10, use the letters A through F to represent the 11th through 16th digits, respectively.
Compose a program named that accepts a positive integer command-line argument n, places the binary representation of n into a string, and then writes the string.

Solution: See binary2.py.
Compose a version of gambler.py that uses two nested while loops or two nested for loops instead of a while loop inside a for loop.
Write a program that traces a gambler's ruin simulation by writing a line after each bet that has one asterisk corresponding to each dollar held by the gambler.
Modify gambler.py to take an extra command-line argument that specifies the (fixed) probability that the gambler wins each bet. Use your program to try to learn how this probability affects the chance of winning and the expected number of bets. Try a value of p close to 0.5 (say, 0.48).
Modify gambler.py to take an extra command-line argument that specifies the number of bets the gambler is willing to make, so that there are three possible ways for the game to end: the gambler wins, loses, or runs out of time. Add to the output to give the expected amount of money the gambler will have when the game ends. Extra credit: Use your program to plan your next trip to Monte Carlo.
Modify factors.py to write just one copy of each of the prime divisors.
Run quick experiments to determine the impact of using the termination condition factor <= n instead of factor*factor <= n in factors.py. For each method, find the largest n such that when you type in an n digit number, the program is sure to finish within 10 seconds.
Compose a program that takes one integer command-line argument n and writes a two dimensional n-by-n checker board pattern with alternating spaces and asterisks, like the following 4-by-4 pattern.
```
* * * *
 * * * *
* * * *
 * * * *
```
Compose a program that accepts two integers x and y from the command-line, and finds and writes the greatest common divisor (gcd) of x and y using Euclid's algorithm, which is an iterative computation based on the following observation: if x > y, then if y divides x, the gcd of x and y is y; otherwise the gcd of x and y is the same as the gcd of x % y and y.
Compose a program that takes one command-line argument n and writes an n-by-n table such that there is an * in row i and column j if the gcd of i and j is 1 (i and j are relatively prime), and a space in that position otherwise.
Compose a program that generates a point that is randomly distributed in the unit disk, but without using a break statement. Compare your solution to the one given at the end of this section.
Compose a program that writes the coordinates of a random point (a, b, c) on the surface of a unit sphere. To generate such a point, use Marsaglia's method: Start by picking a random point (x, y) in the unit disk using the method described at the end of this section. Then, set a to 2 x sqrt(1 - x² - y²), b to 2 y sqrt(1 - x² - y²), and c to 1 - 2 (x² + y²).

Creative Exercises

Ramanujan's taxi. S. Ramanujan was an Indian mathematician who became famous for his intuition for numbers. When the English mathematician G. H. Hardy came to visit him in the hospital one day, Hardy remarked that the number of his taxi was 1729, a rather dull number. To which Ramanujan replied, "No, Hardy! No, Hardy! It is a very interesting number. It is the smallest number expressible as the sum of two cubes in two different ways." Verify this claim by composing a program that takes a command line argument n and writes all integers less than or equal to n that can be expressed as the sum of two cubes in two different ways. In other words, find distinct positive integers a, b, c, and d such that a³ + b³ = c³ + d³. Use four nested for loops.

Solution: See ramanujanwhile.py and ramanujanfor.py.

Now, the license plate 87539319 seems like a rather dull number. Determine why it's not.
Checksums. The International Standard Book Number (ISBN) is a 10 digit code that uniquely specifies a book. The rightmost digit is a checksum digit which can be uniquely determined from the other 9 digits from the condition that 10d₁₀ + 9d₉ + ... + 2d₂ + d₁ must be a multiple of 11 (here d_i denotes the ith digit from the right). The checksum digit d₁ can be any value from 0 to 10: the ISBN convention is to use the value 'X' to denote 10. Example: the checksum digit corresponding to 020131452 is 5 since is the only value of d₁ between 0 and and 10 for which 10*0 + 9*2 + 8*0 + 7*1 + 6*3 + 5*1 + 4*4 + 3*5 + 2*2 + d₁ is a multiple of 11. Compose a program that takes a 9-digit integer as a command-line argument, computes the checksum, and writes the 10-digit ISBN number. It's OK if the program doesn't write any leading 0's.

Solution: See isbn.py.
Counting primes. Compose a program that takes a command-line argument n and writes the number of primes less than n. Use it to write the number of primes less than 10 million. Note: if you are not careful to make your program efficient, it may not finish in a reasonable amount of time. Later in Section 1.4, you will learn about a more efficient way to perform this computation called the Sieve of Eratosthenes.
2D random walk. A two dimensional random walk simulates the behavior of a particle moving in a grid of points. At each step, the random walker moves north, south, east, or west with probability 1/4, independently of previous moves. Compose a program that takes a command-line argument n and estimates how long it will take a random walker to hit the boundary of a 2n+1-by-2n+1 square centered at the starting point.
Median-of-5. Compose a program that takes five distinct integers from the command line and writes the median value (the value such that two of the other integers are smaller and two are larger). Extra credit: Solve the problem with a program that compares values fewer than seven times for any given input.
Exponential function. Assume that x is a float. Compose a code fragment that uses the Taylor series expansion to assign e^x = 1 + x + x²/2! + x³/3! + ... to total.

Solution: The purpose of this exercise is to get you to think about how a library function like math.exp() might be implemented in terms of elementary operators. Try solving it, then compare your solution with the one developed here. We start by considering the problem of computing one term. Suppose that x is a float and n is an integer. The following code assigns xⁿ / n! to term using the direct method of having one loop for the numerator and another loop for the denominator, then dividing the results:

num = 1.0
den = 1.0
for i in range(1, n+1):
    num *= x
for i in range(1, n+1):
    den *= i
term = num / den

A better approach is to use just a single for loop:

term = 1.0
for i in range(1, n+1):
    term *= x / i

Besides being more compact and elegant, the latter solution is preferable because it avoids inaccuracies caused by computing with huge numbers. For example, the two-loop approach breaks down for values like x = 10 and n = 100 because 100! is too large to represent accurately as a float.

To compute e^x, we nest this for loop within a while loop:

term = 1.0
total = 0.0
n = 1
while total != total + term:
    total += term
    term = 1.0
    for i in range(1, n+1):
        term *= x / i
    n += 1

while

total

(term > 0)

for