2.1 Defining Functions
You have been composing code that calls Python functions since the beginning of this booksite. In this section, you will learn how to define and call your own functions. Functions support a key concept that will pervade your approach to programming from this point forward: Whenever you can clearly separate tasks within a computation, you should do so.
Using and Defining Functions
The effect of calling a Python function is easy to understand. For example, when you place math.sqrt(ab)
in a program, the effect is as if you had replaced that code with the return value that is produced by Python's math.sqrt()
function when passed the expression ab
as an argument. If you think about what the system has to do to create this effect, you will see that it involves changing a program's control flow.
You can define a function using a def
statement that specifies the function signature, followed by a sequence of statements that constitute the function. For example, harmonicf.py defines a function named harmonic()
that takes an argument n
and computes the n
th harmonic number (as described in Section 1.3). It also illustrates the typical structure of a Python program, having three components:
 A sequence of
import
statements  A sequence of function definitions
 Arbitrary global code, or the body of the program
Python executes the global code when we invoke the program by typing python harmonicf.py
on the command line; that global code calls the harmonic()
function defined earlier. (For purposes of illustration, we have made the userinteraction part of the program a bit more complicated than in Section 1.3.)
Control flow.
The diagram shown at the right illustrates the flow of control for the commandpython harmonicf.py 1 2 3
. First, Python processes the import
statements, thus making all of the features defined in the sys
and stdio
modules available to the program. Next, Python processes the definition of the harmonic()
function at lines 4 through 8, but does not execute the function — Python executes a function only when it is called. Then, Python executes the first statement in the global code after the function definition, the for
statement, which proceeds normally until Python begins to execute the statement value = harmonic(arg)
, starting by evaluating the expression harmonic(arg)
when arg
is 1. To do so it transfers control to the harmonic()
function — the flow of control passes to the code in the function definition. Python initializes the "parameter" variable n
to 1 and the "local" variable total
to 0.0 and then executes the for
loop within harmonic()
, which terminates after one iteration with total equal to 1.0. Then, Python executes the return
statement at the end of the definition of harmonic()
, causing the flow of control to jump back to the calling statement value = harmonic(arg)
, continuing from where it left off, but now with the expression harmonic(arg)
replaced by 1.0. Thus, Python assigns 1.0 to value
and writes it to standard output. Then, Python iterates the loop once more, and calls the harmonic()
function a second time with n
initialized to 2, which results in 1.5 being written. The process is then repeated a third time with arg
(and then n
) equal to 4, which results in 2.083333333333333 being written. Finally, the for loop terminates and the whole process is complete. As the diagram indicates, the simple code masks a rather intricate flow of control.
Informal function call/return trace.
One simple approach to following the control flow through function calls is to imagine that each function writes its name and argument(s) when it is called and its return value just before returning, with indentation added on calls and subtracted on returns. The result enhances the process of tracing a program by writing the values of its variables, which we have been using since Section 1.2. An informal trace for our example is shown at right.Basic terminology.
There are several concepts rolled up in the idea of a mathematical function and there are Python constructs corresponding to each, as summarized in this table:When we use a symbolic name in a formula that defines a mathematical function (such as f(x) = 1 + x + x^{2}), the symbol x is a placeholder for some input value that will be substituted into the formula to determine the output value. In Python, we use a parameter variable as a symbolic placeholder and we refer to a particular input value where the function is to be evaluated as an argument.
Function definition.
The first line of a function definition, known as its signature, gives a name to the function and to each parameter variable. The signature consists of the keyworddef
; the function name; a sequence of zero or more parameter variable names separated by commas and enclosed in parentheses; and a colon. The indented statements following the signature define the function body. The function body can consist of the kinds of statements that we discussed in Chapter 1. It also can contain a return statement, which transfers control back to the point where the function was called and returns the result of the computation or return value. The body may also define local variables, which are variables that are available only inside the function in which they are defined.
Function calls.
As we have seen throughout, a Python function call is nothing more than the function name followed by its arguments, separated by commas and enclosed in parentheses. Each argument can be an expression, which is evaluated and the resulting value passed as input to the function. When the function finishes, the return value takes the place of the function call as if it were the value of a variable (perhaps within an expression).Multiple arguments.
Like a mathematical function, a Python function can have more than one parameter variable, so it can be called with more than one argument.Multiple functions.
You can define as many functions as you want in a .py file. The functions are independent, except that they may refer to each other through calls. However, the definition of a function must appear before any global code that calls it. That is the reason that a typical Python program contains (1)import
statements, (2) function definitions, and (3) arbitrary global code, in that order.
Multiple return statements.
You can putreturn
statements in a function wherever you need them: control goes back to the calling program as soon as the first return
statement is reached.
Single return value.
A Python function provides only one return value to the caller (or, more precisely, it returns a reference to one object). This policy is not as restrictive as it might seem, because Python data types can contain more information than a single number, boolean, or string. For example, you will see later in this section that you can use arrays as return values.Scope.
The scope of a variable is the set of statements that can refer to that variable directly. The scope of a function's local and parameter variables is limited to that function; the scope of a variable defined in global code — known as a global variable — is limited to the.py
file containing that variable. Therefore, global code cannot refer to either a function's local or parameter variables. Nor can one function refer to either the local or parameter variables that are defined in another function. When a function defines a local (or parameter) variable with the same name as a global variable (such as i
in harmonicf.py), the variable name in the function refers to the local (or parameter) variable, not the global variable. While code in a function can refer to global variables, it should not do so: all communication from a caller to a function should take place via the function's parameter variables, and all communication from a function to its caller should take place via the function's return value.
Default arguments.
A Python function may designate an argument to be optional by specifying a default value for that argument. If you omit an optional argument in a function call, then Python substitutes the default value for that argument. We have already encountered a few examples of this feature. You can specify an optional argument with a default value in a userdefined function by putting an equals sign followed by the default value after the parameter variable in the function signature. You can specify more than one optional argument in a function signature, but all of the optional arguments must follow all of the mandatory arguments. Theharmonic()
function in the table shown below uses a default argument.
Side effects.
A pure function is a function that, given the same arguments, always return the same value, without producing any observable side effects, such as consuming input, producing output, or otherwise changing the state of the system. In computer programming it is also useful to define functions that do produce side effects. In fact, we often define functions whose only purpose is to produce side effects. An explicit return statement is optional in such a function: control returns to the caller after Python executes the function's last statement. Functions with no specified return value actually return the special valueNone
, which is usually ignored. The drawTriangle()
function in the table shown below has side effects, and does not return a value.
Type checking.
In mathematics, the definition of a function specifies both the domain and the range. For example, for the harmonic numbers, the domain is the positive integers and the range is the positive real numbers. In Python, we do not specify the types of the parameter variables or the type of the return value. As long as Python can apply all of the operations within a function, Python executes the function and returns a value. If Python cannot apply an operation to a given object because it is of the wrong type, it raises a runtime error to indicate the invalid type. This flexibility is a popular feature of Python (known as polymorphism) because it allows us to define a single function for use with objects of different types.The table below summarizes our discussion by providing examples of function definitions.
Implementing Mathematical Functions
We now consider two important functions that play an important role in science, engineering, and finance. The Gaussian (normal) distribution function is characterized by the familiar bellshaped curve and defined by the formula:
and the cumulative Gaussian distribution function Φ(z) is defined to be the area under the curve defined by φ(x) above the xaxis and to the left of the vertical line x = z. Functions to calculate φ and Φ are not available in Python's math
module, so we develop our own implementations.
Closed form.
In the simplest situation, we have a closedform mathematical formula defining our function in terms of functions that are implemented in Python'smath
module. This is the case for φ, so a function pdf()
corresponding to the mathematical definition is easy to implement. For convenience, gauss.py uses the default arguments μ = 0 and σ = 1 and actually computes φ(x, μ, σ) = φ((x  μ) / σ) / σ
No closed form.
If no formula is known, we may need a more complicated algorithm to compute function values. This situation is the case for Φ — no closedform expression exists for this function. A Taylor series approximation to the ratio of Φ and φ turns out to be an effective basis for evaluating the function:This formula readily translates to the Python code for the function cdf()
in gauss.py. For small (respectively large) z, the value is extremely close to 0 (respectively 1), so the code directly returns 0 (respectively 1); otherwise, it uses the Taylor series to add terms until the sum converges. Again, for convenience, gauss.py actually computes Φ(z, μ, σ) = Φ((z  μ) / σ), using the defaults μ = 0 and σ = 1.
Using Functions to Organize Code
With the ability to define functions, we can better organize our programs by defining functions within them when appropriate. For example, coupon.py is a version of couponcollector.py (from Section 1.4) that better separates the individual components of the computation:
 Given n, compute a random coupon value.
 Given n, do the coupon collection experiment.
 Get n from the command line, then compute and write the result.
