Fibonacci Algorithm

5 Key excerpts on "Fibonacci Algorithm"

• 

  eBook - PDF

  Programming with Mathematica®

  An Introduction

  • Paul Wellin(Author)
  • 2013(Publication Date)
  • Cambridge University Press

    (Publisher)

  The Fibonacci numbers have since been studied extensively, finding application in such diverse areas as random number generation, compression algorithms, musical tunings, phyllotaxy in plants, population generation, and much more. See Knuth (1997) for a detailed discussion. The Fibonacci numbers are generated as follows: start with two 1s, then add them to generate the third number in the sequence; and generally, each new number in the sequence is created by adding the previous two numbers you have written down. 1 1 2 3 5 8 13 21 … F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8 … The simplest way to define these numbers is with recursion. F 1 = 1 F 2 = 1 F n = F n-2 + F n-1 , for n > 2 If we think of this sequence as a function, we would just change this to a functional definition. FH1L = 1 FH2L = 1 FHnL = FHn - 2L + FHn - 1L, for n > 2 In this form, we can translate the definition directly into Mathematica. In[1]:= F@1D = 1; In[2]:= F@2D = 1; In[3]:= F@n_D := F@n - 2D + F@n - 1D ê; n > 2 As it turns out, the condition n > 2 is unnecessary because Mathematica looks up specific rules such as F@1D = 1 before more general rules like that for F@nD. Here is a list of the first twenty-six Fibonacci numbers. In[4]:= Table@F@iD, 8i, 1, 26 2, you only apply F to numbers smaller than n. Let us trace the evaluation of F@4D only looking at expressions that involve an F@integerD or a sum of two Fs. 232 Recursion In[5]:= TracePrint@F@4D, F@_IntegerD F@_D + F@_DD F@4D F@4 - 2D + F@4 - 1D F@2D F@3D F@3 - 2D + F@3 - 1D F@1D F@2D Out[5]= 3 The first two lines indicate that F@4D is rewritten to F@4 - 2D + F@4 - 1D, and the lines that are indented show the calls of F@2D and F@3D.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Number Theory

  A Historical Approach

  • John J. Watkins(Author)
  • 2013(Publication Date)
  • Princeton University Press

    (Publisher)

  Fibonacci begins Liber abaci , written in 1202, by explaining that in India there are nine figures and that with these nine figures and the symbol 0 any number can be expressed. He then uses a variety of problems taken from Arab sources such as the works of al-Khwarizmi and abu-Kamil and from Greek texts to demonstrate how very much better the Hindu-Arabic number system is than the Roman system. The second edition of Liber abaci came out in 1228, and the use of the Hindu-Arabic number system for the calculations needed in such practical matters as everyday commerce and surveying quickly spread throughout Europe. The Fibonacci Sequence The Fibonacci sequence 1 , 1 , 2 , 3 , 5 , 8 , 13 , . . . , has an extraordinary number of interesting properties that people have noticed through the years. We begin our study of this fascinating sequence by unlocking what is perhaps its single most amazing property. First, we observe that the Fibonacci sequence { F n } is defined recursively by F 1 = 1 , F 2 = 1 , and F n = F n − 1 + F n − 2 for n > 2 . 326 Chapter 12 Now, let α be the irrational number α = 1 + √ 5 2 . This is one of the most famous numbers in all of mathematics. It is called the golden ratio , and we will soon discover what this particular irrational number has to do with the Fibonacci sequence. Similarly, let β be the number β = 1 − √ 5 2 . These two numbers α and β were not just randomly pulled out of a hat. They are the two roots of the characteristic polynomial x 2 − x − 1 of the recurrence relation for the Fibonacci sequence. More generally, the characteristic polynomial for a recurrence relation of the form s n = as n − 1 + bs n − 2 , where a and b are nonzero constants, is the polynomial x 2 − ax − b . This means that α and β are the two solutions to the equation x 2 − x − 1 = 0. You should check this either by using the quadratic formula or by actually plugging α and β into this equation.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Design and Analysis of Algorithms

  A Contemporary Perspective

  • Sandeep Sen, Amit Kumar(Authors)
  • 2019(Publication Date)
  • Cambridge University Press

    (Publisher)

  1 C H A P T E R Model and Analysis When we make a claim such as Algorithm A has running time O(n 2 log n), we have an underlying computational model where this statement is valid. It may not be true if we change the model. Before we formalize the notion of a computational model, let us consider the example of computing Fibonacci numbers. 1.1 Computing Fibonacci Numbers One of the most popular sequences is the Fibonacci sequence defined by F i =    0 i = 0 1 i = 1 F i-1 + F i-2 otherwise for i ≥ 2 It is left as an exercise problem to show that F n = 1 √ 5 (φ n - φ 0 n ) where φ = 1 + √ 5 2 φ 0 = 1 - φ Clearly, it grows exponentially with n and F n has θ(n) bits. Since the closed form solution for F n involves the golden ratio – an irrational number – we must find a way to compute it efficiently without incurring numerical errors or approximations as it is an integer. 2 Design and Analysis of Algorithms Method 1 By simply using the recursive formula, one can easily argue that the number of operations (primarily additions) involved is proportional to the value of F n . We just need to unfold the recursion tree where each internal node corresponds to an addition. As we had noted earlier, this leads to an exponential time algorithm and we cannot afford it. Method 2 Observe that we only need the last two terms of the series to compute the new term. Hence, by applying the principle of dynamic programming, 1 we successively compute F i starting with F 0 = 0 and F 1 = 1 and use the previously computed terms, F i and F i-1 for i ≥ 2. This takes time that is proportional to approximately n additions, where each addition involves adding (increasingly large) numbers. The size of F dn/2e is about n/2 bits; so, the last n/2 computations will take Ω(n) steps 2 culminating in an O(n 2 ) algorithm. Since the nth Fibonacci number is at most n bits, it is reasonable to look for a faster algorithm.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Discrete Mathematics with Applications

  • Thomas Koshy(Author)
  • 2004(Publication Date)
  • Academic Press

    (Publisher)

  Leonardo’s subsequent business trips to Egypt, Syria, Greece, and Sicily brought him closer to Indian mathematics. In 1202, shortly after his return, convinced of the elegance of the Indian methods of computation, Fibonacci published his famous work, Liber Abaci . (The word abaci in the title does not refer to the old abacus, but to computa-tion in general.) This book, devoted to arithmetic and elementary algebra, introduced the Indian notation and arithmetic algorithms to Europe. Fibonacci wrote three additional books: Practica Geometriae , a collec-tion of results in geometry and trigonometry; Liber Quadratorum , a major work on number theory; and Flos , also on number theory. Fibonacci’s importance and usefulness to Pisa and its citizenry through his teaching and services were honored by Emperor Frederick II of Pisa. The numbers 1, 1, 2, 3, 5, 8, . . . are Fibonacci numbers . ∗ They have a fascinating property: Any Fibonacci number, except the first two, is the sum of the two immediately preceding Fibonacci numbers. (At the given rate, there will be 144 pairs of rabbits on December 1.) This yields the following recursive definition of the n th Fibonacci number F n : F 1 = F 2 = 1 ← initial conditions F n = F n − 1 + F n − 2 , n ≥ 3 ← recurrence relation The next example illustrates recursion and also shows that Fibonacci numbers occur in quite unexpected places. EXAMPLE 5.8 Let a n denote the number of n -bit words containing no two consecutive 1’s. Define a n recursively. ∗ See author’s Fibonacci and Lucas Numbers with Applications for a thorough discussion of Fibonacci numbers. 270 Chapter 5 Recursion SOLUTION: First, let us find the n -bit words containing no two consecutive 1’s corre-sponding to n = 1, 2, 3, and 4 (see Table 5.2). It follows from the table that a 1 = 2, a 2 = 3, a 3 = 5, and a 4 = 8. Table 5.2 n = 1 n = 2 n = 3 n = 4 0 00 000 0000 1 01 010 0100 10 100 1000 001 0010 101 1010 0001 0101 1001 Now, consider an arbitrary n -bit word.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  How to Count

  An Introduction to Combinatorics, Second Edition

  • R.B.J.T. Allenby, Alan Slomson(Authors)
  • 2010(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  These numbers are named after the Italian mathematician Leonardo of Pisa,* who introduced them in connection with the following problem. * Leonardo of Pisa lived during the late twelfth and early thirteenth century. His alternative name Fibonacci comes from filius Bonacci , meaning “the son of Bonacci.” His biggest contribution to mathematics was his book Liber Abaci , in which, among other things, he advocated the use of the Indian place-value system for numbers, which we now regard as standard. He also described the problem about rabbits that gives rise to what we now call Fibonacci numbers. 104 ◾ How to Count: An Introduction to Combinatorics, Second Edition Rabbits take one month to reach maturity. A mature pair of rabbits produces another pair of rabbits each month. If you start with one pair of newly born rabbits, how many pairs will you have after n months? We let f n , for n ≥ 1, be the number of pairs of rabbits alive after n months. Thus f n is the number of pairs of rabbits, f n –2 , born to the rabbits who have reached maturity, plus the number, f n –1 , who were alive the previous month. Thus, for n ≥ 1, f n = f n –2 + f n –1 . (7.18) We obtain the Fibonacci numbers when we solve this recurrence relation subject to the initial conditions f 1 = 1 and f 2 = 1. (7.19) Note that, except for a change of notation, the recurrence relation in Equation 7.18 is the same as in Equation 7.14. The only difference is that the initial conditions given by Equation 7.19 are different from those given by Equation 7.13. The numbers in the sequence defined by Equations 7.18 and 7.19 are the Fibonacci num-bers. It is easy to calculate the first few terms in the sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, … , but can we find a simple formula for the numbers in this sequence? This was Problem 7 of Chapter 1. We now show how we can answer this question by finding the generating func-tion for the sequence.

  Sign up to read

  Learn more about book