iamrajiv's blog

By iamrajiv, history, 5 weeks ago, In English

The Fibonacci numbers occur as the ratio of successive convergents of the continued fraction for $$$\varphi$$$, and the matrix formed from successive convergents of any continued fraction has a determinant of $$$+1$$$ or $$$-1$$$.

$$$\varphi=1+\cfrac1{1+\cfrac1{1+\cfrac1{1+\cfrac1{1+\ddots}}}}$$$

The matrix representation gives the following closed-form expression for the Fibonacci numbers i.e.

$$${\begin{pmatrix}1&1\\\ 1&0\end{pmatrix}}^n=\begin{pmatrix}F_{n+1}&F_n\\\ F_n&F_{n-1}\end{pmatrix}$$$

The matrix is multiplied $$$n$$$ time because then only we can get the $$$(n+1)^{th}$$$ Fibonacci number as the element at the row and the column $$$(0,0)$$$ in the resultant matrix.

If we apply the above method without using recursive multiplication of matrix, then the Time Complexity: $$$O(n)$$$ and Space Complexity: $$$O(1)$$$.

But we want Time Complexity: $$$O(log\ n)$$$, so we have to optimize the above method, which can be done by recursive multiplication of matrix to get the $$$n^{th}$$$ power.

Implementation of the above rule can be found below.

#include <stdio.h>

void multiply(int F[2][2], int M[2][2]);

void power(int F[2][2], int n);

/*
The function that returns nth Fibonacci number.
*/

int fib(int n) {
	int F[2][2] = {{1, 1}, {1, 0}};
	if (n == 0)
		return 0;
	power(F, n - 1);
	return F[0][0];
}

/*
Optimized using recursive multiplication.
*/

void power(int F[2][2], int n) {
	if ( n == 0 || n == 1)
		return;
	int M[2][2] = {{1, 1}, {1, 0}};
	power(F, n / 2);
	multiply(F, F);
	if (n % 2 != 0)
		multiply(F, M);
}

void multiply(int F[2][2], int M[2][2]) {
	int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
	int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
	int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
	int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
	F[0][0] = x;
	F[0][1] = y;
	F[1][0] = z;
	F[1][1] = w;
}

int main() {
	printf("%d\n", fib(15));
	/*
	15th Fibonacci number is 610.
	*/
	return 0;
}
 
 
 
 
  • Vote: I like it
  • -14
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

Is this tested? :/

	power(F, n / 2);
	multiply(F, F);

I think you're supposed to do multiply(F, F) before power(F, n / 2);.

edit: oops my bad

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That would be incorrect, like for fib(15) answer should be 160. If I do multiply(F, F) before power(F, n / 2), it will give output 89, which is incorrect.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Just a side note, interchanging the line does not work because the matrix M is hard-coded in the power() function. Otherwise, both ordering would give the correct answer.

    void power(int F[2][2], int n) {
    	if (n == 0 || n == 1)
    		return;
    	int M[2][2] = {{F[0][0], F[0][1]}, {F[1][0], F[1][1]}};  // modified
    	power(F, n / 2);
    	multiply(F, F);
    	if (n % 2 != 0)
    		multiply(F, M);
    }
    

    Hard-coding values can lead to confusing situations and a pain to debug, hence, should be avoided.

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

I always had trouble understanding where the matrix came from. Till I realized:

$$$\begin{bmatrix} a_1 & b_1 \\ c_1 & d_1 \end{bmatrix} \cdot

\begin{bmatrix} a_2 & b_2 \\ c_2 & d_2 \end{bmatrix}

=\begin{bmatrix} a_1\cdot a_2 + b_1\cdot c_2 & a_1\cdot b_2 + b_1\cdot d_2 \\ c_1\cdot a_2 + d_1\cdot c_2 & c_1\cdot b_2 + d_1\cdot d_2 \end{bmatrix} $$$

Notice that, we need the the first cell to have a+b and any to have whatever but to be able to do the transition. So, if we substituted $$$a_2=1$$$, $$$c_2=1$$$ then the first cell in the first row and first column would have $$$a+b$$$. If we can also make that $$$b_1$$$ change to $$$a$$$, then we are basically done as this will be the transition. If we set $$$b_2=1$$$ and $$$d_2=0$$$, this will negate the $$$b_1$$$ and add 1 of $$$a_1$$$. And we are done! We've done it:

$$$\begin{bmatrix} a_1 & b_1 \\ c_1 & d_1 \end{bmatrix} \cdot

\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}

=

\begin{bmatrix} a_1+b_1 & a_1 \\ useless & useless \end{bmatrix} $$$

We basically won't use the other two cells in the transition, but they are essential for making the matrix complete as the first cell and second cell in the first row transition are dependent on it for the complete transition.