Whenever you can clearly separate tasks within a computation, you should do so.
Passing Arguments and Returning Values
Next, we examine the specifics of Python's mechanisms for passing arguments to and returning values from functions.
Call by object reference.
You can use parameter variables anywhere in the body of the function in the same way as you use local variables. The only difference between a parameter variable and a local variable is that Python initializes the parameter variable with the corresponding argument provided by the calling code. We refer to this approach as call by object reference. One consequence of this approach is that if a parameter variable refers to a mutable object and you change that object's value within a function, then this also changes the object's value in the calling code (because it is the same object). Next, we explore the ramifications of this approach.Immutability and aliasing.
As discussed in Section 1.4, arrays are mutable data types, because we can change array elements. By contrast, a data type is immutable if it is not possible to change the value of an object of that type. The other data types that we have been using (int
, float
, str
, and bool
) are all immutable. In an immutable data type, operations that might seem to change a value actually result in the creation of a new object, as illustrated in the simple example at right. First, the statement i = 99
creates an integer 99, and assigns to i
a reference to that integer. Then j = i
assigns i
(an object reference) to j
, so both i
and j
reference the same object — the integer 99. Two variables that reference the same objects are said to be aliases. Next, j += 1
results in j
referencing an object with value 100, but it does not do so by changing the value of the existing integer from 99 to 100! Indeed, since int
objects are immutable, no statement can change the value of that existing integer. Instead, that statement creates a new integer 1, adds it to the integer 99 to create another new integer 100, and assigns to j
a reference to that integer. But i
still references the original 99. Note that the new integer 1 has no reference to it in the end — that is the system's concern, not ours.
Integers, floats, booleans, and strings as arguments.
Whenever you pass arguments to a function, the arguments and the function's parameter variables become aliases. In practice, this is the predominant use of aliasing in Python. For purposes of illustration, suppose that we need a function that increments an integer (our discussion applies to any more complicated function as well). A programmer new to Python might try this definition:
def inc(j): j += 1
and then expect to increment an integer i
with the call inc(i)
. Code like this would work in some programming languages, but it has no effect in Python, as shown in the figure at right.
To increment variable i
, we could use the definition
def inc(j): j += 1 return j
and call the function with the assignment statement i = inc(i)
.
The same holds true for any immutable type. A function cannot change the value of an integer, a float, a boolean, or a string.
Arrays as arguments.
When a function takes an array as an argument, it implements a function that operates on an arbitrary number of objects. For example, the following function computes the mean (average) of an array of floats or integers:
def mean(a): total = 0.0 for v in a: total += v return total / len(a)
Side effects with arrays.
Since arrays are mutable, it is often the case that the purpose of a function that takes an array as argument is to produce a side effect (such as changing the order of array elements). A prototypical example of such a function is one that exchanges the elements at two given indices in a given array. We can adapt the code that we examined at the beginning of Section 1.4:
def exchange(a, i, j): temp = a[i] a[i] = a[j] a[j] = temp
A formal trace of a call on this function is shown on the right.
A second prototypical example of a function that takes an array argument and produces side effects is one that randomly shuffles the elements in the array, using this version of the algorithm that we examined in Section 1.4 (and the exchange()
function just defined):
def shuffle(a): n = len(a) for i in range(n): r = random.randrange(i, n) exchange(a, i, r)
Arrays as return values.
A function can return an array. For example, consider the following function, which returns an array of random floats:
def randomarray(n): a = stdarray.create1D(n) for i in range(n): a[i] = random.random() return a
The table below concludes our discussion of arrays as function arguments by highlighting some typical arrayprocession functions.
Superposition of Sound Waves
Notes like concert A have a pure sound that is not very musical, because the sounds that you are accustomed to hearing have many other components. Most musical instruments produce harmonics (the same note in different octaves and not as loud), or you might play chords (multiple notes at the same time). To combine multiple sounds, we use superposition: simply add their waves together and rescale to make sure that all values stay between 1 and +1.
The program playthattunedeluxe.py is a version of playthattune.py (from Section 1.5) that encapsulates the sound wave calculation and adds harmonics. Try running playthattunedeluxe.py repeatedly with its standard input redirected to each of these data files (created by various students): elise.txt, ascale.txt, stairwaytoheaven.txt, entertainer.txt, firstcut.txt, freebird.txt, and looney.txt.
Q & A
Q. Can I use the statement return in a function without specifying a value?
A. Yes. Technically, it returns the None
object, which is the sole value of the type NoneType
.
Q. What happens if a function has one control flow that leads to a return
statement that returns a value but another control flow that reaches the end of the function body?
A. It would be poor style to define such a function, because doing so would place a severe burden on the function's callers: the callers would need to know under which circumstances the function returns a value, and under which circumstances it returns None
.
Q. What happens if I compose code in the body of a function that appears after the return
statement?
A. Once a return
statement is reached, control returns to the caller. So any code in the body of a function that appears after a return statement is useless; it is never executed. In Python, it is poor style, but not illegal to define such a function.
Q. What happens if I define two functions with the same name (but possibly a different number of arguments) in the same .py
file?
A. This is known as function overloading, which is embraced by many programming languages. Python, however, is not one of those languages: the second function definition will overwrite the first one. You can often achieve the same effect by using default arguments.
Q. What happens if I define two functions with the same name in different files?
A. That is fine. For example, it would be good design to have a function named pdf()
in gauss.py that computes the Gaussian probability density function and another function named pdf()
in cauchy.py
that computes the Cauchy probability density function. In Section 2.2 you will learn how to call functions defined in different .py
files.
Q. Can a function change the object to which a parameter variable is bound?
A. Yes, you can use a parameter variable on the left side of an assignment statement. However, many Python programmers consider it poor style to do so. Note that such an assignment statement has no effect in the client.
Q. The issue with side effects and mutable objects is complicated. Is it really all that important?
A. Yes. Properly controlling side effects is one of a programmer's most important tasks in large systems. Taking the time to be sure that you understand the difference between passing arrays (which are mutable) and passing integers, floats, booleans, and strings (which are immutable) will certainly be worthwhile. The very same mechanisms are used for all other types of data, as you will learn in Chapter 3.
Q. How can I arrange to pass an array to a function in such a way that the function cannot change the elements in the array?
A. There is no direct way to do so. In Section 3.3 you will see how to achieve the same effect by building a wrapper data type and passing an object of that type instead. You will also see how to use Python's builtin tuple
data type, which represents an immutable sequence of objects.
Q. Can I use a mutable object as a default value for an optional argument?
A. Yes, but it may lead to unexpected behavior. Python evaluates a default value only once, when the function is defined (not each time the function is called). So, if the body of a function modifies a default value, subsequent function calls will use the modified value. Similar difficulties arise if you initialize the default value by calling an impure function. For example, after Python executes the code fragment
def append(a=[], x=random.random()): a += [x] return a b = append() c = append()
b[]
and c[]
are aliases for the same array of length 2 (not 1), which contains one float repeated twice (instead of two different floats).
Exercises

