Fibonacci sequence – Part 2

In this post we’ll compare the various methods of generating Fibonacci sequence terms and implementing the code to recognize Fibonacci terms and to determine index of these terms. These have been discussed mathematically in the previous post.

Generating Fibonacci Terms

Method 1 – Iterative method

Using the basic concept of the Fibonacci sequence, that each term is the sum of the previous two terms, the following function in Python generates the n^th term:

def F_iter(n) :
    if n == 0 or n == 1: return n
    a, b = 0, 1
    for i in xrange(n-2) :
        a, b = b, a+b
    return b

If the input n is either 0 or 1, n itself is returned as the first two Fibonacci terms are 0 and 1. Otherwise, further terms are calculated by adding the respective two previous terms. Finally when we reach the upper bound n, we return the last term generated. This method runs in linear time and thus has a complexity of Θ(n).

Method 2 – Recursive method

The n^th Fibonacci term can be easily generated by using the same concept as above in a recursive function. This is demonstrated in Python as follows:

def F_rec(n) :
    if n == 0: return 0
    elif n == 1: return 1
    return F_rec(n-1) + F_rec(n-2)

This method has a very long running time for large values of n and has a complexity of Ω(φⁿ).

Method 3 – Golden ratio method

This method uses the relation between the Fibonacci sequence and the Golden ratio that the product of a Fibonacci term and the Golden ratio gives the next term when rounded off. In the previous post, we had obtained a relation that for all n ≥ 0, the number F_n is the closest integer to , where φ is the Golden ratio. The implementation in Python is:

def F_phi(n) :
    ans = round((phi**n)/sqrt(5))
    if n < 0: ans = (-1)**(n+1) * ans
    return ans

This method has a logarithmic running time – O(log n), which is the best of the three methods, but it has a disadvantage that it uses floating point calculations. However, it can easily generate Fibonacci terms of negative indices.

Recognizing Fibonacci Terms and Their Indices

From Gessel’s test discusses in the previous post, N is a Fibonacci number if and only if 5N² + 4 or 5N² – 4 is a square number. Now, we need two functions, one for determining if a given number is a perfect square and one for determining if a given number is a Fibonacci term (using the first function).

Following are some methods for checking whether a number is a perfect square:

Method 1:

The simplest method is to check if the square root of the number is an integer. If yes, then the number is a perfect square. The Python code is:

def isPerfectSquare1(n) :
    a = sqrt(n)
    return a % 1 == 0

Method 2:

Another simple method would be to find the integer part of the square root of the input, square it ans compare it with the input itself. If there is a match, the input is a perfect square. A Python implementation:

def isPerfectSquare2(n) :
    a = int(sqrt(n))
    return a*a == n

Method 3:

The code can be improved if we can rule out some possibilities before calling the square root function. For example, look at the last digit of the number in hex by doing a bit-wise “and”. Perfect squares can only end in 0, 1, 4, or 9 in base 16. So for 75% of the inputs one can avoid a call to the square root in exchange for some very fast bit twiddling. Also, any negative input can be rejected right away before proceeding. In Python:

def isPerfectSquare3(n) :
    if n < 0: return False
    if (n & 0xF) in (0, 1, 4, 9) : return sqrt(n)%1 == 0
    return False

Among the above three methods, the last one has the best efficiency (running in about 40% of the time taken by the second method). Hence, for determining if a term belongs to the Fibonacci sequence, we will use it. The Python code for this is as follows:

def isFibTerm(n) :
    a = 5*n*n
    x, y = a + 4, a - 4
    return isPerfectSquare3(x) or isPerfectSquare3(y)

For finding the index, the modification of Binet’s formula in the previous post using logarithms gives the index n as n = ( log N + log(5)/2 ) / log(φ) if N is a Fibonacci term and φ is the Golden ratio. A simple code is:

def fibIndex(n) :
    if isFibTerm(n) :
        phi = (1 + sqrt(5)) / 2
    return int(ceil( (log10(n) + log10(5)/2) / log10(phi) ))