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 ifelse
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 ifelse
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 commandline 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:
The table below summarizes some typical situations where you might need to use a
power = 1 for i in range(n+1): stdio.writeln(str(i) + ' ' + str(power)) power *= 2
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 themath.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 commandline 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 whenfactor
*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 looptermination condition is satisfied, and execute some other sequence of statements. That is, we want to position the loopcontrol 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 looptermination 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 loopcontinuation condition is always satisfied, generate the random point (x, y) in the 2by2 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 fourspace 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 nonboolean 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 builtin 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 loopindex 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 loopcontrol variable after the loop terminates?
A. It is the last value of the loopcontrol variable during the loop. Upon termination of the for loop above, i
refers to the integer 109. Using the loopcontrol 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 Ctrlc
. That is, hold down the key labeled Ctrl
or control
and press the c
key. For Windows Command Prompt type Ctrlz
.
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 commandline 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^{2}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 commandline arguments, and writes
True
if both are strictly between 0 and 1 andFalse
otherwise. 
Improve your solution to the "wind chill" exercise from Section 1.2 by adding code to check that the values of the commandline 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 commandline argument. You may assume that the argument is less than 1000. Hint: consider using
i % 10
andi % 100
to determine whether to usest
,nd
,rd
, orth
for writing thei
th Hello. 
Compose a program that, using one
for
loop and oneif
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 commandline argument, usesrandom.random()
to writen
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^{2}, and n^{3} for n = 2, 4, 8, ..., 2048. Use tabs (
'\t'
characters) to line up columns. 
What are
m
andn
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): stdio.writeln(f) f = f + g g = f  g
Solution: Run the program fibonacci.py.

Compose a program that takes a commandline argument
n
and writes all the positive powers of 2 less than or equal ton
. Make sure that your program works properly for all values ofn
. (Your program should write nothing ifn
is negative.) 
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 offor
loops. 
Unlike the harmonic numbers, the sum 1/1^{2} + 1/2^{2} + ... + 1/n^{2} does converge to a constant as n grows to infinity. (Indeed, the constant is π^{2}/6, so this formula can be used to estimate the value of π.) Which of the following
for
loops computes this sum? Assume thatn
is the integer 1000000 andtotal
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.0 / (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 xaxis 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 commandline arguments and writes the kth root of n (Hint: See the previous exercise.)

Modify binary.py to create a program that takes
i
andk
as commandline arguments and convertsi
to basek
. Assume thatk
is an integer between 2 and 16. For bases greater than 10, use the lettersA
throughF
to represent the 11th through 16th digits, respectively. 
Compose a program named that accepts an integer commandline argument
n
, places the binary representation ofn
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 nestedfor
loops instead of awhile
loop inside afor
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 commandline 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 commandline 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
i <= n
instead ofi*i <= 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 commandline argument
n
and writes a two dimensionaln
byn
checker board pattern with alternating spaces and asterisks, like the following 4by4 pattern.* * * * * * * * * * * * * * * *

Compose a program that accepts two integers
x
andy
from the commandline, and finds and writes the greatest common divisor (gcd) ofx
andy
using Euclid's algorithm, which is an iterative computation based on the following observation: ifx > y
, then ify
dividesx
, the gcd ofx
andy
isy
; otherwise the gcd ofx
andy
is the same as the gcd ofx % y
andy
. 
Compose a program that takes one commandline argument
n
and writes ann
byn
table such that there is an*
in rowi
and columnj
if the gcd ofi
andj
is 1 (i
andj
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 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^{2}  y^{2}), b to 2 sqrt(1  x^{2}  y^{2}), and c to 1  2 (x^{2} + y^{2}).
Solution: See functiongrowth.py.
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 ton
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^{3} + b^{3} = c^{3} + d^{3}. Use four nestedfor
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 d_{1} + 2d_{2} + 3d_{3} + ... + 10d_{10} must be a multiple of 11 (here d_{i} denotes the ith digit from the right). The checksum digit d_{1} 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_{1} between 0 and and 10 for which d_{1} + 2*2 + 3*5 + 4*4 + 5*1 + 6*3 + 7*1 + 8*0 + 9*2 + 10*0 is a multiple of 11. Compose a program that takes a 9digit integer as a commandline argument, computes the checksum, and writes the 10digit 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 commandline argument
n
and writes the number of primes less thann
. 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 commandline argument
n
and estimates how long it will take a random walker to hit the boundary of a 2n
by2n
square centered at the starting point. 
Medianof5. 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}/2! + x^{3}/3! + ... tototal
. 
Experimental analysis. Run experiments to determine the relative costs of
Math.exp()
and the following three methods from Exercise 2.3.36 for the problem of computing e^{x}: the direct method with nestedfor
loops, the improved method with a singlefor
loop, and the latter with the termination condition(term > 0)
. For each method, use trialanderror with a command line argument to determine how many times your computer can perform the computation in 10 seconds. Trigometric functions. Compose programs that compute sin x and cos x using the Taylor series expansions:
sin x = x  x^{3}/3! + x^{5}/5!  x^{7}/7! + ...
cos x = 1  x^{2}/2! + x^{4}/4!  x^{6}/6! + ...Partial solution: See sine.py.