Compose a function
max3()
that takes threeint
orfloat
arguments and returns the largest one.Solution:
def max3(a, b, c) max = a if b > max: max = b if c > max: max = c return max

Compose a function
odd()
that takes threebool
arguments and returnsTrue
if an odd number of arguments areTrue
, andFalse
otherwise. 
Compose a function
majority()
that takes threebool
arguments and returnsTrue
if at least two of the arguments areTrue
, andFalse
otherwise. Do not use anif
statement.Solution: Here are two solutions. The first is concise. The second is silly, but does adhere to the rules.
def majority(a, b, c): return (a and b) or (a and c) or (b and c) def majority(a, b, c): while a and b: return True while a and c: return True while b and c: return True return False

Compose a function
areTriangular()
that takes three numbers as arguments and returnsTrue
if they could be the sides of a triangle (none of them is greater than or equal to the sum of the other two), and False otherwise. 
Compose a function
sigmoid()
that takes afloat
argumentx
and returns thefloat
obtained from the formula: 1 / (1  e^{x}). 
Compose function
lg()
that takes an integern
as an argument and returns the base2 logarithm ofn
. You may use Python'smath
module. 
Compose a function
lg()
that takes an integern
as an argument and returns the largest integer not larger than the base2 logarithm ofn
. Do not use the standard Pythonmath
module. 
Compose a function
signum()
that takes afloat
argumentn
and returns 1 ifn
is less than 0, 0 ifn
is equal to 0, and +1 ifn
is greater than 0. Consider this function
duplicate()
:def duplicate(s): t = s + s
What does the following code fragment write?
s = 'Hello' s = duplicate(s) t = 'Bye' t = duplicate(duplicate(duplicate(t))) stdio.writeln(s + t)
Consider this function
cube()
:def cube(i): i = i * i * i
How many times is the following
while
loop iterated?i = 0 while i < 1000: cube(i) i += 1
Solution: Just 1000 times. A call to
cube()
has no effect on client code. It changes the value of its local parameter variablei
, but that change has no effect on thei
in thewhile
loop, which is a different variable. If you replace the call tocube(i)
with the statementi = i * i * i
(maybe that was what you were thinking), then the loop is iterated five times, withi
taking on the values 0, 1, 2, 9, and 730 at the beginning of the five iterations.
What does the following code fragment write?
for i in range(5): stdio.write(i) for j in range(5): stdio.write(i)
Solution: 0123444444. Note that the second call to
stdio.write()
usesi
, notj
. Unlike analogous loops in many other programming languages, when the first for loop terminates, the variablei
is 4 and it remains in scope. 
The following checksum formula is widely used by banks and credit card companies to validate legal account numbers:
d_{0} + f(d_{1}) + d_{2} + f(d_{3}) + d_{4} + f(d_{5}) + d_{6} + ... = 0 (mod 10) The d_{i} are the decimal digits of the account number and f(d) is the sum of the decimal digits of 2d (for example, f(7) = 5 because 2 × 7 = 14 and 1 + 4 = 5). For example, 17327 is valid because 1 + 5 + 3 + 4 + 7 = 20, which is a multiple of 10. Implement the function f and compose a program to take a 10digit integer as a commandline argument and print a valid 11digit number with the given integer as its first 10 digits and the checksum as the last digit.

