Discussion on: Let's Get Clever #1: Fibonacci Sequence

[Curtis Fenner]

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 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.

local function matmul(a, b, c, d, x, y, z, w)
    return a*x+b*z, a*y+b*w, c*x+d*z, c*y+d*w
end

local function matsq(a, b, c, d)
    return matmul(a, b, c, d, a, b, c, d)
end

local function fib(n)
    local a, b, c, d = 1, 0, 1, 0
    local x, y, z, w = 0, 1, 1, 1
    while n > 0 do
        if n % 2 == 1 then
            a, b, c, d = matmul(x, y, z, w, a, b, c, d)
        end
        n = n // 2
        x, y, z, w = matsq(x, y, z, w)
    end
    return a
end

print(fib(16)) --> 987

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.