tonetheman's blog

lua and fib

Randomly wrote fib function. One with a backing store and one without... needless to say the slow one is really slow compared to the cached version.

local compute_count = 0

-- backing store with first 2 fib numbers
local backing = {0,1}

-- fairly standard way to compute fib
function slowfib(n)
    -- check the backing for the first cases
    if n==1 then
        return backing[1]
    elseif n==2 then
        return backing[2]
        compute_count = compute_count + 1
        -- otherwise recursive call to get the values
        -- this can be slow just from the number of calls
        return slowfib(n-1) + slowfib(n-2)

-- faster version
-- using the backing store when it is avail
-- like memoization ... or maybe it is really
-- using a cache like a boss
function fib(n)
    -- if it is 1 or 2 then these are hardcoded into the backing storage
    if n==1 then
        return backing[1]
    elseif n==2 then
        return backing[2]
        -- otherwise check if the backing has it
        -- and use that if possible
        if backing[n] ~= nil then
            return backing[n]
            -- compute it blech
            compute_count = compute_count + 1

            -- recursive call here
            -- but in this case if we already have the value
            -- it is no cost! the joy of caching
            local v = fib(n-1)+fib(n-2)
            -- save it since we took the hit on the work
            backing[n] = v
            -- return the value
            return v

-- something to hold the coroutines
local workers = {}
for i=1,30 do
    -- make them and save them
    -- this does not start the work
    -- they start suspended
    local co = coroutine.create(fib)

-- do the work
-- print the result
for i,v in ipairs(workers) do

-- dump the backing store to console
for i,v in ipairs(backing) do
    print("backing", i,v)

-- how many times did we really do work?
-- on slowfib it is a lot
-- on fib it is very low
print("total compute count",compute_count)