Given two stars with angles of declination and right ascension (d1, a1) and (d2, a2), the angle they subtend is given by the Haversine formula:
2 arcsin((sin^{2}(d/2) + cos(d_{1}) cos(d_{2}) sin^{2}(a/2))^{1/2}) where a_{1} and a_{2} are angles between 180 and 180 degrees, d_{1} and d_{2} are angles between 90 and 90 degrees, a = a_{2}  a_{1}, d = d_{2}  d_{1}. Compose a program to take declination and right ascension of two stars as commandline arguments and write the angle they subtend. Hint: Be careful about converting from degrees to radians.
See the similar exercise from Section 1.2. Latitude corresponds to declination and longitude to ascension.

Compose a
Solution: The body of the function is virtually the same as for the corresponding function given in the table earlier in this page for twodimensional arrays of floats:readBoolean2D()
function that reads a twodimensional matrix of 0 and 1 values (with dimensions) into an array of booleans.def readBool2D(): m = stdio.readInt() n = stdio.readInt() a = stdarray.create2D(m, n, False) for i in range(m): for j in range(n): a[i][j] = stdio.readBool() return a

Compose a function that takes an array
a[]
of strictly positive floats as its argument and rescales the array so that each element is between 0 and 1 (by subtracting the minimum value from each element and then dividing each element by the difference between the minimum and maximum values). Use the builtinmax()
andmin()
functions. 
Compose a function
histogram()
that takes an arraya[]
of integers and an integerm
as arguments and returns an array of lengthm
whosei
th entry is the number of times the integeri
appears in the argument array. Assume that the values ina[]
are all between 0 andm
1, so that the sum of the values in the returned array should be equal tolen(a)
. 
Assemble code fragments in this section and in Section 1.4 to develop a program that takes an integer
n
from the command line and writesn
fivecard hands, separated by blank lines, drawn from a randomly shuffled card deck, one card per line using card names likeAce of Clubs
. 
Compose a function
multiply()
that takes two square matrices of the same dimension as arguments and returns their product (another square matrix of that same dimension). Extra credit: Make your program work whenever the number of rows in the first matrix is equal to the number of columns in the second matrix. 
Compose a function
any()
that takes an array of booleans as its argument and returnsTrue
if any of the entries in the array isTrue
, andFalse
otherwise. Compose a functionall()
that takes an array of booleans as its argument and returnsTrue
if all of the entries in the array areTrue
, andFalse
otherwise. Note thatall()
andany()
are Python builtin functions; the goal of this exercise is to understand them better by creating your own versions. 
Develop a version of
getCoupon()
that better models the situation when one of the coupons is rare: choose one value at random, return that value with probability (1/1000n), and return all other values with equal probability. Extra credit: How does this change affect the average value of the coupon collector function? 
Modify playthattune.py (from Section 1.5) to add harmonics two octaves away from each note, with half the weight of the oneoctave harmonics.
Creative Exercises

