fibonacci series


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Tags

recursion

Source Code

-- Fibonacci series implementation
-- See: http://en.wikipedia.org/wiki/Fibonacci_number
-- Implementation note:
--  With respect to Lua's array numbering, with starts at 1,
--  the following assumes that, given a function F which returns
--  the i-th term in a Fibonacci series,
--  F(0) is undefined
--  F(1) = 1
--  F(2) = 1
--  F(n) = F(n-1) + F(n-2), given any n > 2

-- Custom memoization function
local function memoize(f)
  local _cache = {}
  return function (v)
    local _result = _cache[v]
    if not _result then _cache[v] = f(v) end
    return _cache[v]
  end
end

-- Recursive evaluation of fibonacci series
-- n: the i-th Fibonacci number

local function fib(n)
  if n > 0 and n <= 2 then return 1 end
  return fib(n-1) + fib(n-2)
end

-- Iterator for Fibonacci series
-- usage:
--  for count, value in fib_iter(limit) do ... end
local function fib_iter(n)
	assert(n > 0, 'Expected n >= 0!')
	return coroutine.wrap(function()
		local a, b, k = 0, 1, 0
		while k < n do
			a, b = b, a+b
			k = k + 1
			coroutine.yield(k, a)
		end
	end)
end

return {
	fib = memoize(fib),
	fib_iter = fib_iter
}
-- Tests for fib.lua
local fib      = (require 'fib').fib
local fib_iter = (require 'fib').fib_iter

local total, pass = 0, 0

local function dec(str, len)
	return #str < len
	   and str .. (('.'):rep(len-#str))
		  or str:sub(1,len)
end

local function run(message, f)
	total = total + 1
	local ok, err = pcall(f)
	if ok then pass = pass + 1 end
	local status = ok and 'PASSED' or 'FAILED'
	print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Fails on running with no arg or 0', function()
	assert(not pcall(fib))
	assert(not pcall(fib, 0))
	assert(not pcall(fib_iter))
	assert(not pcall(fib_iter, 0))
end)

run('Evaluates the i-th term in fibonacci series', function()
	local fib_values = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144}
	for i,v in ipairs(fib_values) do
		assert(v == fib(i))
	end

	for i,v in fib_iter(#fib_values) do
		assert(fib_values[i], i,v)
	end

end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
	:format(total, pass, total-pass, (pass*100/total)))