Fibonacci Number for very large value 10^10^10 continued

Fibonacci Number for very large value 10^10^10 continued

 If you want to know what is Fibonacci sequence and different approaches to find Nth Fibonacci number then please do follow it in my previous post Fibonacci Sequence .

Here in this post we are going address the problem of finding Nth Fibonacci number with following given conditions

  • How to find the Nth Fibonacci number when N is very large which can not be stored in our default data types available (3 <= N <= 10^10^5 and 10 <= M <= 10^9.).
  • How we can optimize and find the Nth Fibonacci number in O(Log(N)) time..

You can download the complete solution hosted here: GitHub Code

In the previous post we discussed about Recursive approach (O(2^N)), Dynamic approach (O(N)), but lets see how we can solve the problem in O(Log(N)).

Lets start with the assumption(Later i will prove it to you) that if we multiply the matrix {{1, 1}, {1, 0}} to itself N times then we will get the (N + 1)th Fibonacci number at resultant matrix at (0, 0) location. But if we are multiplying the matrix for N times, then again its O(N) complexity, so in order to reduce it to Log(N) then we will take help of the power function which computes the power of a matrix in Log(N) time.

long[][] fibIdentity = { { 1, 1 }, { 1, 0 } };
private long[][] matrixPower(long[][] fibIdentity, int n, int m) {
	long[][] identity = { { 1, 0 }, { 0, 1 } };
	while (n > 0) {
		if (n % 2 == 1) {
			identity = matrixMultiply(identity, fibIdentity, m);
		}
		fibIdentity = matrixMultiply(fibIdentity, fibIdentity, m);
		n = n / 2;
	}
	return identity;
}

So above method will compute Fibonacci matrix (F) to power of N with modulus M, i.e F^N . After that it is straight forward to check the (0, 0) of the matrix to find the N-1th Fibonacci number.

And we are forgetting the first constraint of N being very large number, how are we going to take care of it? As the default data types available in the programming language can not store this. So we will process it as a character array and manipulate it to address our needs.

String nthNumber = "1000000008945386535333333333333333111111111111322222222222222220565165135313131531321351321531321313215321531321351313513513135131351313151351348698465";

So lets say you are given N value as mentioned above and asked to find the Nth Fibonacci number in logarithmic time complexity, don’t be like 😉

only data structure that comes to our rescue is String(Character array). And mainly as we see in matrixPower method, N is being used hardly in two lines, i.e.

if (n % 2 == 1)

and

n = n / 2;

So as we thought of processing N as a character array, lets see how we can write divide and modulus functions

private char[] division(char[] dividend, int divisor) {
	char[] quotient = new char[dividend.length];
	int i = 0, j = 0;
	long temp = 0;
	for (i = 0; i < dividend.length; i++) {
		temp = temp * 10 + dividend[i] - 48;
		if (temp < divisor) {
			quotient[j++] = 48;
		} else {
			quotient[j++] = (char) ((temp / divisor) + 48);
			temp = temp % divisor;
		}
	}
	return quotient;
}

This is the generic divide function which is exactly same as how we used to divide numbers in our childhood days.

and as far as modulus is concerned, Taking a modulus of the whole number is as good as checking the last character of it just like below

n[size - 1] % 2 == 1

so we can update the matrixPower function like below

private long[][] matrixPower(long[][] A, char[] n, long M) {
	long[][] identity = { { 1, 0 }, { 0, 1 } };
	int size = n.length;
	while (isNGreaterThanZero(n)) {
		if (n[size - 1] % 2 == 1) {
			identity = matrixMultiply(identity, A, M);
		}
		A = matrixMultiply(A, A, M);
		n = division(n, 2);
	}
	return identity;
}

private boolean isNGreaterThanZero(char[] n) {
	for (int i = n.length - 1; i >= 0; i--) {
		if (n[i] > 48) {
			return true;
		}
	}
	return false;
}

To summarize the complete code,

public class FibonacciNthNumber {

       public static void main(String[] args) {
		String str = "1000000008945386535333333333333333111111111111322222222222222220565165135313131531321351321531321313215321531321351313513513135131351313151351348698465";
		char[] N = str.toCharArray();
		long M = 999999999;
		FibonacciDecimal instance = new FibonacciDecimal();
		long fib = instance.findFib(N, M);
		System.out.println(fib);
	}
	protected long findFib(char[] N, long M) {
		long[][] fibIdentity = { { 1, 1 }, { 1, 0 } };
		long[][] result = matrixPower(fibIdentity, N, M);
		return result[0][0];
	}

