Fast Exponentiation. This is the fastest way to raise a number to an integer power.
It requires the fewest multiplies, and does not use
logarithms.

Procedure 9.1. Fast Exponentiation of integers, raises
n to the p power

Base Case. If p = 0, return 1.0.

Odd. If p is odd, return
n × fastExp
(n, p−1
).

Even. If p is even, compute
t ← fastExp
(n, p÷2 );
return t × t.

Greatest Common
Divisor. The greatest common divisor is the largest number which will
evenly divide two other numbers. You use this when you reduce
fractions. See Greatest Common Divisor in
for an alternate example of this exercise's algorithm. This version
can be slightly faster than the loop we looked at earlier.

Procedure 9.2. Greatest Common Divisor of two integers,
p and q

Base Case. If p = q, return
p.

Swap. If p < q,
return GCD (q,
p).

Subtract. If p > q,
return GCD (p,
p−q).

Factorial Function. Factorial of a number n is the number of
possible arrangements of 0 through n things. It
is computed as the product of the numbers 1 through
n. That is, 1×2×3×...×n.
We touched on this in Computing e
in the section called “Iteration Exercises”. This function
defintion can simplify the program we wrote for that
exercise.

Procedure 9.3. Factorial of an integer, n

Base Case. If n = 0, return 1.

Multiply. If n > 0, return
n × factorial
(n−1).

Fibonacci Series. Fibonacci numbers have a number of interesting mathematical
properties. The ratio of adjacent Fibonacci numbers approximates the
golden ratio ((1+ √5)/2, about 1.618), used widely in art and
architecture.

Procedure 9.4. The nth Fibonacci Number,
F_{n}

F_{0}
Case. If n = 0, return 0.

F_{1}
Case. If n = 1, return 1.

F_{n} =
F_{n−1} and
F_{n−2}. If n > 2, return
fibonacci (n−1) +
fibonacci
(n−2).

Ackermann's Function. An especially complex algorithm that computes some really big
results. This is a function which is specifically designed to be
complex. It cannot easily be rewritten as a simple loop. Further, it
produces extremely large results because it describes extremely
large exponents.

Procedure 9.5. Ackermann's Function of two numbers, m
and n

Base Case. If m = 0, return
n+1.

N Zero Case. If m ≠ 0 and n =
0, return ackerman (m−1,
1).

N Non-Zero Case. If m ≠ 0 and n ≠
0, return ackerman (m−1,
ackerman (m,
n−1)).

Compute the Maximum Value of Some Function. Given some integer-valued function
f(x), we want to know what
value of x has the largest value for
f(x) in some interval of
values. For additional insight, see
[Dijkstra76].

Imagine we have an integer function of an integer, call it
f(x). Here are some examples
of this kind of function.

def f1(x): return x

def f2(x): return -5/3*x-3

def f3(x): return -5*x*x+2*x-3

The question we want to answer is what value of
x in some fixed interval returns the largest
value for the given function? In the case of the first example,
def f1(x): return x, the largest value of
f1(x) in the interval 0 ≤
x < 10 occurs when x is
9. What about f3(x) in the
range (-10 ≤ x ≤ 10)

Procedure 9.6. Max of a Function in the interval low to
high

Initialize

x ←
low

max ←
x

maxFx ←
f(max)

Loop. While low ≤ x
< high.

New Max? If f(x) >
maxFx, then

max ←
x

maxFx ←
f(max)

Next X. Increment x by 1.

Return. Return x as the value at which
f(x) had the largest
value.

Integration Approximation. This is a simple rectangular rule for finding the area under a
curve which is continuous on some closed interval.

We will define some function which we will integrate, call it
f (x). Here are some
examples.

def f1(x): return x*x

def f2(x): return 0.5 * x * x

def f3(x): return exp( x )

def f4(x): return 5 * sin( x )

When we specify
y=f(x),
we are specifying two dimensions. The y is given
by the function's values. The x dimension is
given by some interval. If you draw the function's curve, you put two
limits on the x axis, this is one set of
boundaries. The space between the curve and the y
axis is the other boundary.

The x axis limits are
a and b. We subdivide this
interval into s rectangles, the width of each is
h=(b−a)÷s.
We take the function's value at the corner as the average height of
the curve over that interval. If the interval is small enough, this is
reasonably accurate.

Procedure 9.7. Integration Function in the interval a
to b in s steps

Initialize

x ← a

h ←
(b−a)÷s

sum ← 0.0

Loop. While a ≤ x <
b.

Update Sum. Increment sum by
f(x) ×
h.

Next X. Increment x by
h.

Return. Return sum as the area under the
curve f(x) for
a ≤ x <
b.

Field Bet Results. In the dice game of Craps, the Field bet in craps is a winner
when any of the numbers 2, 3, 4, 9, 10, 11 or 12 are rolled. On 2
and 12 it pays 2:1, on the other number, it pays 1:1.

Define a function win (dice,
num, pays ). If
the value of dice equals
num, then the value of
pays is returned, otherwise 0 is returned. Make
the default for pays a 1, so we don't have to
repeat this value over and over again.

Define a function field
(dice). This will call
win 7 times: once with each of the values for
which the field pays. If the value of dice is a 7, it returns -1
because the bet is a loss. Otherwise it returns 0 because the bet is
unresolved. It would start with

Create a function roll that creates two
dice values from 1 to 6 and returns their sum. The sum of two dice
will be a value from 2 to 12.

Create a main program that calls roll to
get a dice value, then calls field with the value
that is rolled to get the payout amount. Compute the average of
several hundred experiments.

range Function Keywords. Does the range function permit keywords for supplying argument
values? What are the keywords?

Optional First Argument. Optional parameters must come last, yet range fakes this out
by appearing to have an optional parameter that comes first. The
most common situation is range(5), and having to type
range(0,5) seems rather silly. In this case,
convenience trumps strict adherence to the rules. Is this a good
thing? Is strict adherence to the rules more or less important than
convenience?

Published under the terms of the Open Publication License