The Fibonacci numbers were introduced by Leonardo Fibonacci in 1202 as a solution to a problem about the size of a rabbit population (Problem 2 in this section’s exercises).

**Example:
Computing the**** ***n***th Fibonacci Number**

The
Fibonacci numbers were introduced by Leonardo Fibonacci in 1202 as a solution
to a problem about the size of a rabbit population (Problem 2 in this section’s
exercises). Many more examples of Fibonacci-like numbers have since been
discovered in the natural world, and they have even been used in predicting the
prices of stocks and commodities. There are some interesting applications of
the Fibonacci numbers in computer science as well. For example, worst-case
inputs for Euclid’s algorithm discussed in Section 1.1 happen to be consecutive
elements of the Fibonacci sequence. In this section, we briefly consider
algorithms for computing the *n*th
element of this sequence. Among other benefits, the discussion will provide us
with an opportunity to introduce another method for solving recurrence
relations useful for analysis of recursive algorithms.

To start,
let us get an explicit formula for ** F (n).** If we
try to apply the method of backward substitutions to solve recurrence (2.6), we
will fail to get an easily discernible pattern. Instead, we can take advantage
of a theorem that describes solutions to a

where ** a, b**, and

that
formula (2.9), which includes arbitrary integer powers of irrational numbers,
yields nothing else but all the elements of Fibonacci sequence (2.5), but it
does!

One of
the benefits of formula (2.9) is that it immediately implies that ** F (n)** grows exponentially (remember
Fibonacci’s rabbits?), i.e.,

In the algorithms that follow, we
consider, for the sake of simplicity, such oper-ations as additions and
multiplications at unit cost. Since the Fibonacci numbers grow infinitely large
(and grow very rapidly), a more detailed analysis than the one offered here is
warranted. In fact, it is the size of the numbers rather than a time-efficient
method for computing them that should be of primary concern here. Still, these
caveats notwithstanding, the algorithms we outline and their analysis provide
useful examples for a student of the design and analysis of algorithms.

To begin
with, we can use recurrence (2.6) and initial conditions (2.7) for the obvious
recursive algorithm for computing ** F (n)**.

**ALGORITHM** *F (n)*

//Computes
the ** n**th Fibonacci number recursively
by using its definition //Input: A nonnegative integer

//Output:
The ** n**th Fibonacci number

**else return ***F
(n*** **−** **1*)*** **+** ***F (n*** **−** **2*)*

Before
embarking on its formal analysis, can you tell whether this is an effi-cient
algorithm? Well, we need to do a formal analysis anyway. The algorithm’s ba-sic
operation is clearly addition, so let ** A(n)** be the
number of additions performed by the algorithm in computing

The
recurrence ** A(n)** −

[** A(n)** + 1] − [

and
substituting ** B(n)** =

The poor efficiency class of the
algorithm could be anticipated by the nature of recurrence (2.11). Indeed, it
contains two recursive calls with the sizes of smaller instances only slightly
smaller than size n. (Have you encountered such a situation before?) We can
also see the reason behind the algorithm’s inefficiency by looking at a
recursive tree of calls tracing the algorithm’s execution. An example of such a
tree for n = 5 is given in Figure 2.6. Note that the same values of the
function are being evaluated here again and again, which is clearly extremely
inefficient.

We can obtain a much faster algorithm
by simply computing the successive elements of the Fibonacci sequence
iteratively, as is done in the following algorithm.

ALGORITHM Fib(n)

//Computes the nth Fibonacci number
iteratively by using its definition

//Input: A nonnegative integer n

//Output: The nth Fibonacci number

F [0] ← 0; F [1] ← 1

for i ← 2 to n do

F [i] ← F [i − 1] + F [i − 2]

return F [n]

This
algorithm clearly makes ** n** − 1 additions. Hence, it is linear
as a function of

The third
alternative for computing the ** n**th
Fibonacci number lies in using formula (2.10). The efficiency of the algorithm
will obviously be determined by the efficiency of an exponentiation algorithm
used for computing

Finally,
there exists a ** (**log

and an
efficient way of computing matrix powers.

**Exercises 2.5**

** **1. Find a Web site dedicated to applications of the
Fibonacci numbers and study it.

** **2. *Fibonacci’s
rabbits problem *A man put a pair of rabbits in a place sur-rounded
by a wall. How many pairs of rabbits will be there in a year if the initial
pair of rabbits (male and female) are newborn and all rabbit pairs are not
fertile during their first month of life but thereafter give birth to one new
male/female pair at the end of every month?

** **3. *Climbing
stairs *Find the number of different ways to climb an* *** n**-stair stair-case if each step is
either one or two stairs. For example, a 3-stair staircase can be climbed three
ways: 1-1-1, 1-2, and 2-1.

4. How many
even numbers are there among the first ** n**
Fibonacci numbers, i.e., among the numbers

** **6. The maximum values of the Java primitive types int and long are 2^{31}
− 1 and 2^{63} − 1, respectively. Find the
smallest ** n** for which the

a. the type int.

**b. **the
type** **long.

** **7. Consider the recursive definition-based algorithm
for computing the ** n**th Fi-

bonacci
number ** F (n)**. Let

**
**** C(n) **=

** **8. Improve algorithm ** F
ib** of the text so that it requires only

9. Prove the
equality

** **10. How many modulo divisions are made by Euclid’s
algorithm on two consec-utive Fibonacci numbers ** F
(n)** and

**
**

** **11. *Dissecting
a Fibonacci rectangle *Given a rectangle whose sides are two con-secutive
Fibonacci numbers, design an algorithm to dissect it into squares with no more
than two squares being the same size. What is the time efficiency class of your
algorithm?

**
**

** **12. In the language of your choice, implement two
algorithms for computing the last five digits of the ** n**th Fibonacci number that are
based on (a) the recursive definition-based algorithm

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Fundamentals of the Analysis of Algorithm Efficiency : Example: Computing the nth Fibonacci Number |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.