	private long[][] matrixPower(long[][] A, char[] n, long M) {
		long[][] identity = { { 1, 0 }, { 0, 1 } };
		int size = n.length;
		while (isNGreaterThanZero(n)) {
			if (n[size - 1] % 2 == 1) {
				identity = matrixMultiply(identity, A, M);
			}
			A = matrixMultiply(A, A, M);
			n = division(n, 2);
		}

		return identity;
	}

	private boolean isNGreaterThanZero(char[] n) {
		for (int i = n.length - 1; i >= 0; i--) {
			if (n[i] > 48) {
				return true;
			}
		}
		return false;
	}

	private long[][] matrixMultiply(long[][] identity, long[][] a, long M) {
		long[][] result = new long[2][2];
		long m = identity.length;
		long n = a[0].length;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				long sum = 0;
				for (int k = 0; k < a.length; k++) {
					sum = (sum + (identity[i][k] * a[k][j]) % M) % M;
				}
				result[i][j] = sum;
			}
		}
		return result;
	}

	private char[] division(char[] dividend, int divisor) {
		char[] quotient = new char[dividend.length];
		int i = 0, j = 0;
		long temp = 0;
		for (i = 0; i < dividend.length; i++) {
			temp = temp * 10 + dividend[i] - 48;
			if (temp < divisor) {
				quotient[j++] = 48;
			} else {
				quotient[j++] = (char) ((temp / divisor) + 48);
				temp = temp % divisor;
			}
		}
		return quotient;
	}
}

So what’s left out to know is how we derived that Fibonacci matrix {{1, 1}, {1, 0}} ?

let me prove it by induction, lets consider below equation.

\[\begin{bmatrix} f[ n + 1] \\ f[n] \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f(n) \\ f(n – 1) \end{bmatrix} \]
let \[A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\]
\[\begin{bmatrix} f[ n + 1] \\ f[n] \end{bmatrix} = A \begin{bmatrix} f(n) \\ f(n – 1) \end{bmatrix}\]
\[\begin{bmatrix} f[ n + 1] \\ f[n] \end{bmatrix} = A x A \begin{bmatrix} f(n -1) \\ f(n – 2) \end{bmatrix}\]
\[\begin{bmatrix} f[ n + 1] \\ f[n] \end{bmatrix} = A x A x A \begin{bmatrix} f(n -2) \\ f(n – 3) \end{bmatrix}\]
\[\begin{bmatrix} f[ n + 1] \\ f[n] \end{bmatrix} = A^k \begin{bmatrix} f(n -k + 1) \\ f(n – k) \end{bmatrix}\]
Terminate when n = k
\[\begin{bmatrix} f[ n + 1] \\ f[n] \end{bmatrix} = A^n \begin{bmatrix} f(1) \\ f(0) \end{bmatrix}\]
\[\begin{bmatrix} f[ n + 1] \\ f[n] \end{bmatrix} = A^n \begin{bmatrix} 1\\ 0\end{bmatrix}\]
so
\[\begin{bmatrix} f[ n + 1] \\ f[n] \end{bmatrix} = \begin{bmatrix} A & B\\ C & D\end{bmatrix} \begin{bmatrix} 1\\ 0\end{bmatrix}\]
Hence f(n) = C, if you multiply matrix n times, then we get (n-1)th term So we will need to multiply matrix for (n + 1) times in order to get Nth Fibonacci number.
If we had a Fibonacci sequence lets say F(n) = F(n – 1) + F(n – 3), then we end up choosing matrix
\[\begin{bmatrix} f[ n + 1] \\ f[n]\\ f[n – 1]\end{bmatrix} = \begin{bmatrix}1& 0 &1\\ 1& 0& 0\\0& 1& 0\end{bmatrix} \begin{bmatrix} f(n) \\ f(n – 1)\\ f(n – 2)\end{bmatrix} \]
 So in order to generalize the matrix derivation, lets consider following equation
f(n) = A x f(n -1) + B x f(n – 2) + C x f(n -3) + D x f(n -4) + ….
\[=\begin{bmatrix}A& B &C\\ 1& 0& 0\\0& 1& 0\end{bmatrix} \begin{bmatrix} f(n) \\ f(n – 1)\\ f(n – 2)\end{bmatrix} \]
 And replace A, B, C, D values accordingly as per the Fibonacci sequence is considered.
Hope you find this blog interesting. Please do comment if you have any doubts or if there is any update to post.

2 thoughts on “Fibonacci Number for very large value 10^10^10 continued

Comments are closed.

Comments are closed.