Let's say you deposit $1 in an interest bearing bank account, where your interest is calculated annually.

etymology of bank: Bankers (banchieri) were originally foreign money exchangers, who sat at benches (stall would be a better word; the french word for stool is "banc"), in the street, in Florence. (from The Ascent of Money, Niall Ferguson, The Penguin Press, NY, 2008, p42. ISBN-978-1-59420-192-9) (Italy was the birth place of banking.) The word "bank" is related to "embankment".

Let's assume your annual interest rate is 100%, calculated annually. At the end of the first year, the balance in your account will be $2. What would you guess would be the balance in your account, if your interest was calculated semi-annually (i.e. 50% interest twice a year), or quarterly (25% interest, but now 4 times a year), or monthly at 8&1/3%? How about weekly, daily, hourly, by the nanosecond? You'd be getting a smaller amount of interest each time, but the number of times your interest is added would be increasing by the same ratio. At the end of the year would you be

than if interest were calculated annually?

Let's try interest calculated twice a year. At the end of the first 6 months, your interest will be $1*1/2=$0.50 and your balance will be $1*(1.0+0.5)=$1.50. At the end of the year, your balance will be $1.50*(1.0+0.5)=$2.25 (instead of $2.00). It appears to be to your advantage to calculate interest at shorter intervals.

Will your balance at the end of the year be finite or infinite? Some series when summed go to 0, some reach a finite sum and some go to ∞. Unless you know the answer already, you aren't likely to guess the sum to ∞ of anything.

Let's find out what happens if you calculate interest at smaller and smaller intervals. Write code (filename calculate_interest.py) that has

Using these variables, write code to calculate (and print out) the value of balance at the end of the year For the first attempt at writing code, calculate interest only once, at the end of the year. Here's my code ^[197] and here's my output

igloo:# ./calculate_interest.py
evaluations/year 1 balance is 2.000000

Modify the code so that interest is calculated semi-annually (i.e. do two calculations, one after another) and print out the balance at the end of the year. Here's my code ^[198] and here's the output

igloo:# ./calculate_interest.py
evaluations/year 2 balance is 2.250000

If you haven't already picked it, the interest calculation should be done in a loop. Rewrite the code to interate evaluations_per_year times. Have the loop print out the loop variable and the balance. (If you're like me, you'll run into the fencepost problem and the number of iterations will be off by one; you'll have adjust the loop parameters to get the loop to execute the right number of times.) Here's my code ^[199] and here's the output

igloo:# ./calculate_interest.py
1 balance is 1.500000
2 balance is 2.250000
evaluations/year 2 balance is 2.250000

Try the program for interest calculated monthly and daily. Turn off the print statement in the loop and put the loop inside another loop, to calculate the interest for 1,10,100...10⁸ evaluations_per_year, printing out the balance for each iteration of the outer loop.

Here's the code ^[200] and here's the output

igloo:# ./calculate_interest.py 
evaluations/year          1 balance is 2.0000000000
evaluations/year          2 balance is 2.2500000000
evaluations/year         10 balance is 2.5937424601
evaluations/year        100 balance is 2.7048138294
evaluations/year       1000 balance is 2.7169239322
evaluations/year      10000 balance is 2.7181459268
evaluations/year     100000 balance is 2.7182682372
evaluations/year    1000000 balance is 2.7182804691
evaluations/year   10000000 balance is 2.7182816941
evaluations/year  100000000 balance is 2.7182817983
evaluations/year 1000000000 balance is 2.7182820520
evaluations/year 2000000000 balance is 2.7182820527

Since we haven't calculated an upper or lower bound, we don't have much an idea of the final value. It could be 2.71828... or we could be calculating a slowly divergent series, which gives a final answer of ∞. It turns out we're calculating the value of e, the base of natural logarithms. One of the formulas for e^x is (1+x/n)ⁿ for n→∞. The final value then is finite; the best guess, as judged by unchanging digits is 2.718282052. Here's the value of e from bc (run the command yourself, to see the relative speed of bc and the calculation we ran).

igloo:~# echo "scale=100;e(1)" | bc -l
2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274

2.718282052 for comparison, the value from (1+1/n)^n

	Note
	almost half our digits are wrong, we'll see why later.

As for the earlier calculation of π using bc, check that the value of e is not stored inside bc by timing the calculation of e^1.01.

For your upcoming presentation on e, make a table of the balance at the end of the year in your account if interest is calculated annually, monthly, weekly, daily, by the hour, minute, second.

This method of calculating e gets about half a decimal place, for a factor of 10 increase in calculation time. This is painfully slow, but if there wasn't anything better (there is), you'd have to use it.

When you're doing 10⁹ (≅2³²) arithmetic operations (e.g. addition, multiplication), you need to know whether the rounding errors have overwhelmed your calculation. In the case of pi errors we got a usable result, because the errors were relative to the size of the numbers being calculated and by going to higher precision (e.g. to 64 bit).

What happens with this calculation of e? We're calculating with (1+1/n)ⁿ, where n is large. If we were using 32 bit reals, i.e. with a 24 bit mantissa), we would chose the largest n possible, n=2²⁴ giving a mantissa of 1.000000000000000000000001₂. Because of rounding, the last two digits could be 00,01 or 10. The resulting number then would be e⁰=1, e¹≍2.7 or e²≍7.4. We're calculating using a number that is as close to 1.0 as possible and the magnitude of the rounding errors is comparable to the magnitude of the last few digits in the number being multiplied. We will have large errors, because the calculation is dependant on the small difference from 1.0, rather than the relative value as it was in the case of the calculation of π.

At this stage let's look at the machine's epsilon.

Here's the value for e calculated from the series and the real value from bc.

e from interest series  e=2.718282052
e from bc               e=2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274

Our calculation is wrong in the last 4 digits. We need a different method of calculating e.

Let's say we wanted to calculate e=(1+1/n)ⁿ for n=1024. In the above section, we did this with 1024 multiplications. Instead let's do this

x=(1+1/1024)
x = x^2		# x=(1+1/1024)^2
x = x^2		# x=(1+1/1024)^4
x = x^2		# x=(1+1/1024)^8
x = x^2		# x=(1+1/1024)^16
x = x^2		# x=(1+1/1024)^32
x = x^2		# x=(1+1/1024)^64
x = x^2		# x=(1+1/1024)^128
x = x^2		# x=(1+1/1024)^256
x = x^2		# x=(1+1/1024)^512
x = x^2		# x=(1+1/1024)^1024

Doing it this way, we only need 10 iterations rather than 1024 iterations to find (1+1/1024)^1024.

	Note
	Note that 1024=210 (i.e. log21024 = 10) and we needed 10 steps to do the calculation.

This algorithm scales with O(log(n)) (here 10) and is much faster than doing the calculation with an algorithm that scales with O(n) (here 1024). You can only use this algorithm for n as a power of 2. This is not a practical restriction; you usually want n as big as you can get; and a large power of 2 is just fine.

The errors are a lot better. The divisor n is a power of 2 and has an exact representation in binary. Thus there will be no rounding errors in (1+1/n). As with the previous algorithm, we still have the problem for 1/n less than the machine's epsilon (what's the problem ^[201] ?). There still will be a few rounding errors. Look what happens when you square a number close to (1+epsilon) (assume an 8-bit machine)

(1+x)^2=1+2x+x^2
for x=1/2^8
then 
2x=1/2^7
x^2=1/2^16

While addition (usually) will fit into the register size of the machine (unless you get overflow), multiplication always requires twice the register width (if you have a 8-bit machine, and you want to square 255, how many bits will you need for your answer?). To do multiplication, the machine's registers are double width. (Joe FIXME, is this true for integers?) For integer multiplication, you must make sure the answer will fit back into a normal register width, or your program will exit with an overflow error. For real numbers, the least significant digits are dropped. How does this affect the squaring in an an 8-bit machine? Here's the output from bc doing the calculations to 40 decimal (about 128 bit) precision. The 8-bit computer will throw away anything past 8-bits.

x=1+1/2^8=10000001 binary
x^2      =1000001000000001
x^4      =10000100

 1.0000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 1.0000010000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 1.0000100000011000001000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 1.0001000001110001110001000110011100000111000001000000000011111111111111111111111111111111111111111111111111111111111111111111111111111
 1.0010000111110001111100111110100111101000100010101001111111011101101010001111001000000110000111100000100000000000111111111111111111101
 1.0100100001100100001011010110001101000101110101101011011100100011110000011101101111100110100010101101001111001111011000011000110100010
 1.1010010101000000110110111000000111100000100100001101001000010111010010000011010010011101001011110001001110100110110010111110011110111
10.1011010100101110011000100110011110101001110001000001001110000101011111011000011001111001111000011111110100011000111001011111011011011

We should be able to get However in the example above, we don't have to multiply the error 1024 times, only 10 times. With this algorithm, we should expect an answer with smaller errors in a shorter time.

If errors weren't a problem, how many iterations would we need (approximately) if we were to calculate e=(1+1/n)ⁿ, using the logarithmic algorithm, for n=10^{9 [202]} ? Write out each step by hand to see that you get this answer. If we scale to multiplying 2³⁰≅10⁹ times, we'll only multiply the rounding errors 30 times.

What is the maximum number of squarings we can do on a 64-bit machine (hint: x=(1+1/n) can't be less than (1+epsilon). What value of n will do this?) ^[203] ?

Could we have used the logarithmic algorithm for the numerical integration of π ^[204] ?

Let's code this up. Copy calculate_interest.py to calculate_interest_logarithmic.py. (You're going to gut most of the old code.) Here's the first attempt at the writing the code (you're doing only one iteration, so there's no loop yet).

Here's my code ^[205] and here's my output.

pip:/src/da/python_class/class_code# ./!$
./calculate_interest_logarithmic_1.py
evaluations/year          1
iteration   1 balance=2.00000000000000000000

We now need to add a loop to do the squaring operations. Note in the initial example above (with 10 iterations), that the first iteration did something different to the rest of the iterations (the first iteration gave the formula for calculating x while the rest of the iterations did the squaring operations). We could implement this in either of these two logically equivalent ways.

#pseudo code
iterations=10

#iteration #1
define x=(1+1/n)
print statement

#iterate for loop_variable =2,iterations+1
	x=x**2
	print statment

or

#pseudo code
iterations=10

iterate for loop_variable=1,iterations+1
	if loop_variable==1
		define x=(1+1/n)
	else
		x=x^2

Both of these are a bit messy.

Sometimes you can't write aesthetically pleasing code; sometimes it's a mess. A problem which is trivial for a human to do in their head, can be quite hard to write down. You can write code to do it either of these two ways (or any other way you want). I'll show both methods above.

For the 1st method: below your current code,

Here's my code for (1st method) ^[206] and here's my output for iterations=1

and for iterations=4

For the 2nd method:

Here's my code (2nd method) ^[207] and here's my output for iterations=1

and for iterations=4

The definition of a factorial is

n!=n*(n-1)*(n-2)...1

where n! is pronounced "n factorial" or "factorial n"

examples
3!=3*2*1=6
6!=6*5*4*3*2*1=120

Factorial series increase the fastest of all series (even faster than exponential series). Factorials wind up in combinatorics.

How many different orderings, left to right, are possible if you want to line up 4 people in a photo? The answer is 4!. You can pick any of 4 people for the left most position. Now you have 3 people you can chose from for the next position, then 2 for the next position, and there is only 1 person for the last position. Since the choices of people at each position are independant, the number of possibilities is 4*3*2*1=4!.

	Note
	0!=1. (there is only 1 way of arranging 0 people in a photo with 0 people.)

Here's a faster converging series to calculate e:

e=1/0!+1/1!+1/2!+1/3!...

Since you'll need a conditional to handle calculation of factorial n for n=0, it's simpler to use the series

e=1+1/1!+1/2!+1/3!...

and have your code initialise e=1, allowing the loop for the factorial series to start at 1/1!.

Write code (e_by_factorial.py) to

Now you want to calculate the value of e from the first two terms (1+1/1!). Do this by

then prints out e. Here's my code ^[208] and here's my output.

pip:# ./!$
./e_by_factorial.py
2.0

What does the construction "/=" do?

Now put the calculation of e into a loop, which calculates the next factorial number in the series and adds it to e. Iterate 20 times, each time print out the calculated value for e using

        print "%2.30f" %e