Birthday problem. Compose a program with appropriate functions for studying the birthday problem (see the related exercise in Section 1.4).

Euler's totient function. Euler's totient function is an important function in number theory: φ(n) is defined as the number of positive integers less than or equal to n that are relatively prime with n (no factors in common with n other than 1). Compose a function that takes an integer argument n and returns φ(n). Include global code that takes an integer from the command line, calls the function, and writes the result.

Harmonic numbers. Compose a program
harmonic.py
that defines three functionsharmonic()
,harmonicSmall()
, andharmonicLarge()
for computing the harmonic numbers. TheharmonicSmall()
function should just compute the sum (as in harmonic.py), theharmonicLarge()
function should use the approximation H_{n} = log_{e}(n) + γ + 1/(2n)  1/(12n^{2}) + 1/(120n^{4}) (the number γ = .577215664901532... is known as Euler's constant), and theharmonic()
function should callharmonicSmall()
for n < 100 andharmonicLarge()
otherwise. 
Gaussian random values. Experiment with the following functon for generating random variables from the Gaussian distribution, which is based on generating a random point in the unit circle and using a form of the BoxMuller transform. (See the "Gaussian random numbers" exercise at the end of Section 1.2.)
def gaussian(): r = 0.0 while (r >= 1.0) or (r == 0.0): x = random.uniform(1.0, 1.0) y = random.uniform(1.0, 1.0) r = x*x + y*y return x * math.sqrt(2.0 * math.log(r) / r)
Take a commandline argument
n
and generaten
random numbers, using an arraya[]
of 20 integers to count the numbers generated that fall betweeni*.05
and(i+1)*.05
fori
from 0 to 19. Then usestddraw
to plot the values and to compare your result with the normal bell curve. Remark: This approach is faster and more accurate than the one described in the "Gaussian random numbers" exercise in Section 1.2. Although it involves a loop, the loop is executed only 4/π (about 1.273) times on average. This reduces the overall expected number of calls to transcendental functions. 
Binary search. A general method that we study in detail in Section 4.2 is effective for computing the inverse of a cumulative probability density function like
cdf()
. Such functions are continuous and nondecreasing from (0, 0) to (1, 1). To find the value x_{0} for which f(x_{0}) = y_{0}, check the value of f(.5). If it is greater than y_{0}, then x_{0} must be between 0 and .5; otherwise, it must be between .5 and 1. Either way, we halve the length of the interval known to contain x_{0}. Iterating, we can compute x_{0} to within a given tolerance. Add a functioncfdInverse()
to gauss.py that uses binary search to compute the inverse.Solution: See gaussinv.py.
 BlackScholes option valuation. The Black Scholes formula supplies the theoretical value of a European call option on a stock that pays no dividends, given the current stock price s, the exercise price x, the continuously compounded riskfree interest rate r, the standard deviation σ of the stock's return (volatility) and the time (in years) to maturity t. The value is given by the formula
sΦ(a)  xe^{rt}φ(b),
where Φ(z) is the Gaussian cumulative distribution function,
a = (ln(s/x) + (r + σ^{2}/2)t)/(σt^{1/2}), and
b = a  σt^{1/2}.
Compose a program that takes
s
,x
,r
,sigma
, andt
from the command line and writes the BlackScholes value. For now, copy the definitions of thephi()
andPhi()
functions from gauss.py into your program. In the next section of the website, you'll learn how to define a function in one.py
file such that it can be called by the code in another.py
file.Myron Scholes won the 1997 Nobel Prize in Economics for the BlackScholes paper.
Solution: See blackscholes.py.

Implied volatility. Typically the volatility is the unknown value in the BlackScholes formula. Write a program that reads
s
,x
,r
,t
, and the current price of the option from the command line and uses binary search (see a previous exercise in this section) to compute σ. 
Horner's method. Compose a program with a function
evaluate(x, a)
that evaluates the polynomial a(x) whose coefficients are the elements in the arraya[]
:a_{0} + a_{1}x^{1} + a_{2}x^{2} + ... + a_{n2}x^{n2} + a_{n1}x^{n1} Use Horner's method, an efficient way to perform the computations that is suggested by the following parenthesization:
a_{0} + x (a_{1} + x( a_{2} + ... + x(a_{n2} + xa_{n1}))...) Then compose a function
exp()
that callsevaluate()
to compute an approximation to e^{x}, using the first n terms of the Taylor series expansion e^{x} = 1 + x + x^{2}/2! + x^{3}/3! + ... Take an argumentx
from the command line, and compare your result against that computed bymath.exp(x)
.Include code to check your answer against that computed by
math.exp()
.Solution: See horner.py.
 Benford's law. The American astronomer Simon Newcomb observed a quirk in a book that compiled logarithm tables: the beginning pages were much grubbier than the ending pages. He suspected that scientists performed more computations with numbers starting with 1 than with 8 or 9, and postulated the first digit law, which says that under general circumstances, the leading digit is much more likely to be 1 (roughly 30%) than the digit 9 (less than 4%). This phenomenon is known as Benford's law and is now often used as a statistical test. For example, IRS forensic accountants rely on it to discover tax fraud. Compose a program that reads in a sequence of integers from standard input and tabulates the number of times each of the digits 19 is the leading digit, breaking the computation into a set of appropriate functions. Use your program to test the law on some tables of information from your computer or from the web. Then, compose a program to foil the IRS by generating random amounts from $1.00 to $1,000.00 with the same distribution that you observed.
The file princetonfiles.txt is a list of file sizes on a public Unix machine at Princeton. Try running your program on that file.
Solution: See benford.py.

Binomial distribution. Compose a function
binomial()
that accepts an integern
, an integerk
, and a floatp
, and computes the probability of obtaining exactlyk
heads inn
biased coin flips (heads with probabilityp
) using the formulaf(k, n, p) = p^{k}(1  p)^{nk}n! / (k!(nk)!) Hint: To avoid computing with huge integers, compute x = ln f(k, n, p) and then return e^{x}. In the global code, take
n
andp
from the command line and check that the sum over all values ofk
between 0 andn
is (approximately) 1. Also, compare every value computed with the normal approximationf(k, n, p) ≈ Φ(k + 1/2, np, (np(1p)^{1/2})  Φ(k  1/2, np, (np(1p)^{1/2}) 
Coupon collecting from a binomial distribution. Compose a version of
getCoupon()
that usesbinomial()
from the previous exercise to return coupon values according to the binomial distribution with p = 1/2. Hint: Generate a uniformly distributed random number x between 0 and 1, then return the smallest value of k for which the sum of f(n, j, p) for all j < k exceeds x. Extra credit: Develop a hypothesis for describing the behavior of the coupon collector function under this assumption. 
Chords. Compose a version of playthattunedeluxe.py that can handle songs with chords (including harmonics). Develop an input format that allows you to specify different durations for each chord and different amplitude weights for each note within a chord. Create test files that exercise your program with various chords and harmonics, and create a version of Fur Elise that uses them.

Postal bar codes. The POSTNET barcode used by the U.S. Postal System to route mail is defined as follows: Each decimal digit in the zip code is encoded using a sequence of three halfheight and two fullheight bars. The barcode starts and ends with a fullheight bar (the guard rail) and includes a checksum digit (after the fivedigit zip code or ZIP+4), computed by summing up the original digits modulo 10. Implement the following functions:
 Draw a halfheight or fullheight bar on
stddraw
.  Given a digit, draw its sequence of bars.
 Compute the checksum digit.
and a test client that reads in a five (or nine) digit ZIP code as the commandline argument and draws the corresponding postal bar code.
Value 0 1 2 3 4 5 6 7 8 9 Encoding ╷╷╷
╷╷╷
╷╷╷
╷╷╷
╷╷╷
╷╷╷
╷╷╷
╷╷╷
╷╷╷
╷╷╷
 Draw a halfheight or fullheight bar on

Calendar. Compose a program that takes two commandline arguments
m
andy
and writes the monthly calendar for them
th month of yeary
, as in this example:February 2009 S M Tu W Th F S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
Hint: See leapyear.py and the "Day of the week" exercise in Section 1.2.
Solution: See calendar.py.

Fourier spikes. Compose a program that takes a commandline argument n and plots the function:
for 500 equally spaced samples of t from 10 to 10 (in radians). Run your program for n = 5 and n = 500. Note: You will observe that the sum converges to a spike (0 everywhere except a single value). This property is the basis for a proof that any smooth function can be expressed as a sum of sinusoids.(cos(t) + cos(2t) + cos(3t) + cos(4t) + ... + cos(nt)) / n