                On-line Guides All Guides eBook Store iOS / Android Linux for Beginners Office Productivity Linux Installation Linux Security Linux Utilities Linux Virtualization Linux Kernel System/Network Admin Programming Scripting Languages Development Tools Web Development GUI Toolkits/Desktop Databases Mail Systems openSolaris Eclipse Documentation Techotopia.com Virtuatopia.com How To Guides Virtualization General System Admin Linux Security Linux Filesystems Web Servers Graphics & Desktop PC Hardware Windows Problem Solutions Privacy Policy  ## Function Exercises

1. 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

1. Base Case. If p = 0, return 1.0.

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

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

2. 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

1. Base Case. If p = q , return p .

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

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

3. 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

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

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

4. 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 n th Fibonacci Number, F n

1. F 0 Case. If n = 0, return 0.

2. F 1 Case. If n = 1, return 1.

3. F n = F n−1 and F n−2If n > 2, return `fibonacci `( `n−1` ) + ```fibonacci ```( `n−2` ).

5. 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

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

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

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

6. 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

1. Initialize

x low

max x

maxFx `f`( `max` )

2. Loop. While low x < high .

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

max x

maxFx `f`( `max` )

2. Next X. Increment x by 1.

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

7. 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

1. Initialize

x a

h ← ( b a s

sum ← 0.0

2. Loop. While a x < b .

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

2. Next X. Increment x by h .

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

8. 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

```def field( dice ):
win( dice, 2, pays=2 )
win( dice, 3, pays=1 )

...

```

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.

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

10. 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 Design by Interspire