Specifically, the transition a', b' := b, a+b can be written as a matrix [[a'][b']] = [[0, 1][1, 1]] * [[a][b]]. Then we can use the fact that applying this n times to get the nth Fibonacci number is the same thing as multiplying the initial state of [[1]][[0]] by the nth power of the matrix [[0,1][1,1]].
Computing the nth power of an object can be done faster than merely multiplying n times. Instead, to compute a^n, we can compute (a^(n/2))^2, which halves the number of multiplications we need to do.
If you want really, really big Fibonacci numbers, this algorithm will be much better than the simple for loop approach, because it requires only logarithmically many arithmetic operations instead of linearly many. For very large values, it's also better than the closed-form solution since you don't have to worry about getting arbitrary precision square roots and exponents. The actual time complexity isn't logarithmic, since arithmetic operations themselves are linear in the number of digits of the values; the overall execution time is thus linear in n since the Fibonacci sequence grows exponentially.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Here's Lua, using the matrix-squaring approach.
Specifically, the transition
a', b' := b, a+b
can be written as a matrix[[a'][b']] = [[0, 1][1, 1]] * [[a][b]]
. Then we can use the fact that applying thisn
times to get then
th Fibonacci number is the same thing as multiplying the initial state of[[1]][[0]]
by then
th power of the matrix[[0,1][1,1]]
.Computing the
n
th power of an object can be done faster than merely multiplyingn
times. Instead, to computea^n
, we can compute(a^(n/2))^2
, which halves the number of multiplications we need to do.If you want really, really big Fibonacci numbers, this algorithm will be much better than the simple
for
loop approach, because it requires only logarithmically many arithmetic operations instead of linearly many. For very large values, it's also better than the closed-form solution since you don't have to worry about getting arbitrary precision square roots and exponents. The actual time complexity isn't logarithmic, since arithmetic operations themselves are linear in the number of digits of the values; the overall execution time is thus linear inn
since the Fibonacci sequence grows exponentially.