Here's my code ^[209] and here's my output

dennis:/src/da/python_class/class_code# ./e_by_factorial.py
2.000000000000000000000000000000
2.500000000000000000000000000000
2.666666666666666518636930049979
2.708333333333333037273860099958
2.716666666666666341001246109954
2.718055555555555447000415369985
2.718253968253968366752815200016
2.718278769841270037233016410028
2.718281525573192247691167722223
2.718281801146384513145903838449
2.718281826198492900914516212652
2.718281828286168710917536373017
2.718281828446759362805096316151
2.718281828458230187095523433527
2.718281828458994908714885241352
2.718281828459042870349549048115
2.718281828459045534884808148490
2.718281828459045534884808148490
2.718281828459045534884808148490

Note that the output increases in precision by a factor of 10 for each iteration (at least up to iteration 15 or so). This is a quickly converging series (all series based on factorials converge quickly). Although you can't tell from the output, this series does converge. Note that the last 3 entries are identical and match the 4th last entry to 15 decimal places.. What piece of information brings together "real" and "accurate to 15 decimal places" ^[210] ? As a check, compare the output of your program with the value from bc.

e from bc               e=2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274
e_by_factorial          e=2.718281828459045
e from interest series  e=2.71828

The value from the factorial series matches the real value to 16 places.

It's possible that any real arithmetic operation (i.e. +-*/) will be rounded, so you must plan for an upper bound in errors of 1 bit/operation. With the 52 bit mantissa for 64 bit math, each operation can potentially introduce an error of 1:2⁵² (≅ 1:10¹⁶ - the machine's epsilon). We needed 10⁹ operations to calculate e by the previous method. How many operations were needed to calculate e by the factorial series? We needed only 16 iterations to calculate e to the precision of python's 64 bit math. How many real math operations were involved in the 16 iterations? It's obviously very much less than 10⁹, but we'll need the exact number in the future, when we start comparing two good (fast) algorithms, so let's calculate it exactly.

The addition of a term in the formula for e requires

This is n+2 operations. For a back of the envelope calculation, let's assume that n operations are required (we can come back and do the exact calculation later). For 16 iterations then, the number of operations is 1+2+.....16. This series of numbers; 1,2..16, is an arithmetic progression

