--[[
	lazy evaluation of Fibonacci sequence with big numbers
--]]
local bc = require "bc"

-- describe a recurrence relation for Fibonacci numbers
local function fibRecurrence(seq, n)
	if rawget(seq, n) then return rawget(seq, n) end;
	table.insert(seq, bc.add(seq[#seq], seq[#seq - 1]))
	return fibRecurrence(seq, n)
end

-- describe a list with initial values 0 and 1 with fibRecurrence relation
local fibonacci = setmetatable({0,1}, {__index=fibRecurrence})

-- describe action to print 10000th element
local main = function () print(fibonacci[10000]) end

-- desribe entry-point
return main()

--[[
$ lua fibonacci.lua | fold -w79
2079360823713349807211264898864283682508703609401590311968294586652850142345568
6648927456034305226515591757343297190158010624794267250973176133810179902738038
2317897483462355564831914315919245323944200280678103204087244146934628490626683
8708330804825092065449334087873322637758084744632487379760373479464825811385863
1550404081017260381202919943892370942852601647398213554479081823593715429566945
1493129936648467790904377992847736753792842706601751346648332663776986420121068
9135579114187277693408080350495679409464829288056605636471818766266897075853738
3352677420835574155945658542003634765324541006121012446785689171494803262408602
6930912116019739382294466360499015319632861596990778804277202892355393296718771
8291564341907918652511867885682160089752017107049943765706734240087108390881180
0976259727431820539554256869460815355918458253398234382360435762759823179896116
7484242695459246332046141379928508143520187384809235815539889908971514694061316
9561449778372074346137375621868510685682609069633981549092125371453724186691160
4250597353747823733268178182198509240226955826416016690084749816072843582488613
1848299053831501800478443537515542015738331055219809981238332532612286898240517
7784658846107979080782836713238479845179401107656905752215868037896153216085838
7223882974380483931929541222100800313580688585002598879566463221427820448492565
0731065958088374016489964235633861097820456341224678729218456064091743606356182
1688381256232166444282295253757749271536532113420453068674243545450510326976814
4370118494906390254934942358904031509877369722437053383165360388595116980245927
9352259015376349256548723808771830083010745694440024264364147569050945350728047
6468449210568002473991449055590439136921869638709291818924615710345038705022930
0603241611410707453960080170928277951834763216705242485820801423866526633816082
9214428830954632590804718193292017101478280252213856563402074897963176632788722
0760779103443170011275355881347888872750382538906682309868335569571813786788298
2111710796422706778536913192342733364556727928018953989153106047379741280794091
639429908796650294603536651238230626
--]]