Home

[This page is auto-generated; please prefer to read the article’s PDF Form.]

Improved Algorithm

In an earlier article titled “Some Proofs About Fibonacci Numbers”, we arrived at below in Relation 4. For all m > 1:

Thus for n being even (2m) or odd (2m + 1), we are able to express F_n in terms of two smaller fibonacci numbers which occur almost halfway earlier in the fibonacci sequence. If we know F_m and F_m+1, we only need four multiplications, one addition and one subtraction to calculate F_2m and F_2m+1. As mentioned earlier for Sequential Algorithm, we will need to handle large numbers and these operations over them.

Say n = 2m. What are all the smaller fibonacci numbers we need to calculate F_n? In what order should they be calculated? F_n can be calculated using (2) if we know F_m and F_m+1. Now, to calculate F_m and F_m+1, again we could use (2) or (3), and will need to know fibonacci numbers located almost halfway of m in the sequence. Thus an algorithm can be written to calculate F_n using recursion, starting at index n and keep doing its half at each recursion. We should also avoid repeated calculation of the same fibonacci number. As with any recursive algorithm, this too will require nested function calls and corresponding space on call-stack.

In this article, we discuss a non-recursive variant of the algorithm. Since n > 2, say the binary representation of n is: (1b₁b₂b₃…b_k), where each b_i is 0 or 1. We have ignored all the starting 0 bits for simplicity. It is pleasant to observe that if we start with an integer x = 1, we can make it equal to n only by doubling and incrementing by 1, as in below C program. Variable b[i] represents b_i.

We saw earlier that both F_2m and F_2m+1 can be calculated just by knowing F_m and F_m+1. So, in above loop, whenever we update x to x ∗ 2, we can calculate F_2x and F_2x+1 if we know F_x and F_x+1.

We now add two variables Fx and Fxp1 (read “xp1” as “x plus 1”), and a temporary storage variable tmp to the above program. Our aim is to maintain the following predicate whenever we update x:

Q is true just before we enter the loop, because F₁ = F₂ = 1. In Block-1 of the code, we calculate F_2x and F_2x+1 from F_x and F_x+1, using equations (2) and (3). Variables Fx and Fxp1 are updated to reflect the new value of x. Thus Block-1 maintains Q.

In Block-2, we calculate F_x+2 from F_x and F_x+1 using recurrence definition (1), and variables Fx and Fxp1 are updated to reflect the new value of x. Thus Block-2 maintains Q.

Hence, each iteration of the loop, with b[i] as 1 or 0, will maintain Q — Q is the loop-invariant. So, when the loop terminates and x has become equal to n, (x = n ∧ Q) must hold true. Further,

Thus, we would receive the value of F_n in Fx.

Note that we can avoid calculating Fx∗Fx twice in each iteration by storing it in a variable. Also, instead of using bit-array b[i], we can directly check a specific bit of n by maintaining a bit-mask.

The pair of consecutive fibonacci numbers Fx and Fxp1 is updated by each iteration to fibonacci numbers of almost double indices. So we may call the algorithm Doubling Fibonacci Pair.

This algorithm requires ⌊log ₂(n)⌋ iterations, doing four multiplications, two additions and one subtraction of large numbers in each iteration. Thus it performs logarithmic (in n) number of operations on large numbers. These operations themselves need not have a constant time-complexity, and so the overall complexity will vary depending upon the implementation of large numbers.

[Prev]   [Up]   

Copyright © 2020 Nitin Verma. All rights reserved.