No Detail Found!

A logarithmic time hybrid solution of Fibonacci numbers using dynamic programming technique

Author(s)
S. Tanwani School of Computer Science, Devi Ahilya University, Indore, INDIA Leonardo of Pisa (1175-1250
H. Mehta School of Computer Science, Devi Ahilya University, Indore, INDIA Leonardo of Pisa (1175-1250
D. Abhyankar School of Computer Science, Devi Ahilya University, Indore, INDIA Leonardo of Pisa (1175-1250
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.
Publication Details
Page(s) 34-41
DOI DOI not available
Published Journal: Journal of Information & Communication Technology (JICT), Volume: 1, Issue: 1, Year: 2007

Request the full text from PASTIC

0

Citations

0

Downloads

81

Views