A logarithmic time hybrid solution of Fibonacci numbers using dynamic programming technique | [Journal of Information & Communication Technology (JICT) • 2007]

Author(s):

1. S. Tanwani: School of Computer Science, Devi Ahilya University, Indore, INDIA Leonardo of Pisa (1175-1250

2. H. Mehta: School of Computer Science, Devi Ahilya University, Indore, INDIA Leonardo of Pisa (1175-1250

3. D. Abhyankar: School of Computer Science, Devi Ahilya University, Indore, INDIA Leonardo of Pisa (1175-1250

4. A. K. Ramani: School of Computer Science, Devi Ahilya University, Indore, INDIA Leonardo of Pisa (1175-1250

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.

Page(s): 34-41

DOI: DOI not available

Published: Journal: Journal of Information & Communication Technology (JICT), Volume: 1, Issue: 1, Year: 2007

Keywords:

Keywords are not available for this article.

References:

References are not available for this document.

Citations

Citations are not available for this document.

Citations

Downloads

Views