# Calculate fibonacci in O(log n)

This program calculates the $n$th fibonacci number, in $O(\log n)$ time. I'm looking for code review, optimizations, and best practices.

public final class Fibo {

private Fibo() { }

public static int getNthfibo(int n) {
if (n < 0) {
throw new IllegalArgumentException("The fibo value cannot be negative");
}

if (n <= 1) return n;

int[][] result = {{1, 0}, {0, 1}}; // identity matrix.
int[][] fiboM = {{1, 1}, {1, 0}};

while (n > 0) {
if (n%2 == 1) {
multMatrix(result, fiboM);
}
n = n / 2;
multMatrix(fiboM, fiboM);
}

return result[1][0];
}

private static void multMatrix(int[][] m, int [][] n) {
int a = m[0][0] * n[0][0] +  m[0][1] * n[1][0];
int b = m[0][0] * n[0][1] +  m[0][1] * n[1][1];
int c = m[1][0] * n[0][0] +  m[1][1] * n[0][1];
int d = m[1][0] * n[0][1] +  m[1][1] * n[1][1];

m[0][0] = a;
m[0][1] = b;
m[1][0] = c;
m[1][1] = d;
}

public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.println(getNthfibo(i));
}
}
}

• Small nitpick: n = n / 2; can just be n /= 2;. – Jamal May 27 '14 at 21:30
• int c = m[1][0] * n[0][0] + m[1][1] * n[0][1]; is wrong, it should end with n[1][0]. (But it still works because n is fiboM which is a symmetric matrix.) – David Knipe May 29 '14 at 23:20
• How can I use this way to find general series? I mean, not starting with 0 and 1, but for example, starting from 9 and 5, then 9+5 = 14, 14+9 = 23, 23+14.....?? – Johnny Willer Jun 15 '16 at 22:22

## Using int as a return value for Fibonacci

I've changed main thus:

for (int i = 0; i < 100; i++) {
System.out.println(i + " " + getNthfibo(i));
}


Sample output from the above code:

45 1134903170
46 1836311903
47 -1323752223
48 512559680


Fibonacci is an exponentially growing series. So by $F$47 you are out of the range of int. $O(n)$ and $O(log n)$ are asymptotic performance statements, and you may not have received much benefit from it for input sizes $0 <= n < 47$.

int has 31 significant bits, double has 52/53 significant bits. So you could just use the closed form of Fibonacci series to calculate $F$n up to Integer.MAX_VALUE in constant time (using doubles and rounding to nearest int), if linear was too slow w.r.t. logarithmic time.

Your code seems to be working properly so there is not much to say on this.

The only changes I would perform would be to make things easier to understand through different little steps.

• Multiplication could return a result

At the moment, your multiplication procedure stores the result in the first argument. First issue is that it cannot be generalised to product of non-square matrices. The second issue is that it can make things a bit hard to understand when looking at the code using your function (getNthfibo in your case). It is a fairly easy change to perform :

private static int[][] multMatrix(int[][] m, int [][] n) {
int a = m[0][0] * n[0][0] +  m[0][1] * n[1][0];
int b = m[0][0] * n[0][1] +  m[0][1] * n[1][1];
int c = m[1][0] * n[0][0] +  m[1][1] * n[0][1];
int d = m[1][0] * n[0][1] +  m[1][1] * n[1][1];
int[][] ret = {
{a, b},
{c, d}};
return ret;
}


result = multMatrix(result, fiboM); and fiboM = multMatrix(fiboM, fiboM);

• The signature of the multMatrix method lets us think that is works for any matrices.

Actually, it only works for 2*2 matrices. This should be documented and checked at runtime (because it doesn't seem to be possible to do so at compilation time).

• Making Mathematics a bit more obvious

Values can be reformatted in such a way that the mathematics behind are easier to understand. Also, a little bit of comment can help.

    int[][] result = {
{1, 0},
{0, 1}};

/*         n
* [ 1 1 ]     [ F(n+1) F(n)   ]
* [ 1 0 ]   = [ F(n)   F(n-1) ]
*/
int[][] fiboM = {
{1, 1},
{1, 0}};