Fibonacci using matrix multiplication

[enedil]

Hello.
I'm not fluent in Java so I won't implement it by myself, however there is an O(log n) solution for finding nth Fibonacci number which is based on matrix exponentiation -

[[1 1] [1 0]]^n = [[F_{n+1} F_n] [F_n F_{n-1}]]

This can be done with exponentiation by squaring which is O(log n).

[sherxon]

hi Thank you, i will add solution using this approach later

[cktang88]

There's also a constant O(1) closed-form formula for the Nth fibonacci number - Binet's Formula

[enedil]

@cktang88 uhmm, it's not? There's exponentiation here which uses at least O(log n) multiplications. Moreover, these are floating point numbers, which are probably slower to operate on than four integers.

[cktang88]

@enedil yes, you're correct. The matrix exponentiation would be more efficient from a CS point of view.