using LinearAlgebra

function slowfib(n)
    if n < 2
        return BigInt(1) # use bigint type to support huge integers
    else
        return slowfib(n-1) + slowfib(n-2)
    end
end

[slowfib(n) for n = 1:10]

function fastfib(n)
    z = BigInt()
    ccall((:__gmpz_fib_ui, :libgmp), Cvoid, (Ref{BigInt}, Culong), z, n)
    return z
end

[fastfib(i) for i = 1:100]

@time fastfib(20)
@time fastfib(20)
@time fastfib(20)
@time slowfib(20)
@time slowfib(20)
@time slowfib(20)

F = [1 1
     1 0]

F^7 * [1,1]

eigvals(F)

(1 + √5)/2

(1 - √5)/2

big.(F)^98 * [1, 1]

fastfib(100), fastfib(99)

(1 + √big(5))/2 # golden ratio computed to many digits

fastfib(101) / fastfib(100)

using PyPlot
plot(1:10, [Float64(fastfib(n+1)/fastfib(n)) for n=1:10], "ro-")
plot([0,10], (1+√5)/2 * [1,1], "k--")
xlabel(L"n")
ylabel(L"f_{n+1}/f_n")
title("ratios of successive Fibonacci numbers")