A series of numbers, where the difference between consecutive numbers is constant, is called an Arithmetic Progression (http://en.wikipedia.org/wiki/Arithmetic_progression). As an example, the set of numbers 2,5,8,11....29, is an arithmetic progression, whose first and last members are 2,29 with a difference of 3.

First we can find an approximate upper bound for the number of operations. Assume the series was 16,16...16 for 16 numbers. The sum of these numbers is 256 giving an upper bound of 256 for the number of operations to calculate e to 16 significant figures. Let's get a better estimate. Here's a diagram showing the number of operations for each term, the first where the number of operations is modelled at 16 for each term, and the second where the number of operations is modelled as n for each term. The sum of the heights of all the members of the series can be found from the area of each of the two diagrams.

****************                 *
****************                **
****************               ***
****************              ****
****************             *****
****************            ******
****************           *******
****************          ********
****************         *********
****************        **********
****************       ***********
****************      ************
****************     *************
****************    **************
****************   ***************
****************  ****************
height=16         height=1..16

The first is a square 16*16 (it doesn't look square because the area occupied by a letter on a computer screen is a rectangle), and the second triangular looking object of 16*16. The second diagram represents the actual number of operations for the 16 iterations used to calculate e. Using simple geometry, what is the number of operations (the area of the 2nd diagram) ^[211] ?

Where's the fencepost error? The triangular looking object above is not a triangle at all; it's a set of stairs. The "*" characters on the hypoteneuse are full characters, and not a "*" sliced diagnonally along the hypotenuse. Here's what the object really looks like

               _|*
              _|**
             _|***
            _|****
           _|*****
          _|******
         _|*******
        _|********
       _|*********
      _|**********
     _|***********
    _|************
   _|*************
  _|**************
 _|***************
 |****************
height=1..16

To calculate the area geometrically, we duplicate the object, rotate it 180°, and join it with the original to make a rectangle (here the duplicated version uses a different symbol).

................
...............*
..............**
.............***
............****
...........*****
..........******
.........*******
........********
.......*********
......**********
.....***********
....************
...*************
..**************
.***************
****************
height=1..16

What is the area of this rectangle and hence the number of real operations required to calculate e ^[212] ?

This means that upto 7 bits (approximately, it would be 7 bits if 128 operations were used) of the 52 bit mantissa could be wrong, or 7/3 i.e. the last 2 decimal digits could be wrong. From the output from bc above, we don't see any rounding errors.

From your understanding of the construction of the rectangle above, what's the formula for the sum of the elements of an arithmetic progression, which has n elements, the first term having the value first and the last term having the value last ^[213] ?

The number of operations was n+2 and not n. Now let's do the exact calculation. The number of operations is 3..18. Here's the diagram showing the number of operations at each iteration of the loop.

................
................
................
...............*
..............**
.............***
............****
...........*****
..........******
.........*******
........********
.......*********
......**********
.....***********
....************
...*************
..**************
.***************
****************
****************
****************
height=3..18

What's the number of real number operations (do it by inspecting the diagram here and from your formula). ^[214] ? Does the exact calculation make any real difference to the number of bits of the mantissa that could be wrong ^[215] ?

The factorial series is better for calculating e than the (1+1/n)ⁿ series for two linked reasons

There's an interesting story about arithmetic progressions and one of the great mathematicians, Gauss. When Gauss was in grade school, the teacher wanted to keep the students busy for a while, so they wouldn't bother him, and he set the class to the task of adding all the numbers 1..100. Gauss handed in his answer immediately, while the rest of the class swatted away, presumably adding all the numbers by brute force. The teacher thought Gauss was being insolent and didn't look at Gauss' answer till all the other student's answers had been handed in and marked. The teacher was astonished to find that Gauss' answer was correct.

Before we look at how Gauss did it, let's look at addition of all numbers from 1..99 (we can add the 100 later). People in this class familiar with loops and finding common elements in a problem, should be able to see that addition of (1+2+3+4+5+6+7+8+9)+(10+11+12+13+1+4+15+16+17+18+19)..99 involves a core problem of adding the numbers 1..9 a couple of different ways. Can you see how to add 1..99 ^[216] ?

Gauss used the geometric constuct we used above, although he didn't need to draw the dots as we did. Gauss wrote out the numbers in a line and then below them wrote out the numbers in the reverse order. His notebook looked like this

  1   2   3   4 ...  97  98  99  100
100  99  98  97 ...   4   3   2    1

What are the sums of each pair of terms?

  1   2   3   4 ...  97  98  99  100
100  99  98  97 ...   4   3   2    1
--- --- --- ---     --- --- ---  ---
101 101 101 101     101 101 101  101

How many terms did Gauss have across his page (it's unlikely that Gauss wrote out all the terms) ^[217] ? What's the sum of all the terms on the bottom line ^[218] ? What's the sum of the original arithmetic progression ^[219] ?

Exercise in Arithmetic Progressions: Calculate the number of casing stones on the Great Pyramid of Khufu at Giza

First a bit of background:

Note

About pyramids in Egypt: Great Pyramid of Giza (http://en.wikipedia.org/wiki/Great_Pyramid_of_Giza), Another look at the Pyramids of Giza by Dennis Balthaser (http://www.truthseekeratroswell.com/ed010108.html) Seven Wonders of the Ancient World (http://en.wikipedia.org/wiki/Wonders_of_the_World#Seven_Wonders_of_the_Ancient_World), Pharaonic monuments in Cairo and Giza (http://www.sis.gov.eg/En/Arts&Culture/Monuments/PharaonicMonuments/070202000000000006.htm). For a likely explanation of in involvement of the number π in the dimensions of the Great Pyramid see Pi and the Great Pyramid (http://www.math.washington.edu/~greenber/PiPyr.html)

The Great Pyramid of Khufu (Cheops in Greek) was built about 2560 BC over a period of 20yrs, employing about 100,000 labourers, moving 800 tonnes of stone a day, excavating, cutting, polishing, transporting and mounting a 15 ton stone every 90 sec. It is the only one of the Seven Wonders of the Ancient World to survive till today. For 3800 yrs it was the tallest man-made structure on earth. The base is horizontal to 15mm, the sides are identical in length to 58mm. The ratio of the circumference of the base (4*440 cubits) to the height (280 cubits) is 2π to an accuracy of 0.04%. The sides of the base are not a square but a 4 pointed star as can be seen by aerial photography at the right time of day (see Aerial photo by Groves 1940 http://www.world-mysteries.com/mpl_2conc1.gif). The closeness of the angles of the base to a right angle (1' deviation) compared to the deviation of the orientation of the pyramid to true north (3' deviation west), allows us to conclude that the pyramid must have been originally oriented to true north and that the continent of Africa has since rotated, with respect to the axis of the earth's rotation, carrying the pyramid with it. The amount of rotation is consistent with estimates from plate tectonics (I read the original paper back in - I think - the '70's but I can't find a reference to it with google).

The pyramid was surfaced by white polished limestone casing stones. Most of the casing stones at Giza were removed to build Cairo. The few that remain today are at the top of the Pyramid of Khafre . The remaining casing stones are dazzling in today's desert sun. Back when the whole pyramid was covered in these stones, it must have been quite a sight as you approached it from over the horizon.

The casing stones on the Pyramid of Khufu are all of the same height and width (to maintain symmetry of the sides), accurate to 0.5mm and weighing 15tons. The casing stones were transported by barge, from the quarry at Aswan, during the Nile flooding, allowing the stones to be deposited next to the pyramid.

Aswan (http://en.wikipedia.org/wiki/Aswan) is famous not only for its quarry which produced syenite (a pink granite used for many of the obelisks in Egypt, and which is also found in our local North Carolina State Park, the Eno River Park), but for being at one end of the arc used in the first estimate of the circumference of the earth by Eratosthenes.

By a fortunate cancellation of two errors of about 20%, Eratosthene's value differed by only 1% from the current accepted value. Christopher Columbus (http://en.wikipedia.org/wiki/Christopher_Columbus) was looking for a route to Japan/India/China across the Atlantic. At the time no ship could carry enough food to last the distance across the Atlantic to China from Europe. As well, a crew would mutiny if required cross open ocean that distance: they might sail off the edge of the earth.

Using the method of Eratosthenes, a century later, Posidonius made his own estimate. Posidonius knew that the star Canopus grazed the horizon at Rhodes (his home) and measured it's maximum elevation as 7.5° (actually 5deg;) at Alexandria. Again by cancellation of errors in the elevation of the star and the distance between the two towns, Posidonius came up with the correct answer.

	Note
	due to light pollution and atmospheric pollution, on most places on earth, it's impossible to see any star on the horizon, much less at 5° above the horizon.

Posidonius later corrected the distance from Rhodes to Alexandria, coming up with a now incorrect estimate of the circumference of the earth of 30,000km (18,000 miles). The two estimates of the size of the earth became known in Europe after translation from Arabic (12th Century). Medieval scholars debated the veracity of the two values for centuries, without any attempt to verify the measurement themselves (for in those days truth was revealed, rather than tested, so the matter would be resolved by debate, rather than measurement).

	Note
	Due to precession of the equinoxes, Canopus no longer reaches an elevation high enough to graze the horizon at Rhodes. Presumably this would have caused some consternation amongst people attempting to reproduce Posidonius's measurement.

	Note
	Posidonius travelled widely. In Hispania, on the Atlantic coast at Gades (the modern Cadiz), Posidonius studied the tides. He observed that the daily tides were connected with the orbit and the monthly tides with the cycles of the Moon.

To show that his trip was practical, in order to gain financing from Queen Isabella, Columbus used the value 30,000km for the circumference of the earth, and a width of 3,300km (2,000miles) of Sipangu (Japan), making the trip across the Atlantic appear practical. Knowing the potential for mutiny, Columbus kept two logs, one to show the crew, which showed that they'd travelled a shorter distance, as well as the correct log. Columbus was lucky to find the West Indies. His crew, being further from land than anyone had ever been, and was within a day of mutiny.

The currently accepted value for the circumference of the earth is 40,000km (thanks to Napoleon).

	Note
	What does Napoleon have to do with the circumference of the earth [220] ?

	Note
	You may wonder what Napoleon is doing in a section on the Pyramids of Egypt, but I thought the connection was too strong to pass up the opportunity to talk about it. You should now go find the connection between Napoleon and the Sphinx which will bring us back to Egypt again.

The dimensions of the casing stones given in Quarries in Ancient Egypt (http://www.cheops-pyramide.ch/khufu-pyramid/stone-quarries.html) gives dimensions for the bottom casing stones of 1 m x 2.5m and 1-1.5m high (6.5 - 10 tons) while the upper casing stones are 1m x 1m and 0.5m high (1.3 tons). Details on the thickness of each layer are at Stone courses of the Pyramid of Khufu (http://www.cheops-pyramide.ch/khufu-pyramid/stonecourses-pyramid.html).

Assuming the same height and width for the casing stones, the number of casing stones in each layer is a (decreasing) arithmetic progression. The height of the pyramid is 146m (482') with a base of 230m (756'). Assuming the pyramid was covered in the upper stones only, how many casing stones would you have needed to order to cover the pyramid? First calculate the number of layers of casing stones (the number of members of the arithmetic series) and the number of casing stones in the first (bottom) and last (top) layers. Then calculate the number of casing stones in a face of the pyramid, then calculate the total number of casing stone for the whole pyramid. Here's my calculations ^[221] . The actual number of casing stones given in the references is 144,000. Our answer doesn't fit real well.

So what happened to our calculation? The references are unclear as to the size of the facing stones. Further work needs to be done (a class trip to the pyramids?).

Since this wasn't a particularly successful calculation, let's try another. A well known 20th century pyramid is the Transamerica Pyramid (http://en.wikipedia.org/wiki/Transamerica_Pyramid) in San Francisco. The number of windows (from http://ecow.engr.wisc.edu/cgi-bin/get/cee/340/bank/11studentpro/transamericabuilding-2.doc) is 3678. You can get an estimate of the number of floors with windows from transamerica.jpg (http://www.pursuethepassion.com/interviews/wp-content/uploads/2007/08/transamerica.jpg) giving about 45 floors of windows (there are supposed to be 48 floors, presumably the extra 3 floors are in the lower section, which has slightly different architecture). Notice from this photo, that the floors are in pairs, with two consecutive floors having the same number of windows. The lower floor of each pair have longer windows at the ends to make up the extra length. The lowest visible floor has 29 windows on a side. The top floor with windows has 8 windows (transam-coit-01-big.jpg http://www.danheller.com/images/California/SanFrancisco/Buildings/transam-coit-big.jpg). (The different colored top, that starts at the top of the elevator shafts - the "wings" - I think is decorative and not part of the floor count.) Let's see if we've accounted for all the windows. We have windows (starting at the bottom) in this series: 29,29,28,28..8,8. How many members are there in this series ^[222] ? Let's add the windows in pairs of floors so we now have an arithmetics series: 58,56...16. What's the sum of this series ^[223] ? There's about 800 windows unaccounted for. (We're not doing real well here either.)

FIXME (elephants have linear ears)

	Note
	The historical writeup on negative numbers came largely from "e: The Story of a Number, Eli Maor (1994), Princeton University Press, ISBN 0-691-05854-7.

The Great Numbers of Mathematics all appear in Euler's Identity (http://en.wikipedia.org/wiki/Euler's_identity)

e^iπ = -1

e^iπ + 1 = 0

The Roman number scheme had no zero ^[224] . The concept of Zero (http://en.wikipedia.org/wiki/Zero) and positional notation entered Europe in the 12th century from the Arab world. It had originated in 628AD in a book by Brahmagupta in India, but was ignored in Europe, mired deep in 1000yrs of ignorance (the Dark Ages). In Central America, the Olmecs were using 0 in the 4th century BC.

Greek mathematics was geometry, for which only positive numbers were needed (lengths, areas and volumes). For the longest time, no-one could handle the concept of less than nothing, much less multiply two negative numbers. Fibionacci (1225) bravely interpreted a negative number in a financial statement as a loss, but this effort was lost on mathematicians. For mathematicians, the idea of subtracting 5 apples from 3 apples was absurd (one of the names given to negative numbers). Bombelli (b 1530) assigned real numbers to the length of a line, with the 4 operators (+-*/) corresponding to movements along the line and that negative numbers were an extension of the line to the left. It was only when subtraction was recognised as being the inverse of addition, that negative numbers became part of geometry and hence math.

Negative numbers cause no problems for even the youngest people now. It's now obvious that they obey the same rules as positive numbers. However we must remember how much effort and time it took to understand what appears to us now as a trivial step.

The concept of π has been handled well since the beginning of time. However our current understanding of π as a transcendental number is only recent.

i=sqrt(-1) is a new concept. Without it, wave functions and much of modern physics and math cannot be understood. see: An Imaginery Tale, The Story of sqrt(-1), Paul J. Nahin 1998, Princeton University Press, ISBN 0-691-02795-1.

An example: what pair of numbers have a sum of 2, and a product of 1 ^[225] ?

What pair of number have a sum of 2, and a product of 2? This problem had no solution till recently. When mathematicians find problems which have a solution for some range of numbers, but not for other quite reasonable looking numbers, they assume that something is missing in mathematics, rather than the problem has no solution for those numbers. The solution to this problem came with the discovery that i=sqrt(-1) behaved quite normally under standard operations (+-*/). It took some time for i to be accepted as just another number, since there was initially no obvious way to represent it geometrically. In the initial confusion, numbers using i were called imaginary (or impossible) to contrast them with real numbers. The name imaginary is still in use and is most unfortunate: imaginary numbers are no less real than numbers which represent less than nothing.

The solution: (1+i, 1-i). Add these numbers and multiply them to see the result.

e is the basis for exponential functions. It is also the basis for natural logarithms. Logarithms to base 10 (called common logarithms) are better known. Logarithms are used to substitute addition for the more complicated process of multiplication. Logarithms were a great advance allowing engineering and math multiplications involved in orbital mechanics, surveying and construction. The first log tables were constructed by hand by Napier, who spent 20 years calculating the 10⁷ logarithms to 7 significant figures. Multiplication then involved looking up logs in a book, adding them and then converting back to the number using a table of anti-logarithms. Later the slide rule allowed the same calculations to be done in seconds, provided you could accept the reduced accuracy of 3-4 signicant figures. The slide rule was used to design all the spacecraft in the era of early space exploration (including ones with human crews), as well as bridges, jet engines, aeroplanes, power plants, electronics (in fact, anything needing a multiplication). It wasn't till the mid 1970's that hand held calculators could do a faster job of multiplying than a human using tables of logarithms. Very few engineering companies could afford a computer.

Why did anyone care about orbital mechanics ^[226] ? It's hardly a topic of conversation in our time.

The great numbers are required for the modern understanding of the physical world. If you're interested in math, a landmark in your progress will be understanding Euler's identity. which you should have by the time you leave high school. If not, you can hold your teachers accountable for failing in their job.

Bank interest is usually put back into the account, where the interest now draws interest. This process of allowing interest to accrue interest is called compound interest.

Write code to calculate compound interest (call it compound_interest.py). You deposit a fixed amount at the beginning of the year, with interest calculated annually at the end of the year. Variables you'll need (with some initialising values) are

Let's do the calculation for only 1 year. Start with your initial principal, add your deposit, wait a year, calculate your interest and add it to your principal.

Here's my code ^[227] and here's my output

pip:# ./compound_interest.py
principal   10500.00

Put your interest calculation into a loop (do you need a for loop or a while loop), which prints out your age and principal at the end of each year, using the start and end ages which you've initialised. Here's my code ^[228] and here's my output

pip:/src/da/python_class/class_code# ./compound_interest.py
age 19 principal   10500.00
age 20 principal   21525.00
age 21 principal   33101.25
age 22 principal   45256.31
age 23 principal   58019.13
age 24 principal   71420.08
age 25 principal   85491.09
age 26 principal  100265.64
age 27 principal  115778.93
age 28 principal  132067.87
age 29 principal  149171.27
age 30 principal  167129.83
age 31 principal  185986.32
age 32 principal  205785.64
age 33 principal  226574.92
age 34 principal  248403.66
age 35 principal  271323.85
age 36 principal  295390.04
age 37 principal  320659.54
age 38 principal  347192.52
age 39 principal  375052.14
age 40 principal  404304.75
age 41 principal  435019.99
age 42 principal  467270.99
age 43 principal  501134.54
age 44 principal  536691.26
age 45 principal  574025.83
age 46 principal  613227.12
age 47 principal  654388.48
age 48 principal  697607.90
age 49 principal  742988.29
age 50 principal  790637.71
age 51 principal  840669.59
age 52 principal  893203.07
age 53 principal  948363.23
age 54 principal 1006281.39
age 55 principal 1067095.46
age 56 principal 1130950.23
age 57 principal 1197997.74
age 58 principal 1268397.63
age 59 principal 1342317.51
age 60 principal 1419933.39
age 61 principal 1501430.06
age 62 principal 1587001.56
age 63 principal 1676851.64
age 64 principal 1771194.22
age 65 principal 1870253.93

You're depositing $10k/yr. How much (approximately) does the bank deposit the first year, the last year ^[229] ? At retirement age, how much (approximately) did you deposit, and how much did the bank deposit ^[230] ? The bank deposited 3 times the amount you did, even though it was only adding 5% interest each year. The growth of money in a compound interest account is one of the wonders of exponential growth.

If you're going this route, the payoff doesn't come till the end (and you have to start early). Rerun the calculations for an interest rate of 5%, and starting saving at the age of 20,25,30,35,40.

How long do you have to delay saving for your final principal to be reduced by half (approximately) ^[231] . There is a disadvantage in delaying earning by doing lengthy studies (e.g. a Ph.D) (you may get a lifestyle you like, but at a lower income on retirement). Rerun the calculations (at 5% interest) for a person who starts earning early (e.g. a plumber) and a Ph.D. who starts earning at 30, but because of a higher salary, can save $20k/yr.

Another property of exponential growth is that small increases in the amount of interest, have large effects on the final amount. Rerun the calculations for an interest rate of 3,4,5,6,7%. Here's my results.

If your interest rate doubles (say from 3% to 6%), does your final principal less than double, double, or more than double? People spend a lot of time looking for places to invest their money at higher rates. Investments which offer higher interest rates are riskier (a certain percentage of them will fail) and the higher interest rate is to allow for the fact that some of them fail (you are more likely to loose your shirt with an investment that offers a higher rate of return).

For your upcoming presentation, prepare a table showing your balance at retirement as a function of the age you started saving; show the amount of money you deposited and the bank deposited. Show the balance as a function of the interest rate. Be prepared to discuss the financial consequences of choosing a career as a plumber or a Ph.D.

While the above section shows that at Ph.D. and a plumber will be about even savings-wise at retirement, there is another exponential process going against the person who does long studies: the interest you but a house on a mortgage (rather than cash, which most people don't have). (The calculations below apply to other loans, e.g. student loans.)

First, how a mortgage works: In the US, people, who want to buy a house and who don't have the cash to pay for it (most of them), take out a mortgage (http://en.wikipedia.org/wiki/Mortgage). A mortgage is a relatively new invention (early 20th century) and was popularized by Roosevelt's New Deal (see Roosevelt's New Deal http://www.bestreversemortgage.com/reverse-mortgage/from-roosevelts-new-deal-to-the-deal-of-a-lifetime/)

Previously only rich people could buy a house; the rest rented. In places like US, renters were sentenced to a life of penury and beholden to odious landlords. In other places (e.g. Europe), owning a house was never seen as being particularly desirable, most people choose to rent and presumably the relationship of a renter with the owner (more often a Bank than a person) was more amicable than in the US. In Australia, people just expect that everyone should own their house (and they do), because that's just the way that it's supposed to be, so most people take out a mortgage as soon as they start earning. In (at least Sydney where I grew up) Australia, changing jobs doesn't require you to move. The city has a great train system, and if you change jobs, you just get off the train at a different stop. A person paying off a mortgage in Sydney won't have to sell their house when they get a new job. In the US, a change of job usually requires you to sell your house, and move. Most US towns are small, and there is only ever 1 job for any person. If you loose your job in the US, you have to move. This arrangement keeps people in jobs they hate. The US job system wrecks the main feature of a mortgage, which is that you don't get any benefit of buying a house on a mortgage, unless you own it for a while (this will be explained below).

The essential features of a mortgage are

Let's see how the US system works: The median house price in the US in 2008 is 250k$. A mortgage lending company expects a deposit of at least 5% of the house price (to show that you're capable of at least a token level of saving, the actual amount is 5-20% depending on the politics and the economics of the moment, but we'll use 5% for the calculations here), does a credit check on you (makes sure you've paid off your other loans, and that you have a steady job), checks that the house is in good condition and is worth the amount of the mortgage, and then after the mortgagee pays legal fees etc, the mortgage is issued and the mortagee gets a book of coupons to fill in, one each month and an address to send the monthly check (cheque) (usually the mortgagee arranges for their bank to do it automatically).

Let's say you've just scraped the 5% deposit and fees and have got a mortgage for 95% of 250k$ (23k75$) at 6% interest/year. If you don't pay off any principal (i.e. the loan), what will be your monthly interest ^[232] ? You don't want a mortgage like this (called a Balloon Mortgage) as you're not paying off any of the principal. You'll be paying interest forever. Let's say instead that you decide each month, to pay off $100 of principal along with the interest payment. What will be your first month's payment ^[233] ? If for the 2nd month you pay off another $100 of principal, and continue to pay interest on the debt at 6%/yr, will your second month's payment be less than, the same as, or more than the first month's payment ^[234] ?

A mortgage like this will have a slowly reducing payment each month, since you will be paying interest on a reduced amount of principal. Having a different payment each month is difficult for the mortgagee to track. The accepted solution is to keep the monthly payment constant and to let the accountants (or now computers) handle the varying amounts of principal and interest each month. Using this algorithm, the mortgagee pays the same amount ($1287) each month, but in the 2nd month has an interest payment lower by $6.44. The mortgagee instead puts the $6.44 towards payment of principal. Here's the calculations for the 2nd month with a constant monthly payment.

1st month:
principal at start          =237500.00
interest on principal at 6% =           1187.00
principal                   =            100.00
1st payment (end month)     =           1287.50

2nd month:
principal at start          =236212.50 
interest on principal at 6% =           1181.06
payment of $106.44 principal=            106.44
2nd payment (end month)     =           1287.50

This schedule (constant payments) has lots of advantages for both the mortgagor and mortgagee based on the following assumptions

The things that (can) go wrong with a mortgage are

(Some) people don't use their money wisely. Rich people spend their money differently to poor people: a poor person will buy an expensive SUV or PickUp truck, whose value in 5-10yrs will be $0. A rich person, who has a lot more money, will buy an adequate car, knowing that it's value will quickly go to $0, and put the rest of their disposable income into some investment; a bigger house, education, lending money to other people for mortgages, stocks, art.

Back to the mortgage calculation: There is a formula for doing these calculations (see Mortgage Calculator http://en.wikipedia.org/wiki/Mortgage_Calculator). Rather than teach you the math neccessary to understand the derivation of the formula, we'll program the computer to do the calculations by brute force.

	Note
	Mortgage calculator webpages are everywhere on the internet.

Write code mortgage_calculation.py to include the following

Here's my code ^[238] and here's my output

dennis: class_code# ./mortgage_calculation.py 
 time    princ. remaining     monthly_payment   principal payment    interest payment      total int paid
    0           250000.00             1350.00                0.00                0.00                0.00
    1           249900.00             1350.00              100.00             1250.00             1250.00

Copy mortgage_calcultion.py to mortgage_calculation_2.py. Add/do the following checking that the program produced sensible output at each stage.

Here's my code ^[239] and here's my output

dennis: class_code# ./mortgage_calculation_2.py
 initial_principal_payment              248.88 annual_interest 0.0600
 time    princ. remaining     monthly_payment   principal payment    interest payment      total int paid       total payment
    0           250000.00             1498.88                0.00                0.00                0.00                0.00
   12           246929.97             1498.88              262.91             1235.96            14916.49            17986.51
   24           243670.60             1498.88              279.13             1219.75            29643.62            35973.02
   36           240210.19             1498.88              296.34             1202.53            44169.72            53959.54
   48           236536.35             1498.88              314.62             1184.25            58482.40            71946.05
   60           232635.91             1498.88              334.03             1164.85            72568.47            89932.56
   72           228494.91             1498.88              354.63             1144.25            86413.98           107919.07
   84           224098.50             1498.88              376.50             1122.37           100004.08           125905.58
   96           219430.92             1498.88              399.72             1099.15           113323.02           143892.10
  108           214475.46             1498.88              424.38             1074.50           126354.07           161878.61
  120           209214.36             1498.88              450.55             1048.32           139079.48           179865.12
  132           203628.77             1498.88              478.34             1020.54           151480.40           197851.63
  144           197698.67             1498.88              507.84              991.03           163536.81           215838.14
  156           191402.81             1498.88              539.17              959.71           175227.47           233824.66
  168           184718.64             1498.88              572.42              926.46           186529.81           251811.17
  180           177622.20             1498.88              607.73              891.15           197419.88           269797.68
  192           170088.07             1498.88              645.21              853.67           207872.26           287784.19
  204           162089.25             1498.88              685.00              813.87           217859.96           305770.70
  216           153597.09             1498.88              727.25              771.62           227354.30           323757.22
  228           144581.14             1498.88              772.11              726.77           236324.87           341743.73
  240           135009.11             1498.88              819.73              679.14           244739.35           359730.24
  252           124846.70             1498.88              870.29              628.58           252563.45           377716.75
  264           114057.49             1498.88              923.97              574.91           259760.76           395703.26
  276           102602.83             1498.88              980.96              517.92           266292.61           413689.78
  288            90441.67             1498.88             1041.46              457.42           272117.96           431676.29
  300            77530.43             1498.88             1105.70              393.18           277193.23           449662.80
  312            63822.86             1498.88             1173.89              324.98           281472.18           467649.31
  324            49269.84             1498.88             1246.30              252.58           284905.66           485635.82
  336            33819.22             1498.88             1323.16              175.71           287441.55           503622.34
  348            17415.63             1498.88             1404.77               94.10           289024.48           521608.85
  360                0.31             1498.88             1491.42                7.46           289595.67           539595.36
 ratio (total cost)/(house price) 2.1644

A few things to notice

Run the code, changing the interest rates (5,6,7,8%) and the monthly payment, to get a mortgage of 30,15,10 and 5yrs. Find the cost/month and total price paid/price of house at purchase. Here's my results.

Note

For some perspective: Low interest 30yr mortgages (2-4%) were common in Australia in the '50's. In the US, a good rate for 30yr mortgage, in the 1990-2000's has been 6%. In the US, the mortgage rates during the stagflation of the 1980s was upto 14%. Short term mortgages (3-5yrs) are common in Switzerland and Australia, but are not the norm for standard house buyers in the US In the US, car loans are for about 5yrs. In this case, divide all the above numbers by a factor of 10 (or so). The problem with taking out a car loan, it that the value of the car drops by 25% just driving it out of the car lot. You'll owe money on selling the car, right till the end of the car loan.

A few things to note (in the US a typical house mortgage is 30yrs, a typical car loan is 5yrs)

How does the interest paid on a mortgage make life easier for the plumber than for the Ph.D? The Ph.D. starts earning later (30yrs old) and is doing well to have paid off their house by the time they retire. Usually the Ph.D. has to move several times, and spends a lot of time paying off interest early in each mortgage. The plumber (hopefully) has a stable business, doesn't move and starts earning when they're 20. The plumber will own his house well before he retires.

Why is it possible to get a 30yr fixed rate mortgage in USA, whereas in other countries, 3-5yrs is the norm? How can banks in USA forecast the country's economy for 30 years into the future and know that they'll make a profit from the loan, whereas no bank in the rest of the world is prepared to make a loan for more that 3-5yrs? The answer is that the banks in USA are no more capable of predicting the economic future than anyone else. In USA, the banks know that the average person stays in their house for 5-7yrs and then has to move. Almost no-one in USA stays in their house for 30yrs. The 30yr fixed rate mortgage is really a 5-7yr mortgage. In the rest of the world, people don't have to move when their job changes, and the banks can't write mortgages for longer than they can forecast the state of the economy.

Similarly, in the US, credit card companies don't have annual fees on their standard credit cards. Why not? Enough people don't pay off their credit cards at the end of the month, incurring interest at rates of upto 37%. The interest on unpaid balances is enough to keep the credit card companies in good financial shape. In the rest of the world, people pay off their balance every month as so credit card companies charge annual fees for the credit card.

With people not trusting other forms of investment (e.g. the stock market), the pressure to buy a house forces up the prices of houses. If for any reason (lack of credit, downturn in the economy) people stop buying houses, then the price of houses crashes.

	Note
	I wish to thank my co-worker, Ed Anderson, for the ideas which lead to this (and the next few) sections.

In 1965 Gordon Moore observed that starting from the introduction of the integrated circuit in 1958, that the number of transistors that could be placed inexpensively on an integrated circuit had doubled about every 2yrs. This doubling has continued for 50yrs and is now called Moore's Law (http://en.wikipedia.org/wiki/Moore%E2%80%99s_law). Almost every measure of the capabilities of digital electronics is linked to Moore's Law: processing speed, memory capacity, number of pixels in a digital camera, all of which are improving at exponential rates. This has dramatically improved the usefullness of digital electronics. A (admittedly self serving) press release says that the new Cray at the CSC Finnish Center for Science (http://www.marketwire.com/press-release/Cray-Inc-NASDAQ-CRAY-914614.html) will take 1msec to do a calculation that the center's first computer, ESKO, installed half a century earlier, would have taken 50yrs to complete.

The conventional wisdom is that Moore's Law says that the speed of computers doubles every 2yrs, but Moore didn't say that; Moore's Law is about the number of transistors, not speed. Still the speed of computers does increase at the Moore's Law rate. What Moore is describing is the result of being able to make smaller transistors. A wafer of silicon has certain irreducible number of crystal defects (e.g. dislocations). Multiple copies (dozens, hundreds, thousands, depending on their complexity) of integrated circuits (ICs) are made next to each other in a grid on a silicon wafer. Any IC that sits over a crystal defect will not work and this will reduce the yield (of ICs) from the wafer driving up costs for the manufacturer. Since on average the number of defects in a wafer is constant, if you can make the ICs smaller, thus fitting more ICs onto the wafer, then the yield increases.

Transistors and ICs are built onto on a flat piece of silicon. What is the scaling of the number of transistors (or ICs) if you reduce the linear dimensions of the transistors by n ^[244] ? The thickness (from top to bottom looking down onto the piece of silicon) decreases by the factor of n too, but since you can't built transistors on top of each other (well easily anyway) you don't get any more transistors in this dimension.

One consequence of making ICs smaller, is that the distance that electrons travel to the next transistor is smaller. With the speed of light (or the speed of electrons in silicon) fixed, the speed of the transistors increased. As well the capacitance of gates was smaller, so that less charge (less electrons) was needed to turn them off or on, increasing the speed of the transition. Silicon wasn't getting any faster, just the transistors were getting smaller. Manufacturers were driven to make smaller transistors by the defects in silicon. The increase in speed was a very welcome side effect.

Let's return to the numerical integration method for calculating π to 100 places, which for a 1GHz computer would take about 10^100-9=91secs or 10⁷⁴*ages of the Universe, and see if Moore's Law can help. Let's assume that Moore's Law continues to hold for the indefinite future (we can expect some difficulties with this assumption; it's hard to imagine making a transistor smaller than an atom) and that for convenience the doubling time is 1yr. Now at the end of each year (31*10⁶=10^7.5secs), instead of allowing the calculation to continue, you checkpoint your calculation (stop the calculation, store the partial results) and take advantage of Moore's Law, by transferring your calculation to a new computer of double the speed. How long does your calculation take now?

Write code (moores_law_pi.py) that does the following

Here's my code ^[245] and here's the output.

pip:# ./moores_law_pi.py
elapsed time (yr)     1, iterations done 3.162278e+16

You now want your code to loop, with the speed of the machine doubling each year.

Here's my code ^[246] and here's the last line of my output.

elapsed time (yr)   278, iterations done 1.535815e+100

This is a great improvement; instead of 10⁷⁴ ages of the Universe, this only takes 278yrs. You can easily finish the calculation in the age of a single Universe and have plenty of time to spare.

50% more calculations were done than asked for, because we only check at the end of each year and we reached our target part way through the year. Assuming that the calculation (i.e. 10¹⁰⁰ iterations), finished exactly at the end of the year, when was the job half done ^[247] ? If you'd started the job at the end of the 278th year, how long would the job have taken ^[248] ?

If you have a process whose output increases exponentially with some external variable, then you don't start till the latest possible moment. In The Effects of Moore's Law and Slacking on Large Computations (http://arxiv.org/pdf/astro-ph/9912202) Gottbrath, Bailin, Meakin, Thompson and Charfman (1999) shows that if you have a long calculation (say 3 yrs) and in 1.5yrs time you will have computers of twice the speed, then it would be better from a productivity point of view to spend the first 1.5yrs of your grant surfing in Hawaii, and run the calculation at twice the speed in the 2nd 1.5yrs.

Boss: "Gottbrath! Where the hell are you and what are you doing?"

Gottbrath: "I'm working sir!"

If you purchase a computer with speed as a requirement, you don't purchase it ahead of time (like 6 months or a year ahead) as it will have lost an appreciable fraction of its Moore's Law speed advantage by the time you put it on-line. With government computer procurements taking a year or so, there is no point in comparing computers with a 25% speed difference; they will lose half their speed while waiting for the procurement process to go through.

Interstellar space travel will take centuries, while back on earth there will be exponential improvements in technology. The result of this will be that the first party to leave on an interstellar trip will be overtaken in 100yrs time by the next party. Figure 1 in the Gottbrath paper shows the effect of delaying starting a job, when the computers double in speed every 18months (Moore's Law time constant). The jobs starting later all overtake the early jobs. This graph could be relabled "the distance travelled through space by parties leaving earth every 5 months", using the exponentially improving (doubling every 18mo) space travel technology. The curves all cross eventually. The first party to arrive at the interstellar destination will be the last to leave. Thus the futility of interstellar space travel.

Since this is a computer class, I had you write a computer program to calculate the time taken for the Moore's Law improvement on the π calculation. However you could have done it your head (a bit of practice might be needed at first). The speed of the Moore's Law computer as function of time is a Geometric Progression (http://en.wikipedia.org/wiki/Geometric_sequence). Example geometric progressions:

1,2,4,8,16,64

1,0.5,0.25,0.125...

A geometric series is characterised by the scale factor (the initial value, here 1) and the common ratio (the multiplier) which for the first series is 2, and for the 2nd series is 0.5. Geometric progressions can be finite, i.e. have a finite number of terms (the first series) or infinite, i.e. have an infinite number of terms (the second series). When the common ratio>1, the sum of an infinite series diverges (exponential growth), i.e. the sum becomes infinite; when the common ratio<1, the sum of an infinite series converges (exponential decay), i.e. the sum approaches a finite number.

example: exponential growth: What is the sum of the finite series 1+2+4+...+128 (hint: reordering the series to 128+64+...+1=11111111₂=0xff=ffh) ^[249] ? What's the sum of the finite series: 2⁰+ 2¹+ 2²+...+ 2^{31 [250]} ? What is the sum of the finite series 10⁰+10¹+10^{2 [251]} ?

example: exponential decay: (from rec.humor.funny http://www.netfunny.com/rhf/jokes/08/Nov/math_beers.html) An infinite number of computer programmers go for pizza. The first programmer asks for a pizza, the next programmer asked for half a pizza, the next for a quarter of a pizza... The person behind the counter, before waiting for the next order yells out to the cook "x pizzas!" (where x is a number). What was the value of "x" (what is the sum of the infinite series 1+0.5+0.25+...) ^[252] ? The question rephrased is "what is the value of 1.111111..₂?"

Let's derive the formula for the sum of a geometric series

sum = ar^0 + ar^1 + ar^2 + ... + ar^n

where r=common ratio (and r⁰=1); a=scaling factor. Multiplying all terms by r and shifting the terms one slot we notice

  sum = ar^0 + ar^1 + ar^2 + ... + ar^n
r*sum =        ar^1 + ar^2 + ... + ar^n + ar^(n+1)

Can you do something with these two lines to get rid of a whole lot of terms (this process is called telescoping)? Hint ^[253] . This leads to the following expression for the sum of a geometric series (for r!=1).

sum = a(r^(n+1)-1)/(r-1)

(For r<1, you can reverse the order of the two terms in each of the numerator and denominator.) Using this formula what is the sum of the finite series 1+2+4+8+...+128 ^[254] ?

From the formula, what is the sum of the infinite series 1+1/10+1/100+ ... ^[255] ? Note: the sum can be written by inspection in decimal as 1.111.... although it's not so obvious that this 1/0.9.

From the formula, what is the sum of the infinite series 1+2/10+4/100+ ... ^[256] ?

From the formula, show that the sum of an infinite series, with (r<1) is always finite ^[257] .

Note

The version of the story quoted here comes from George Gamow's book "One Two Three...Infinity". The book came out in 1953 and is still in print. It's about interesting facts in science and I read this book in early high school (early '60's). In 2008 I still find it interesting. When I first looked up this story, I saw it in the book on π (and not from Gamow's book), where I found that the grain involved was rice and I did my calculations below on the properties of rice. It seems that the original story was about wheat. Rather than redo my calculations, I've left the calculations based on the properties of rice (the answer is not going to be significantly different).

According to legend, the inventor of chess, the Grand Vizier Sissa Ben Dahir was offered a reward for his invention, by his ruler King Shirham of India. The inventor asked for 1 grain of rice for the first square on the board, 2 grains of rice for the 2nd square on the board, 4 grains for the 3rd square... The king, impressed by the modesty of the request, orders that the rice be delivered to the inventor. (For a more likely history of chess see history of chess http://en.wikipedia.org/wiki/Chess#History.) How many grains of rice will the inventor receive ^[258] ?

If the Royal Keeper of the Rice counts out the grains at 1/sec, how long will he take (in some manageable everyday unit, i.e. not seconds) ^[259] ? Clearly the inventor would prefer not to have to wait that long, but understanding exponential processes, it's likely that he'll suggest to the Royal Keeper of the Rice that for each iteration, that an amount of rice double that of the last addition be added to the pile (this is not part of the legend). How long will it take the Royal Keeper of the Rice to measure out the rice now ^[260] ? The lesson is that if you handle exponential processes with linear solutions, you will take exponential time (your solution will scale exponentially with time); if you have exponential solutions, you will take linear time (your solution will scale linearly with time). (Sometimes exponential solutions are available e.g. the factorial series for π, sometimes they aren't.)

How high is the pile of rice? First we'll calculate the volume. To find the height, we need to know the shape of the pile. The rice will be delivered by the Royal Conveyor Belt and will form a conical pile. The formula for the volume of a cone is V=πr²h/3. The only variable for a cone of grains, poured from one point above, is the angle at the vertex, which will allow us to find the height of the pile of known volume.

The height of the pile can be done as a back of the envelope calculation. It doesn't have to be exact: we just need to know whether the answer is a sack full, a room full, or a sphere of rice the size of the earth. We have the number of grains; we want the volume. There's some more data we need. We can lookup the number of grains in a bag of rice. Rice is sold by weight. Knowing the weight, we can calculate the number of grains/weight. However we want the number of grains/volume, so we need the weight/volume (the density) of rice. Going on the internet we find the missing numbers

We want volume/number; we have the weight/volume (let's say relative density is 0.75) and the number/weight (60,000/kg). How do we get what we want? Using dimensional analysis, the dimensions on both sides of the equation must be the same.

volume/number= 1.0/((number/weight)*(weight/volume))	#the dimension of weight cancells out
units?       = 1.0/( number/kg     * kg/m^3 )
             = 1.0/( number/m^3 )
             = volume/number

volume/grain = 1.0/(60000*750)

The units of our answer are going to be in the units of the quantities on the right, i.e. m^3/grain
pip:# echo "1.0/(60000*750)" | bc -l
.00000002222222222222	#m^3/grain

Let's turn this into more manageable units, 
by multiplying by successive powers of 10^3 till we get something convenient.

pip:# echo "1.0*10^9/(60000*750)" | bc -l
22.22222222222222222 	#nm^3/grain (nano cubic metres/grain)

Can we check this number to make sure we haven't gone astray by a factor of 10³ or so? What is the side of a cube of volume 1 n(m³) (this is a cube of volume 10^-9 cubic metres, not a cube of side 1nm=10^-9m.)? The length of the side is cuberoot(10^-9m³)=10^-3m=1mm. A rice grain, by our calculations, has a volume of 22 cubes each 1mm on a side. Does this seem about right? We could make the volume of a grain of rice, by lining up 22 of these volumes in a line (11mm*1mm*1mm) or 20 of them by lining up 5mm*2mm*2mm. This is about the size of a grain of rice, so we're doing OK so far.

We've got 2⁶⁴ of these grains of rice. What's the volume of the rice ^[262] ? What's the weight of this amount of rice using density=0.75tons/m^{3 [263]} ?

The next thing to be determined is the shape of the cone. Mathematicians can characterise a cone by the angle at the vertex. For a pile of rice (or salt, or gravel), in the everyday world, the angle that's measured is the angle the sloping side makes with the ground (called the angle of repose http://en.wikipedia.org/wiki/Angle_of_repose). If the rice is at a steeper angle, the rice will initiate a rice-slide, restoring the slope to the angle of repose. A talus (scree) slope is a pile of rocks at its angle of repose. A talus slope is hard to walk up, as your foot pressure pushes on rocks which are at their angle of repose. Your foot only moves the rocks down the slope and you don't get anywhere (see the photo of scree http://en.wikipedia.org/wiki/Scree). An avalanche is caused by the collapsing of a slope of snow at its angle of repose. A sand dune (http://en.wikipedia.org/wiki/Dune, look at the photo of Erg Chebbi) in the process of building, will have the downwind face at the angle of repose for sand (this will be hard to walk up too).

Rice still with its hulls forms a conical pile with an angle of repose of about 45° (for image see rice pile crop http://www.sas.upenn.edu/earth/assets/images/photos/rice_pile_crop.jpg). For hulled rice (which the inventor will be getting) the angle of repose The Mechanics and Physics of Modern Grain Aeration Management is 31.5° or Some physical properties of rough rice (Oryza Sativa L.) grain. M. Ghasemi Varnamkhastia, H. Moblia, A. Jafaria, A.R. Keyhania, M. Heidari Soltanabadib, S. Rafieea and K. Kheiralipoura 37.66 and 35.83°.

For convenience, I'm going to take an angle of repose for rice of 30°. What is the relationship between the radius and height of a cone with angle of repose=30°?

We need to take a little side trip into trigonometry. Come back here when you're done.

The formula for the volume of a cone (V=πr²h/3) involves the height and the radius. When you make a cone by pouring material onto the same spot, the height and radius of the cone are dependant (i.e. they are always determined by the angle of repose). In this case, we can use a formula for the volume of a cone that uses either the radius or the height, together with the angle of repose.

If we know the angle of repose, what is the trig function that tells us the ratio of the height to the radius of the cone ^[264] ? Let's say tan(angle_repose)=0.5 then

h = tan(angle_repose)*r
h = 0.5*r

substituting this relationship into the formula for the volume of a cone gives
V = pi*r^2*0.5*r/3
  = 0.5*pi*r^3/3

in general terms
V  = pi*tan(angle_repose)*r^3/3 

What is the ratio height/radius for a cone with an angle of repose of 30° (you can do this with a math calculator or with python)? Python uses radians for the argument to trig functions. You turn radians into degrees with degrees() and degrees into radians with radians().

dennis:/src/da/python_class# python
Python 2.4.3 (#1, Apr 22 2006, 01:50:16) 
[GCC 2.95.3 20010315 (release)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from math import *
>>> radians(30)
0.52359877559829882
>>> degrees(0.52359877559829882)
29.9999999999999996	#note rounding error in last place in real representation
>>> tan(radians(30))
0.57735026918962573
>>> 

For a cone of rice, h/r=0.577. For a back of the envelope calculation we can make h/r=0.5 (or even 1.0; it's not going to make much difference to the height of the pile of rice). If you want a more accurate answer, you can come back later and use the real numbers. What angle has tan(angle)=0.5 ^[265] ? It's somewhere between 26 and 27° The inverse trig functions allow you to find the angle for which a number is the tan(). The inverse of tan() is called either tan^-1(), arctan() or atan() (the name in python).

>>> atan(0.5)
0.46364760900080609	#angle in radians
>>> degrees(atan(0.5))
26.56505117707799	#angle in degrees

giving an angle of repose of 26.5°

The cone of rice, from its angle of repose (in the section on trigonometry), has r=2h. For such a cone V=πr²h/3=(4π/3)h³. If the rice is presented to the inventor as a conical pile of rice, what is its height ^[266] ? For comparison, how high do commercial airliners fly ^[267] ? How high is Mt Everest ^[268] ?

The radius of the cone of rice with an angle of repose of 30° is twice the height. What is the diameter of the base of the pile of rice ^[269] ?

What is the world's annual production of rice (look it up with google)? How many years of the world's rice production would be needed for the reward ^[270] ?

Let's go back to the program which calculated the time to determine the value of π, when the computer speed increased with Moore's Law. The number of iterations/yr is a geometric series with scaling factor=10^7.5*10^9=10^16.5, common ratio=2. You didn't need to write a program to calculate the sum. Using the formula for the sum of a geometric series, what is the sum of n terms of this geometric series ^[271] ? What is n if sum=10*100? You will need a calculator - python will do. Make a few guesses about x to calculate values for 2**x/10**83.5 which in turn will give the expected number of iterations. Here's my calculation ^[272] . The answer is that you will need 277 years of calculating, with the value for π arriving at the start of the 278th year.

	Note
	If you know logs: pip:~# echo "83.5*l(10)/l(2)" | bc -l 277.38 ie 10**83.5=2**227.4

(I haven't been clear about the fencepost problem. You now need to decide if the answer is 277 or 278 years.)

Let's differentiate wealth and money

Where does money come from? As Galbraith says ("The Age of Uncertainty, John Kenneth Gailbraith (1977), Houghton Miflin, ISBN 0-395-24900-7 - anything by Galbraith is worth reading, not only for the substance, but for the style in which he communicates) on p 167, it's created from nothing.

Galbraith credits the mechanism for the creation of money to the Amsterdam bankers (bottom of p 166) in 1606, although the principle was known earlier. The theory of the creation of money (multiplication) is a standard part of Macroeconomics. The best description I found on the web is at The Banking System and the Money Multiplier (http://www.colorado.edu/Economics/courses/econ2020/section10/section10-main.html), which I'm using here.

Banks make loans, from which they earn interest. This is obvious to everyone. In the process, banks also create money. How this works is not quite so obvious. Let's assume that everyone banks in the same or linked banking system (for convenience, let everyone bank at the same branch of a bank). Warren Buffett deposits 1M$ in the bank. The bank has an asset of 1M$ and a liability to Warren Buffett of 1M$. Let's look at the bank's balance sheet.

Programmer's Bank of N.C.

  Assets	                 Liabilities
  D    C                          D    C
-----------                      -----------
 1M  |       cash                    | 1M    Warren Buffett

Note

Double entry accounting rules: Each block here is called an account. In this case, the bank has an asset account and a liability account. When money moves, the same amount of money must appear in two accounts, in opposite columns. In accounting, the left hand column is called "debit" and the right hand column "credit". These two names are just opposite labels, like positive and negative, up and down, left and right. You always have credits and debits in equal amounts. In accounting money is not created or destroyed. It just moves. For more about accounting see Gnucash and Double Entry Accounting (http://www.austintek.com/gnucash/).

The bank has 1M$ on hand in cash and has a liability to (owes) Warren Buffett 1M$.

Note

The bank's net worth is $0 However they have 1M$ cash on hand, which they can use to make money. As long as the bank makes enough money to pay Warren Buffett his monthly interest (which will confirm his wisdom in choosing to leave his money with this bank), the bank stays in business. Warren Buffett is in no hurry to close out his account (retrieve his money). Surprisingly much of the economy (people, businesses) has little net worth or is in debt and everyone has agreed that this is just fine. I started off with a 5% down mortgage, where I was in debt to the tune of 95% of the value of my house. Many businesses have receive and pay out money at different rates throughout the year; sometimes having lots of cash and sometimes having less than none. These businesses have a line of credit with a bank, to even out the money flow, allowing them to make payroll and expenses at all times of the year. Of course you have to pay interest on the loans, but it makes the business possible, and allows people to buy a house rather than rent. Let's say the bank makes some really bad decisions and looses all of Warren Buffett's money. Who's in trouble? Not the bank - they have no money. What about the bank's officers? Their houses and personal money aren't involved in the bank. Only Warren is in trouble. He's lost 1M$. Admittedly, the bank's officers won't be able to show their faces in town (they'll leave), but that's about as bad as it gets. In the US there's no moral outrage about this sort of thing. The bank's officers, using the same skills they used to convince you to deposit your money with them, will get jobs somewhere else. To handle this situation, in the US, the FDIC insures the depositor's money, so that in the event of a bank forfeiture, the FDIC will reimburse you for the lost amount. For this to work, the FDIC has to keep tabs on the bank's accounts and track what they're doing. The bank has to pay the FDIC for their work, and so that the FDIC has enough money to handle any forfeitures (i.e. insurance). Once this has been setup, the bank can hang the FDIC sign in their window. In the last few years, with no forfeitures since the S&L scandal (only 20yrs ago), Congress decided to stop levying this charge against the banks. (Congress and the banks were good mates you understand, and the banks long ago had stopped being bad boys. Congress wanted to help the economy with reduced regulation, which as everyone knows, increases honesty and transparency in business.) As a result, with the credit and bank implosion in late 2008, the FDIC found it had no money socked away to handle the bankruptcies. Where did the money come from? Congress took it from the taxpayers (definitely not the banks).

What's the bank going to do with Warren's money? If they just let it sit in the vault, there won't be any income for the bank. The bank has to pay salaries, expenses, and to Warren Buffett, interest. To cover expenses and earn money, the bank loans out the money for which it charges interest. They don't loan all of it out. In the US, the Federal Reserve (the "Fed") decrees that the bank must hold 10% of their deposits in reserve, against possible withdrawals by customers. The bank deposits the required amount with the Federal Reserve (earning a small amount of interest). Let's look at the bank's balance sheet now.

Python Programmer's Bank of N.C.

  Assets	                 Liabilities                   Federal Reserve 
                                 (deposits)                        Escrow 
  D    C                          D    C                           D   C
-----------                      -----------                   -------------
 1M  |       cash                    | 1M    Warren Buffett          |
     |  0.1M                         |                          0.1M |    

The bank has 0.9M$ available to make loans. For simplicity, let us assume that the entire $900,000, made available by Warren's deposit, was borrowed by one business: Joe the Plumber. Joe the Plumber doesn't borrow the money for fun, he wants to invest in new capital equipment, to increase the productivity of his workers. Joe the Plumber wants to invest in a new laser rooter, for which he pays $900,000 to Sapphire Slick's Laser Emporium. Let us also assume that Sapphire has an account with the Python Programmer's Bank, where she deposits the $900,000 received from Joe the Plumber's purchase. The bank deposits 10% of Sapphire's deposit with the Fed. Here's the accounts at the Python Programmer's Bank after Sapphire's deposit.

Python Programmer's Bank of N.C.

  Assets	                 Liabilities                   Federal Reserve         Loans
                                 (deposits)                        Escrow 
  D    C                          D    C                           D   C               D    C
-----------                      -----------                   -------------         -----------
1.0M |                               |1.0M Warren Buffett            |                   |
     |  0.1M                         |                          0.1M |                   |
     |  0.9M                         |                               |              0.9M |   Joe the Plumber
0.9M |                               |0.9M Sapphir Slick             |                   |   
     |  0.09M                        |                          0.09M|                   |   

Total:
0.81M                                 1.9M                      0.19M               0.9M

The bank now has assets of 0.81M$ (with 0.19M$ in the Fed escrow account). It has issued a loan for 0.9M$ to Joe the Plumber (there is now 0.9M$ injected into the business world). However the bank now has deposits of 1.9M$ (it also has liabilities of 1.9M$). The bank has an extra 0.9M$ on deposit, which it can use to make more loans. Let's say the bank now issues a loan of 0.81M$ to another business, which buys equipment or has work done for it and the contractor deposits the money back in the Python Programmer's bank. And this goes on till the bank's assets are reduced to 0$. How much money is on deposit at the bank, how much money is in the Fed escrow account and how much money has been loaned out to businesses?

Loans (M$): 
0.9 + 0.81....
= 1(0.9^1+0.9^2+...)
using the formula for the sum of a geometric series
S=a(1-r^n)/(1-r)
= 0.9 * (1-0.9^inf)/(1-0.9)
= 9.0M$

The amount of money that's loaned out is the original amount of money put into circulation by the first loan, divided by the Federal Reserve ratio (the 1-0.9 term).

the money multiplier = 1/reserve_ratio

The amount of money on deposit is 10.0M$ (9.0M$ + original deposit), and the amount of money in the Federal Reserve is 1.0M$.

	Note
	The bank has no money as reserves (in case anyone wants to withdraw money) (the bank will usually not lend out all its money).

Here's the bank's accounts when all of the money has been loaned out

Python Programmer's Bank of N.C.

  Assets	                 Liabilities                   Federal Reserve         Loans
                                 (deposits)                        Escrow 
  D    C                          D    C                           D   C               D    C
-----------                      -----------                   -------------         -----------
1.0M |                               |1.0M Warren Buffett            |                   |
     |  0.1M                         |                          0.1M |                   |
     |  0.9M                         |                               |              0.9M |   Joe the Plumber
0.9M |                               |0.9M Sapphir Slick             |                   |   
     |  0.09M                        |                          0.09M|                   |   
     .                               .

Total:
0.0M                                  10.0M                      1.0M               9.0M

Notice we started with a deposit of 1M$ and when the process is finished, the bank has 10M$ in deposits, with 9M$ in loans and 1M$ in the Federal Reserve. Was any wealth created ^[273] ? Was any money created ^[274] ?

In reality there are a number of leakages from the above scenario, that will reduce the value of the multiplier:

The multiplier effect works in all sectors of the economy. You buy a self levitating mouse for your computer; the clerk at the store, the store's owner, the truck driver who delivered the mouse, the factory that made the mouse, the guy that designed the mouse, all get money. These people in turn go to stores and buy Homer Simpson towels... and on it goes. The circulation of money maintains the economy (at least in the US) and leads to Fisher's concept of the velocity of money Quantity theory of money (http://en.wikipedia.org/wiki/Quantity_theory_of_money), which is a bit outside the scope of this course.

What's needed to maintain this system of creating money

As Galbraith says on p167 in the above reference

The creation of money by a bank is as simple as this, so simple, I've often said, the mind is repelled.

The important thing, obviously, is that the original depositor and the borrower must never come to the bank at the same time for their deposits - their money. They must trust the bank. They must trust it to the extent of believing it isn't doing what is does as a matter of course.

While we may think of banks as just safe places to store our extra money, their main role in the economy is to make loans. If they stop making loans, the amount of money in circulation drops by a factor of 10. Credit worthy people can't get loans to buy a house, people who move and want to sell their houses can't, but still have to keep paying the mortgage on their empty house, businesses can't meet payroll or pay for the goods they need to buy to stay in business. The economy goes into a death spiral, with people being laid off and defaulting on their mortgages, businesses fail, people default on their loans and the banks have even less money to make loans.

The multiplication feature of the creation of money means that any small changes in the economy are greatly magnified. If people stop spending money, or banks stop making loans, the amount of money in circulation drops drastically. Businesses can't pay their bills, people loose their jobs and can't pay their mortgage, which means that the banks loose money on their bad loans and can't make more loans. Then in good times, the economy swings the other way. For people trying to go about their lives, as my friend Tony Berg says, the worst thing is change. You can plan your life if you know the rules, even if they aren't great rules, but if one day after making all your plans, someone comes and says "we've changed the rules, the multipliers, the interest rates...", your plan goes out the window. The multiplication factor and the amount of money in circulation needs strict monitoring, or the economy will go through booms and busts, causing havoc and disruption in the lives of innocent people, who are just trying to work hard and get their jobs done. When you hear newspapers/commentators talking about the US economy being a vibrant innovative place, where people can take risks and reap the rewards, what they're talking about is an economy with large swings where a small number of people (those with the money) can make a packet and get out, while the expendable workers suffer lives of great disruption. However the newly unemployed will have a chance to be the first to buy the next iPod.

One of the critical features of this system is the reserve ratio. The banks are always pressing to reduce the amount of money they have to deposit with the Fed. If this is reduced to 5%, then the banks can loan out twice the amount of money, and earn twice as much interest. The problem here is that there may not be enough demand for the extra money from credit worthy people, in which case the banks will have to start chasing people who are less credit worthy. This got a lot of banks into trouble in the US credit crunch of 2008.

We're all told that saving is a good thing (a penny saved is a penny earned etc - who said this ^[275] ?). Note that personal saving derails the system here, by taking money out of the multiplication spiral. Economics text books are full of examples of the type "If you do X, what effect will this have on you, have on the economy? If everyone does X, what effect will this have on you, have on the economy?" In some of these an activity done by one or by everyone is good (e.g. working hard), while another activity (e.g. preparing a good resume, so you will get a particular job) is good for you, but you wouldn't want to hand around your resume to all the other applicants. You need to know what's good for you and what's good for the economy. Sometimes they're the same; sometimes they're the opposite.

It turns out that saving is good for you, but just not good for the economy, at least in the sense discussed above. After 9/11, George Bush told the US to go shopping (to keep the economy rolling), when he should have told the country to tighten its belt.

The US credit crunch of 2008 was caused by banks making home loans to people who didn't have a good enough credit rating for standard (prime) rate mortgage. Instead these people were given a sub-prime mortgage, with a higher interest rate to handle the risk that the mortgagee would default. The only reason that lending money to high risk mortgatees worked was because at the same time there was a house price bubble (house prices were rising faster than their real worth). When people defaulted, the increased value of the house covered the bank's costs. As well the defaulter would get back some money from the sale of the house. Previously no-one would touch these high risk people, but with the house prices rising, some banks decided it was worth the risk and these banks made a packet writing sub-prime mortgages. Eventually the house price bubble burst. When house prices decreased with the purchase value of the house, and mortgagees defaulted, banks with outstanding loans now had a lot of bad loans and the mortgagees went bankrupt.

The initial problem, in the credit crunch, was that banks no longer had money to make loans. Businesses who weren't a part of the sub-prime mortgage problem, weren't able to make their payroll, make planned purchases, even though their businesses were being conducted to the highest standards. The problem became obvious to people who read newspapers in the middle of 2007.

Here are the players involved

The people who were running the economy about Sept 2008 realised there was a problem. (these were Henry Paulson and Ben Bernanke. Alan Greenspan had retired and expressed profound disappointment that his perfectly working scheme had been derailed by human greed. Quite reasonably, Greenspan was not held responsible for the consequences of his incompetence.)

With what you know now, you're qualified to solve the problem. To make it easier, I'll make it multiple-guess. What would you do (you can choose more than one answer)? While you're at it, what do you think Congress did?

Even though they'd watched mesmerised as the whole economy sank, the US Congress in Oct 2008, decided that they were the best people to fix the problem and gave Paulson and Bernanke, 700G$ of the tax payers money (how much more does each person in the US owe the government as a result of this decision ^[277] ?) to do whatever they liked to fix the problem. The plan was to give this money to the banks who were in trouble to use in whatever way they wanted. It was clear to even the uneducated, that there was no hope that this would work. The banks used the money for weekend parties and retreats, to pay off debts to other banks and to give bonuses to the executives. Guess how much of the 700G$ that the goverment required to be used for loans ^[278] ? After receiving 85G$ from the taxpayers, AIG held a week long party at an expensive resort (AIG) costing 500k$ (see AIG bailout means facials, pedicures http://blogs.moneycentral.msn.com/topstocks/archive/2008/10/07/aig-bailout-means-facials-pedicures.aspx). to make sure that the taxpayers know the contempt in which they are held by the financial industry. Not wishing to miss the party, the Detroit auto makers arrived in private jets to plead their special poverty. Six weeks later (mid Nov 2008), after spending 350G$ of the money without the slighest effect, Paulson admitted that the plan wasn't working. He was adamant that the money should be used to bailout the banks (an investment) rather than prevent mortgage forclosures (an expense). Paulson changed tactics - he would send the remainder to credit card companies. How much money was going to people who needed loans ^[279] ? This is being written in mid Nov 2008, when the results of this new move aren't in. My prediction, as a newspaper reading non-economist, is that the new plan will not work any better than the earlier plan.

If you're like me when I was growing up, you'd say "these are a bunch of idiots. I can see what's wrong already, I'm going to have no problem getting a job, kicking these people out and fixing the whole situation up." You're wrong.

The futility of trying to establish a meritocracy can be seen in the failure of Plato's "The Republic". If you're good in school, your elders and betters will say "we want bright energetic people like you". They'll give you prizes at the end of the year. You'll wind up is working for them, in an assembly line (you may not be assembling cars, but you'll be in an assembly line none the less). The pinacle of achievement is a Ph.D. You work for 5yrs, at no pay, to help your supervisor, who will get tenure out of your (and other student's) work. At the end of it, you get a piece of paper which tells the world "this person will work for 5 yrs at no pay, for a piece of paper saying that they're really smart". Employers love to see people like this come in the door for job interviews. Ask your professors for advice in University: "of course you should take my course; there's a bright future in this field, otherwise I wouldn't be in it". Don't ask anyone, who has a vested interest in the outcome, for advice (OK ask them, but be careful of taking it). While a Ph.D. is a requirement for entry into many fields, make sure that the time spent on it is on your terms and not just to help the career of others.

So why won't you get Paulson's job? You know what's wrong, know what needs to be done and you know that they're a bunch of idiots. These people see you coming. They have comfortable jobs, they aren't held accountable for their blunders and aren't required to deliver results. Their pronouncements are greeted with fauning and adulation by Congress. Are they going to be glad to see you walk in the door ^[280] ? You'll be greeted with the same applause that's followed you since grade school. They'll find something special for a person like you and you won't realise till long afterwards, that you wasted your time. They'll do everything they can to crush you from the very start. If you want to fix up the situation, you'll have a life like Martin Luther King Jr, Jonas Salk or Ralph Nader.

Financial people who made it, not playing along with the system, but using its weaknesses for their own profit, include Warren Buffet and Jeremy Grantham, both of whom seem to have had comfortable lives.

Early on you'll need to choose between the life of Henry Paulson and Alan Greenspan, with public adulation on one hand, or the life of Jonas Salk on the other hand, who cured the world of polio, but who was regarded as a technician by the scientific community, and who had to raise all the money for his cure himself (through the March of Dimes). Salk wasn't even admitted as a member of the National Academy of Science (neither was the educator and populariser of science Carl Sagan). Richard Feynman resigned from the Academy, seeing it as a club of self congratulatory incompetents (my words not his).

If you want to set things right, competence in your field is necessary, but not sufficient. The frontier will be the idiots, not your chosen field of endeavour. As Frederick Douglass said

"Power concedes nothing without a demand. It never did and it never will."

As I said earlier, if you have problems that scale exponentially, to solve them in linear time, you need tools that scale exponentially. If your tools scale linearly, you need exponential time to solve the problem.

One attempt to increase the amount of computing power is parallel programming. You divide a problem into smaller pieces, send each piece off to its own cpu and then to merge/join/add all the results at the end. It turns out that dividing problems into subproblems and joining the partial results doesn't scale well. Much of the time of the computation is spent passing partial answers back and forth between cpus. As well the cost of cpus scales linearly (or worse) with the number of cpus. So parallel programming is a linear solution, not an exponential solution.

When a client on the internet connects to a server on the internet, the client first sends a request to connect (called a SYN packet). This is the tcpip equivalent of ringing the door bell (or the phone). The server replies (SYN-ACK) and the client confirms the connection (ACK). The client then sends its request (give me the page "foo.html"). A DDoS is an attack on a machine (usually a server for a website), where so many (network) packets are sent to the server, that it spends all its time responding to DDoS packets (answering the door to find no-one there), and is not able to respond to valid knocks on the door. The machine doing the DDoS only sends the SYN packet. The server replies with the SYN-ACK and has to wait for a timeout (about 2mins) before deciding that the client machine is not going to connect. There is no way for the server to differentiate a DDoS SYN packet from a packet coming from a valid client on the internet.

DDoS machines are poorly secured machines (Windows) than have been taken over (infected with a worm) by someone who wants to mount an attack on a site. The machines are called zombies and once infected, are programmed to find other uninfected machines to take over. The process of infecting other machines is exponential or linear ^[281] ? The zombies sit there appearing to be normal machines to their owners, until the attacker wants to attack a site. The attacker then commands his zombies (which can number in the millions) to send connect requests to a particular site, taking it off the network. All the zombies in the world are Windows boxes linked to the internet by cable modems. It takes about 20 mins after an unprotected Windows box is put on the internet for it to be infected by one of these worms.

Note

For the information on the navigation required for this feat, I am indebted to "Portnoy's Imponderables", Joe Portnoy, 2000, Litton Systems Inc, ISBN 0-9703309-0-1. available from Celestaire (http://www.celestaire.com/). Table 4 on p 33 showed how lucky Lindy was. This book has tales of great navigation for those who have to sit at home, while everyone else is out in their boat having the real fun. Celestaire has all sorts of nice navigational equipment. Other information comes from Lindbergh flies the Atlantic http://www.charleslindbergh.com/history/paris.asp), Charles Lindbergh, (http://en.wikipedia.org/wiki/Charles_Lindbergh), Orteig Prize (http://en.wikipedia.org/wiki/Orteig_Prize), Charles Lindbergh (http://www.acepilots.com/lindbergh.html) table of full moons (http://home.hiwaay.net/~krcool/Astro/moon/fullmoon.htm)

Following a run of bad weather, a forecast on 19 May 1927 predicted a break in the rain. At 7:20AM on 20 May 1927, 4 days after the full moon, an unknown air mail pilot, Charles Lindbergh, in pursuit of the $25k Orteig Prize for the first transatlantic flight between New York and Paris, slowly accelarated his overloaded (2385lb gasoline) single engine Ryan monoplane, northward down the boggy runway at Roosevelt field, clearing the power lines at the end of the runway by only 20'. To save weight Lindbergh carried no radio, no sextant and only carried a compass (accuracy 2°) and maps for navigation (but presumably having an altimeter and airspeed indicator). The plane had no brakes, and the plane was so filled with fuel tanks that Lindbergh had to view the world outside through a periscope.

Six people has already died in attempts on the Orteig prize. Two weeks earlier, Nungesser and his navigator, who planned to fly through the moonless night, left Paris in an attempt to reach New York and were not seen or heard of after they crossed Ireland. Six months earlier, leaving from the same Roosevelt field, Fonck and two crew members, never got off the ground, when the landing gear of the grossly overloaded (by 10,000 lbs) transport biplane collapsed during takeoff. The two crew members (but not Fonck) died in the subsequent inferno.

Lindbergh made landfall at Nova Scotia, only 6 miles off-course and headed out into the Atlantic as night fell. Lindberg had marked up his Mercator Projection map into 100mile (approximately 1hr flying time) segments of constant magnetic heading. He hand pumped fuel from the tanks inside the plane to the wing tanks. He alternately dodged clouds, which covered his wings with sleet (what's the problem there ^[282] ?) by flying over them at 10,000 ft or going around them. At one stage Lindbergh thought of turning back, but once half way, it was easier to keep going. His hope to use the full moon for illumination, did not pan out (what's the problem here ^[283] ?). To gauge windspeed, Lindbergh flew 20' over the wavetops, looking at the direction of spray and intensity of the whitecaps (how does this help ^[284] ?).

Sunrise on the second day came over the Atlantic with Lindberg arriving over the southern tip of Ireland in the late afternoon, after 1700miles and almost a day of ocean, only 3 miles off-course, a incredible directional error of only 0.1°. The adverse weather had put him an hour behind schedule, and considering the errors in estimating drift from the waves, magnetic variation and the inherent error in the compass, he should have been 50 miles off course. He crossed into Europe as the second night fell, arriving in Paris at 10pm. Amazingly his imminent arrival had been signalled from Ireland, with 150,000 people waiting at Le Bourget field to greet him.

Considering there was no internet, few phones or cars back then, Paris notified and moved 150,000 people by public transport in a few hours, a feat that be impossible in most American cities even today. Would you believe your neighbour pounding on the door "Vite! Lindbergh arrivera au Bourget a 2200hrs!" while you're relaxing having dinner and reading Le Figaro? No way. I would have stayed at home. My neighbour would have fumed (in a John Cleese voice) "You stupide Frenchman!"

The whole world went gaga. Lindbergh was a hero. In my lifetime, the big event was Armstrong landing (and returning) from the moon. But all of us watching the great event on TV knew we wouldn't be landing on the moon. With Lindbergh's flight, people realised that anyone would be able to fly across oceans.

Lindbergh was aggrieved by the considerable number of people who declared his accomplishment just luck. Let's see how lucky he was. As a person who's read just about every story of adventure and exploration that's been printed and has spent a large about of time hiking in the outdoors, you need to know the difference between a successful trip/expedition and an unsuccessful one:

What determines whether the trip is going to be successful or not? The difference between a successful trip and an unsuccessful trip is (ta-dah... drum roll): good planning and preparation. That's it - that's all you need to know. Most of the dramatic adventures that are burned into society's conciousness about how we got to be where we are, the nature of bravery and heroism, and what we pass on to the next generation as important lessons, are nothing more than examples of really bad planning. The un-newsworthy successful trips that should be the focus of our learning are ignored.

To see if Lindy was lucky, we have to look at the preparations he made.

The main risk factor in a 33.5hr, 3,150nmi flight over ocean, is engine failure. Lindbergh selected the highly reliable Wright Whirlwind J-5C engine. Back then (1927) "highly reliable" meant a complete failure (the plane won't fly) every 200hrs (MTBF, mean time between failure = 200hr). A new car engine by comparison can be expected to run for 2000hrs or more (with oil changes etc) without failing. (A car engine doesn't have to be light, like a plane engine. A plane engine will only have just enough metal to hold it together.) Interestingly, 15yrs later in WWII, plane engines still only had the same MTBF. By then a plane (and the pilot) was expected to have been shot down by the time it had spent 200hrs in the air. It wasn't till the reliable jet engine arrived, that commercial passenger aviation became safe and cheap enough that the general populace took to it.

The failure rate of many devices follows the bathtub curve (http://en.wikipedia.org/wiki/Bathtub_curve). There is an initial high rate of failures (called infant mortality) where bad devices fail immediately. Lindbergh was flying over land, during daylight, for this part of the trip. The second phase is a low constant rate of failure, where random defects stop the device from working. At the end of life, as parts wear out, the failure rate rises steeply.

If you have a large number (n) of devices with MTBF=200hrs then on the average, you'll need to replace one every 200/n hrs.

What is the distribution of failures? While it's fine to say that if you have 200 light bulbs (globes) each with a MTBF of 200hrs, that you'll be replacing (on the average) 1/hr, what if you're in a plane and you've only got a small number (1,2 or 3) of engines? Knowing the average failure time of a large number of engines is not of much comfort, when you're over an ocean and your life depends on knowing what each engine is going to do. MTBF=200hrs could mean that the engine will have a linearly descreasing probability of functioning with time, having a 50% chance of working at 100hrs and being certain to die at close to 200hrs. Experimental measurements show that this isn't the way things fail. Presumably the manufacturer knew the distribution of failures of Lindbergh's engine, but I don't, so I'll make the assumption which is simplest to model; the flat part of the bathtub curve, with a uniform distribution of failures i.e. that in any particular hour, the engine has the same (1/200) chance of failure, or a 100-0.5=99.5% chance of still running at the end of an hour.

The Wright Whirlwind J-5C engine was fitted to single engined, two engined and three engined planes.

Let's say that Lindbergh wants to know the chances of making it to Paris in a single engine plane. Write code lindbergh_one_engine.py with the following specs

Here's my code ^[287] and here's my output

dennis: class_code# ./lindbergh_one_engine.py
./lindbergh_one_engine.py
time  1 in_air 0.99500

Note

You could have done without the variable interval and replaced it with the constant "1.0". You would have got the same result, but it's sloppy programming. A variable, which should be declard up top and which you might want to change later, will now be buried as a constant deep in the code. Someone wanting to modify the code later, will have to sort through all the constants e.g. "1.0" or "1" to figure out which ones are the interval. It's better for you to code it up correctly now and save the next person a whole lot of bother figuring out how the code works.

Now we want to find the probability of the engine still running at any time during the flight. Copy lindbergh_one_engine.py to lindbergh_one_engine_2.py.

Here's my code ^[288] and here's my output

dennis:class_code# ./lindbergh_one_engine_2.py 
time in_air 
   0  1.000
   1  0.995
   2  0.990
   3  0.985
   4  0.980
   5  0.975
   6  0.970
   7  0.966
   8  0.961
   9  0.956
  10  0.951
  11  0.946
  12  0.942
  13  0.937
  14  0.932
  15  0.928
  16  0.923
  17  0.918
  18  0.914
  19  0.909
  20  0.905
  21  0.900
  22  0.896
  23  0.891
  24  0.887
  25  0.882
  26  0.878
  27  0.873
  28  0.869
  29  0.865
  30  0.860
  31  0.856
  32  0.852
  33  0.848
  34  0.843
  35  0.839
  36  0.835
  37  0.831
  38  0.827

The flight to Paris took 33.5hrs. What probability did Lindbergh have of making it in a single engined plane ^[289] ?

Let's define luck as the probability that matters beyond your control, that will wreck your plan, will be in your favour. (In conversational terms, luck is not defined in any measurable units. It's high time that luck be put on a sound mathematical basis.) In this case Lindbergh has a 16% chance that the engine will fail. He requires 16% luck for the flight to be successful.

Figure 11. probability of engine failure stopping flight. Vertical line at 33.5hr is actual time of Lindberg's flight.

The loop parameters in a python for loop, e.g. the step parameter are integers. In the code above, step takes the default=1. We want step=interval a real. For the code above to work, we must chose an interval that is a multiple of 1.0 and we must hand code the value of step to match interval (i.e. if we want to change interval, we also have to change step in the loop code). To let maintainers know what we're doing we should at least do this

start    =0
fuel_time=2500.0
end=int(fuel_time)
interval =1.0
step=int(interval)

for time in (start, end, step):
	...

This will give sensible results as long as fuel_time, interval are multiples of 1.0 Still this code is a rocket waiting to blow up. Python while loops can use reals as parameters. Copy lindbergh_one_engine_2.py to lindbergh_one_engine_3.py and use a while loop to allow the loop parameters to be reals. Here's my code ^[290] (the output is unchanged). Now you can change the parameter affecting the loop, in the variable list above the loop, without touching the loop code.

about areas: The units of area are the product of the units of each dimension. The area of a rectangle, with sides measured in cm, is measured in square centimetres (cm²).

To predict the amount of energy that a power plant will need to produce for a month, the power company plots the expected temperature on the y axis, with days (date) on the x axis. The number of degrees below a certain temperature (somewhere about 17°C, 65°F) at any time multiplied by the number of days, gives the amount of heat (energy) needed in degree-days (http://en.wikipedia.org/wiki/Heating_degree_day) that customers will need. i.e. the number of degree-days is the area between the line temp=65° and the line showing the actual temperature (in winter). Tables of degree-days for US cities are at National Weather Service - Climate Prediction Center (http://www.cpc.noaa.gov/products/analysis_monitoring/cdus/degree_days/).

What's the units of the area under the one-engine graph ^[291] ? If you ran the graph to infinite time, what do you think the area under the graph might be ^[292] ? Let's find out. Copy lindbergh_one_engine_3.py to lindbergh_one_engine_4.py

Here's my code ^[293] and here's my output

dennis: class_code# ./lindbergh_one_engine_3.py
time in_air    area
   0  1.000 1.000
 100  0.606 79.452
 200  0.367 126.975
 300  0.222 155.764
 400  0.135 173.203
 500  0.082 183.767
 600  0.049 190.167
 700  0.030 194.043
 800  0.018 196.392
 900  0.011 197.814
1000  0.007 198.676
1100  0.004 199.198
1200  0.002 199.514
1300  0.001 199.706
1400  0.001 199.822
1500  0.001 199.892
1600  0.000 199.935
1700  0.000 199.960
1800  0.000 199.976
1900  0.000 199.985
2000  0.000 199.991
2100  0.000 199.995
2200  0.000 199.997
2300  0.000 199.998
2400  0.000 199.999
2500  0.000 199.999

It looks like the area is going to be exactly the MTBF.

At what time is the area 100hr (you'll have to run the code again printing out the area at every hour)? Can you see a simple relationship between t₁₀₀ and MTBF?

In the current code, the loop requires integer parameters, while the code requires real parameters. To get a reasonable estimate of the area, we have to not only intcrease time to a large number, but we have to decrease the interval to a small (i.e. non integer) value. We need to rewrite the loop using real numbers as the parameters. To do this we need to change the loop from a for to a while loop. Copy lindbergh_one_engine_3.py to lindbergh_one_engine_4.py. Make the following changes to the code

FIXME

Before we start wondering what this means, is our estimate of the area an upper bound, a lower bound, or exactly right (within the 64-bit precision of the machine) (hint: is the probability of the engine working as a function of time a continuous function or is it a set of steps? How have we modelled the probability, as a continuous function or a set of steps?) ^[294] ? If this an upper or lower bound, what is the other bound ^[295] ? So what can we say about the area under the graph ^[296] ?

Why are we talking about Lindbergh in a section on programming geometric series and exponential processes? The probability of Lindbergh still flying at the end of each hour is a geometric series

p       = r^0, r^1, r^2 ... r^n
where r = 0.995

Using the formula for the sum of a geometric series, what's the sum of this series

Sum     = r^0 + r^1 + r^2 ... r^n
        = 1/(1-0.995) = 200

?

Why is the area under the graph = MTBF = 200hrs?

The next problem is fuel - if you run into headwinds or have to go around storms, you'll run out of fuel. A two engined plane can carry a bigger load (more fuel). However one engine alone is not powerful enough to fly the heavier plane. If you have two engines each with a MTBF of 200hrs, what's the MTBF for (any) one engine? It's 100hrs. (If you have 200 light bulbs, each with a MTBF of 200hrs, then on the average there will be a bulb failure every hour.) Copy lindbergh_one_engine_2.py to lindbergh_two_engines.py. Change the documenation and the MTBF to 100hrs and rerun the flight for the same 38hrs (Lindbergh will now have more fuel than this). Here's my code ^[297] and here's my result

./lindbergh_two_engines.py
time in_air 
   0  1.000
   1  0.990
   2  0.980
   3  0.970
   4  0.961
   5  0.951
   6  0.941
   7  0.932
   8  0.923
   9  0.914
  10  0.904
  11  0.895
  12  0.886
  13  0.878
  14  0.869
  15  0.860
  16  0.851
  17  0.843
  18  0.835
  19  0.826
  20  0.818
  21  0.810
  22  0.802
  23  0.794
  24  0.786
  25  0.778
  26  0.770
  27  0.762
  28  0.755
  29  0.747
  30  0.740
  31  0.732
  32  0.725
  33  0.718
  34  0.711
  35  0.703
  36  0.696
  37  0.689
  38  0.683

Lindbergh won't have to worry about running out of fuel anymore. Now how lucky does Lindy have to be ^[298] ? Would you rely on this amount of luck for your life?

Before we go on to the 3 engine case, we didn't derive the formula for the one or two engine case rigourously, and the method we used doesn't work for 3 engines. So let's derive the formula in the proper way. For this we're going to make a side trip to learn some Section 36.

The next possibility is a 3 engine plane. This could carry the extra fuel and it could still fly with on two engines.

Building a house (or a rocket) is a linear process. You start with the basement, then the floors, then the walls, the roof... You can't build the roof any faster if the basement is finished in half the time.

Any process where later stages are helped if earlier stages are better will be an exponential process. Examples (other than investing early) are

After you've built your first rocket, or house, you will be in a better position to build a second house, or dozens of houses (rockets) just like the first one.

The point is: if it's an exponential process, get in early and stick with it.

It seems that to excel in a field (whether playing music or computer programming), you need to first spend about 10,000hrs at it A gift or hard graft? (http://www.guardian.co.uk/books/2008/nov/15/malcolm-gladwell-outliers-extract). No one seems to be able to differentiate genius from 10,000hrs of hard work.

Give a presentation on exponential processes (you can use any content from this webpage).