61 6161 612009-09-29 13:11:30 UTC / rev b19331f50bbd4Modes4.1 Growth of the Fibonacci series 524.2 Taking out the big part from Fibonacci 554.3 Operator interpretation 574.4 General method: Partial fractions 59The goals of this chapter are:• to illustrate the experimental way that an engineer studies sys-tems, even abstract, mathematical systems;• to illustrate what modes are by finding them for the Fibonacci sys-tem; and• to decompose second-order systems into modes, explaining thedecomposition using operators and block diagrams.The first question is what a mode is. That question will be answered as wedecompose the Fibonacci sequence into simpler sequences. Each simplesequence can be generated by a first-order system like the leaky tank and iscalled a mode of the system. By decomposing the Fibonacci sequence intomodes, we decompose the system into simpler, first-order subsystems.The plan of the chapter is to treat the Fibonacci system first as a blackbox producing an output signal F and to develop computational probesto examine signals. This experimental approach is how an engineer stud-ies even abstract, mathematical systems. The results from the probes willshow us how to decompose the signal into its modes. These modes arethen reconciled with what the operator method predicts for decomposingthe system.62 6262 6252 4.1 Growth of the Fibonacci series2009-09-29 13:11:30 UTC / rev b19331f50bbdWhy describe the experimental, and perhaps harder, method for findingthe modes before giving the shortcuts using operators? We know the op-erator expression for the Fibonacci system, and could just rewrite it usingalgebra. The answer is that the operator method has meaning only afteryou feel modes in your fingertips, a feeling developed only as you playwith signals. Without first playing, we would be teaching you amazingfeats of calculation on meaningless objects.Furthermore, the experimental approach works even when no differenceequation is available to generate the sequence. Engineers often character-ize such unknown or partially known systems. The system might be:• computational: Imagine debugging someone else’s program. You sendin test inputs to find out how it works and what makes it fail.• electronic: Imagine debugging a CPU that just returned from the fabri-cation run, perhaps in quantities of millions, but that does not correctlydivide floating-point numbers [12]. You might give it numbers to di-vide 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-primeconjecture [16], one of the outstanding unsolved problems of numbertheory. [The conjecture states that there are an infinite number of primepairs p, p + 2, such as (3, 5), (5, 7), etc.] The new field of experimentalmathematics, which uses computational tools to investigate mathemat-ics 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 seriesSection 1.1.2 estimated how fast the sequence f[n] grew. It seemed to growgeometrically with an order of growth between√2 and 2. Our first projectis to experimentally narrow this range and thereby to guess a closed formfor the order of growth.One probe to find the order of growth is to compute the successive ratiosf[n]/f[n − 1]. The ratios oscillated around 1.618, but this estimate is not63 6363 634 Modes 532009-09-29 13:11:30 UTC / rev b19331f50bbdaccurate enough to guess a closed form. Since the oscillations in the ratiodie out as n grows, let’s estimate the ratio accurately by computing it forlarge n. Our tool for these experiments – our probe – is a computer that weprogram in Python, a clean, widely available language. Use any tool thatfits 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 1return f(n-1) + f(n-2)But the code is slow when n is large. Here are the running times to evaluatef[n] on a Pentium CoreDuo 1.8GHz processor:n 10 15 20 25 30time (ms) 0.17 1.5 21 162 1164The 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 adesert island with only a graphing calculator; then the times might be afactor of 10 or of 100 longer. We would like to build an efficient computa-tional probe so that it is widely usable.An efficient function would store previously computed answers, returningthe stored answer when possible rather than recomputing old values. InPython, one can store the values in a dictionary, which is analogous to ahash in Perl or an associative array in awk. The memoized version of theFibonacci function is:memo = {}def f(n):if n < 2 : return 1if n in memo : return memo[n]memo[n] = f(n-1) + f(n-2)return memo[n]64 6464 6454 4.1 Growth of the Fibonacci series2009-09-29 13:11:30 UTC / rev b19331f50bbdPause 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 inexpen-sively compute f[n] for large n. Here are the ratios f[n]/f[n − 1]:n f[n]/f[n − 1]5 1.6000000000000000910 1.6181818181818181715 1.6180327868852459920 1.6180339985218033025 1.6180339886704431230 1.6180339887505408335 1.6180339887498895740 1.6180339887498949045 1.61803398874989490These values are very stable by n = 45, perhaps limited in stability onlyby the precision of the floating-point numbers.Let’s see what closed form would produce the ratio 1.61803398874989490at 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/ISCmain.html.By using the Inverse Symbolic Calculator, you increase your repertoire ofclosed 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 mostlikely the positive root of x2− x − 1 or, equivalently, is the golden ratio φ:φ ≡1 +√52Let’s use that hypothesis. Thenf[n] ∼ φn.But we do not know the constant hidden by the ∼ symbol. Find that con-stant by using the Inverse Symbolic Calculator one more time. Here is a65
View Full Document
Unlocking...