61 61 4 Modes 4 1 4 2 4 3 4 4 Growth of the Fibonacci series Taking out the big part from Fibonacci Operator interpretation General method Partial fractions 52 55 57 59 The goals of this chapter are to illustrate the experimental way that an engineer studies systems even abstract mathematical systems to illustrate what modes are by finding them for the Fibonacci system and to decompose second order systems into modes explaining the decomposition using operators and block diagrams The first question is what a mode is That question will be answered as we decompose the Fibonacci sequence into simpler sequences Each simple sequence can be generated by a first order system like the leaky tank and is called a mode of the system By decomposing the Fibonacci sequence into modes we decompose the system into simpler first order subsystems The plan of the chapter is to treat the Fibonacci system first as a black box producing an output signal F and to develop computational probes to examine signals This experimental approach is how an engineer studies even abstract mathematical systems The results from the probes will show us how to decompose the signal into its modes These modes are then reconciled with what the operator method predicts for decomposing the system 61 2009 09 29 13 11 30 UTC rev b19331f50bbd 61 62 62 52 4 1 Growth of the Fibonacci series Why describe the experimental and perhaps harder method for finding the modes before giving the shortcuts using operators We know the operator expression for the Fibonacci system and could just rewrite it using algebra The answer is that the operator method has meaning only after you feel modes in your fingertips a feeling developed only as you play with signals Without first playing we would be teaching you amazing feats of calculation on meaningless objects Furthermore the experimental approach works even when no difference equation is available to generate the sequence Engineers often characterize such unknown or partially known systems The system might be computational Imagine debugging someone else s program You send in test inputs to find out how it works and what makes it fail electronic Imagine debugging a CPU that just returned from the fabrication run perhaps in quantities of millions but that does not correctly divide floating point numbers 12 You might give it numbers to divide until you find the simplest examples that give wrong answers From that data you can often deduce the flaw in the wiring mathematical Imagine computing primes to investigate the twin prime conjecture 16 one of the outstanding unsolved problems of number theory The conjecture states that there are an infinite number of prime pairs p p 2 such as 3 5 5 7 etc The new field of experimental mathematics which uses computational tools to investigate mathematics problems is lively growing and a fertile field for skilled engineers 4 14 8 So we hope that through experimental probes of the Fibonacci sequence you learn a general approach to solving problems 4 1 Growth of the Fibonacci series Section 1 1 2 estimated how fast the sequence f n grew It seemed to grow geometrically with an order of growth between 2 and 2 Our first project is to experimentally narrow this range and thereby to guess a closed form for the order of growth One probe to find the order of growth is to compute the successive ratios f n f n 1 The ratios oscillated around 1 618 but this estimate is not 62 2009 09 29 13 11 30 UTC rev b19331f50bbd 62 63 63 4 Modes 53 accurate enough to guess a closed form Since the oscillations in the ratio die out as n grows let s estimate the ratio accurately by computing it for large n Our tool for these experiments our probe is a computer that we program in Python a clean widely available language Use any tool that fits you perhaps another language a graphing calculator or a spreadsheet Section 2 3 2 offered this Python code to compute f n def f n if n 2 return 1 return f n 1 f n 2 But the code is slow when n is large Here are the running times to evaluate f n on a Pentium CoreDuo 1 8GHz processor n 10 15 20 25 30 time ms 0 17 1 5 21 162 1164 The times grow rapidly Exercise 21 What is the running time of this implementation The times might seem low enough to be usable but imagine being on a desert island with only a graphing calculator then the times might be a factor of 10 or of 100 longer We would like to build an efficient computational probe so that it is widely usable An efficient function would store previously computed answers returning the stored answer when possible rather than recomputing old values In Python one can store the values in a dictionary which is analogous to a hash in Perl or an associative array in awk The memoized version of the Fibonacci function is memo def f n if n 2 return 1 if n in memo return memo n memo n f n 1 f n 2 return memo n 63 2009 09 29 13 11 30 UTC rev b19331f50bbd 63 64 64 4 1 Growth of the Fibonacci series 54 Pause to try 20 What is the running time of the memoized function in big Oh notation The new function runs in linear time a faster probe so we can inexpensively compute f n for large n Here are the ratios f n f n 1 n 5 10 15 20 25 30 35 40 45 f n f n 1 1 60000000000000009 1 61818181818181817 1 61803278688524599 1 61803399852180330 1 61803398867044312 1 61803398875054083 1 61803398874988957 1 61803398874989490 1 61803398874989490 These values are very stable by n 45 perhaps limited in stability only by the precision of the floating point numbers Let s see what closed form would produce the ratio 1 61803398874989490 at n 45 One source for closed forms is your intuition and experience Another wonderful source is the Inverse Symbolic Calculator http oldweb cecm sfu ca projects ISC By using the Inverse Symbolic Calculator you increase your repertoire of closed form and thereby enhance your intuition Pause to try 21 Ask the Inverse Symbolic Calculator about 1 61803398874989490 The Inverse Symbolic Calculator thinks that 1 61803398874989490 is most likely the positive root of x2 x 1 or equivalently is the golden ratio 1 5 2 Let s use that hypothesis Then f n n But we do not know the constant hidden by the symbol Find that constant by using the Inverse Symbolic Calculator one more time Here is a 64 2009 09 29 13 11 30 UTC rev b19331f50bbd 64 65 65 4 Modes 55 table of the ratio f n n With luck it converges to a constant And it does n 0 10 20 30 40 50 60 70 80 90 100 f n n 1 00000000000000000 0 72362506926471781 0
View Full Document
Unlocking...