Pepys's problem. In 1693 Samuel Pepys asked Isaac Newton which is more likely: getting 1 at least once when rolling a fair die six times or getting 1 at least twice when rolling it 12 times. Compose a program that could have provided Newton with a quick answer.

Game simulation. In the 1970s game show Let's Make a Deal, a contestant is presented with three doors. Behind one of them is a valuable prize. After the contestant chooses a door, the host opens one of the other two doors (never revealing the prize, of course). The contestant is then given the opportunity to switch to the other unopened door. Should the contestant do so? Intuitively, it might seem that the contestant's initial choice door and the other unopened door are equally likely to contain the prize, so there would be no incentive to switch. Compose a program to test this intuition by simulation. Your program should take a commandline argument
n
, play the gamen
times using each of the two strategies (switch or do not switch), and write the chance of success for each of the two strategies. Or you can play the game here.Solution: See montehall.py.

Chaos. Compose a program to study the following simple model for population growth, which might be applied to study fish in a pond, bacteria in a test tube, or any of a host of similar situations. We suppose that the population ranges from 0 (extinct) to 1 (maximum population that can be sustained). If the population at time t is x, then we suppose the population at time t + 1 to be rx(1x), where the parameter r, known as the fecundity parameter, controls the rate of growth. Start with a small population — say, x = 0.01 — and study the result of iterating the model, for various values of r. For which values of r does the population stabilize at x = 1  1/r ? Can you say anything about the population when r is 3.5? 3.8? 5?
Biologists model population growth of fish in a pond using the logistic equation. Investigate some of its chaotic behavior.

Euler's sumofpowers conjecture. In 1769 Leonhard Euler formulated a generalized version of Fermat's Last Theorem, conjecturing that at least n nth powers are needed to obtain a sum that is itself an nth power, for n > 2. Compose a program to disprove Euler's conjecture (which stood until 1967), using a quintuply nested loop to find four positive integers whose 5th power sums to the 5th power of another positive integer. That is, find five integers a, b, c, d, and e such that a^{5} + b^{5} + c^{5} + d^{5} = e^{5}.

Dragon curves. This exercise is a generalization of the "dragon curves" exercise from Section 1.2. Compose a program that takes an integer commandline argument
n
and writes the instructions for drawing a dragon curve of ordern
.Solution: See dragon2.py.
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} / 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 twoloop 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 another for
loop:
The number of times the
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
loop iterates depends on the relative values of the next term and the accumulated sum. Once total
stops changing, we leave the loop. (This strategy is more efficient than using the termination condition (term > 0)
because it avoids a significant number of iterations that do not change the value of the total.) This code is effective, but it is inefficient because the inner for
loop recomputes all the values it computed on the previous iteration of the outer for
loop. Instead, we can make use of the term that was added in on the previous loop iteration and solve the problem with a single while
loop:
term = 1.0 total = 0.0 n = 1 while total != total + term: total += term term *= x/n n += 1