A logarithmic time hybrid solution of Fibonacci numbers using dynamic programming technique
Volume 1 Issue 1 2007
Download| Author(s): | H.Mehta, D.Abhyankar,S. Tanwani, A. K. Ramani |
|---|---|
| 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. |
| Keywords | Dynamic Programming, memorization, Fibonacci number, recursive solution, Recursive squaring, complexity |
| Year | 2007 |
| Volume | 1 |
| Issue | 1 |
| Type | Research paper, manuscript, article |
| Journal Name | Journal of Information & Communication Technology | Publisher Name | ILMA University | Jel Classification | - | DOI | - | ISSN no (E, Electronic) | 2075-7239 | ISSN no (P, Print) | 2415-0169 | Country | Pakistan | City | Karachi | Institution Type | University | Journal Type | Open Access | Manuscript Processing | Blind Peer Reviewed | Format | Paper Link | https://jict.ilmauniversity.edu.pk/journal/jict/1.1/3.pdf | Page | 34-41 |