DefinePK

Abstract

Leonardo of Pisa (1175-1250) in 1202 introduced Fibonacci numbers.
Gabriel lame used the Fibonacci sequence in the analysis of the efficiency
of the Euclidean algorithm (the first algorithm of the world). Lucas who
popularized the Towers of Hanoi puzzle derived many properties of this
sequence. Lucas was first to call these numbers the Fibonacci sequence.
Despite a long history, very limited literature is available on the efficient
solution of the Fibonacci sequence. In this paper, we propose an algorithm
that efficiently computes Fibonacci numbers. The proposed algorithm
is an hybrid version of two existing algorithms: one based on
memroization Mehta (2006) and the other based recursive squaring
method Knuth and designed to deliver best space-time tradeoff. The
implementation of our algorithm and the experimental results prove
that the suggested algorithm outperforms the other known algorithms.