Greatest Common Divisor. The greatest common divisor is the largest number which will evenly divide two other numbers. Examples: GCD( 5, 10 ) = 5, the largest number that evenly divides 5 and 10. GCD( 21, 28 ) = 7, the largest number that divides 21 and 28.

GCD's are used to reduce fractions. Once you have the GCD of the numerator and denominator, they can both be divided by the GCD to reduce the fraction to simplest form. 21/28 reduces to 3/4.

Extracting the Square Root. This is a procedure for approximating the square root. It works by dividing the interval which contains the square root in half. Initially, we know the square root of the number is somewhere between 0 and the number. We locate a value in the middle of this interval and determine of the square root is more or less than this midpoint. We continually divide the intervals in half until we arrive at an interval which is small enough and contains the square root. If the interval is only 0.001 in width, then we have the square root accurate to 0.001

Sort Four Numbers. This is a challenging exercise in if-statement construction. For some additional insight, see [Dijkstra76], page 61.

Given 4 numbers ( W , X , Y , Z )

Assign variables w, x, y, z so that w ≤ x ≤ y ≤ z and w, x, y, z are from W , X , Y , and Z . Do not use an array. One way to guarantee the second part of the above is to initialize w, x, y, z to W , X , Y , Z , and then use swapping to rearrange the variables.

Hint: There are only a limited combination of out-of-order conditions among four variables. You can design a sequence of if statements, each of which fixes one of the out-of-order conditions. This sequence of if statements can be put into a loop. Once all of the out-of-order conditions are fixed, the numbers are in order, the loop can end.

Highest Power of 2. This can be used to determine how many bits are required to represent a number. We want the highest power of 2 which is less than or equal to our target number. For example 64 ≤ 100 < 128. The highest power of 2 ≤ 100 is 2⁶.

Given a number n , find a number p such that 2 ^p ≤ n < 2 ^p +1.

This can be done with only addition and multiplication by 2. Multiplication by 2, but the way, can be done with the << shift operator. Do not use the pow function, or even the ** operator, as these are too slow for our purposes.

Consider using a variable c , which you keep equal to 2 ^p . An initialization might be p ←1, c ←2. When you increment p by 1, you also double c .

Develop your own loop. This is actually quite challenging, even though the resulting program is tiny. For additional insight, see [Gries81], page 147.

How Much Effort to Produce Software? The following equations are the basic COCOMO estimating model, described in [Boehm81]. The input, K , is the number of 1000's of lines of source, total source lines÷1000.

Equation 8.1. Development Effort

Equation 8.2. Development Cost

Equation 8.3. Project Duration

Equation 8.4. Staffing

Where K is the number of 1000's of lines of source, E is effort in staff-months, D is duration in calendar months, S is the average staff size, R is the billing rate, C is the cost in dollars (assuming R $ per hour, and 152 working hours per staff-month).

Evaluate these functions for projects which range in size from 8,000 lines ( K =8) to 64,000 lines ( K =64) in steps of 8. Produce a table with lines of source, Effort, Duration, Cost and Staff size.

Wind Chill Table. Wind chill is used by meteorologists to describe the effect of cold and wind combined. Given the wind speed in miles per hour, v , and the temperature in °F, t , the Wind Chill, w , is given by the formula below. See Wind Chill in the section called “Numeric Types and Expressions” for more information.

Wind speeds are for 0 to 40 mph, above 40, the difference in wind speed doesn't have much practical impact on how cold you feel.

Evaluate this for all values of v (wind speed) from 0 to 40 mph in steps of 5, and all values of t (temperature) from -10 to 40 in steps of 5.

Celsius to Fahrenheit Conversion Tables. We'll make two slightly different conversion tables.

For values of Celsius from -20 to +30 in steps of 5, produce the equivalent Fahrenheit temperature. The following formula converts C (Celsius) to F (Fahrenheit).

For values of Fahrenheit from -10 to 100 in steps of 5, produce the equivalent Celsius temperatures. The following formula converts F (Fahrenheit) to C (Celsius).

Dive Planning Table. Given a surface air consumption rate, c , and the starting, s , and final, f , pressure in the air tank, a diver can determine maximum depths and times for a dive. For more information, see Surface Air Consumption Rate in the section called “Numeric Types and Expressions”.

Accept c , s and f from input, then evaluate the following for d from 30 to 120 in steps of 10. Print a table of t and d .

For each diver, c is pretty constant, and can be anywhere from 10 to 20, use 15 for this example. Also, s and f depend on the tank used, typical values are s =2500 and f =500.

Computing π. Each of the following series compute increasingly accurate values of π (3.1415926...)

Computing e. A logarithm is a power of some base. When we use logarithms, we can effectively multiply numbers using addition, and raise to powers using multiplication. Two Python built-in functions are related to this: math.log and math.exp. Both of these compute what are called natural logarithms, that is, logarithms where the base is e . This constant, e , is available in the math module, and it has the following formal definition:

Equation 8.5. Definition of e

For more information on the Σ operator, see the section called “Digression on The Sigma Operator”.

Equation 8.6. Definition of Factorial, n!

4!=4×3×2×1. By definition, 0! = 1.

If we add up the values 1/0! + 1/1! + 1/2! + 1/3! + 1/4! + ... we get the value of e. Clearly, when we get to about 1/10!, the fraction is so small it doesn't contribute much to the total.

We can do this with two loops, an outer loop to sum up the 1/ k !'s, and an inner loop to compute the k !'s.

However, if we have a temporary value of k !, each time through the loop we can multiply the temporary by k , and then add 1/ temp to the sum.

You can check your work against math.e ~ 2.71828... or math.exp ( 1 ).

Hailstone Numbers. For additional information, see [Banks02].

Start with a small number, n , 1 ≤ n ≤ 30.

There are two transformation rules that we will use:

Perform a loop with these two transformation rules until you get to n = 1. You'll note that when n = 1, you get a repeating sequence of 1, 4, 2, 1, 4, 2, ...

You can test for oddness using the % (remainder) operation. If n % 2 == 1, the number is odd, otherwise it is even.

The two interesting facts are the “path length”, the number of steps until you get to 1, and the maximum value found during the process.

Tabulate the path lengths and maximum values for numbers 1..30. You'll need an outer loop that ranges from 1 to 30. You'll need an inner loop to perform the two steps for computing a new n until n == 1; this inner loop will also count the number of steps and accumulate the maximum value seen during the process.

Check: for 27, the path length is 111, and the maximum value is 9232.