lua
#!/usr/local/bin/lua-5.1

-- A simple lua program

function fib1(n)
    -- Recursive algorithm
    if n < 2 then
        return 1
    end

    return fib1(n - 1) + fib1(n - 2)
end

function fib2(n)
    -- Linear algorithm
    a = {1, 1}

    for c = 3, n do
        a[c] = a[c - 1] + a[c - 2]
    end

    return a[n]
end

function fib3(n)
    -- Direct calculate
    -- Ref: http://en.wikipedia.org/wiki/Fibonacci_number
    return math.floor(math.pow(((1 + math.sqrt(5)) / 2), n) / math.sqrt(5))
end

print(string.format("%s %s:", "It's", "recursive version"))
f1 = fib1(10)
print(type(f1), f1)
print()

print([[It's linear algorithm version:]])
f2 = fib2(10)
print(type(f2), f2)
print()

print([=[It's math]=] .. [==[ algorithm version:]==])
f3 = fib3(10)
print(type(f3), f3)
print()