# Lua and the space/time duality (1 Viewer)

Functions `f(x)` use a fixed amount of space and who knows how much time, whereas tables `t[x]` use a fixed amount of time and who knows how much space. The traditional speed-up, trading space for time, is called memoization:
Code:
``````memoize = function (f)
local t = { }
return function (x)
local a = t[x]
if not a then
a = f(x)
t[x] = a
end -- if
return a
end -- function
end -- function``````
For example, the traditional Fibonacci function:
Code:
``````fib = function (n)
if n < 2 then return n end -- if
return f(n-1) + f(n-2)
end -- function``````
is hopelessly inefficient, but `memoize (fib)` is much better.
But Lua, uniquely I suspect, lets us trade in the other direction, delaying the filling of a table:
Code:
``````local t = setmetatable ( { 0, 1}, {
__index = function (f,x)
local a = f[x-1] + f[x-2]
f[x] = a
return a
end -- function
})
newfib = function (x) return t[x] end -- function``````
The function `newfib` is better still. Are there other languages that make this space/time duality so explicit?

#### gaurami

##### Newcomer
I had to make a correction in the third example:

local t = setmetatable ( { 1, 1}, {
...

to make it produce the same results as the first two examples, but I can't figure out why it works much faster than the "memorized" Fibonacci. Could somebody explain it in the plain Beginnerish?

Last edited:

#### GavinW

##### Newcomer
Creator of RiscLua
Thanks for the correction. Why is `newfib` faster? I think it is because table-lookup is faster than function-calling. The point of memoization is to obey the adage "never calculate the same value twice". Ask yourself how many Lua function calls does it take to calculate the n-th Fibonacci number, using these methods? Table-lookup obviously involves a C-function, as does addition, but these are the only operations after the first call to `newfib`, which calls a Lua function only once. On the other hand `memoize(fib)` needs to call n Lua-functions, one for each of the numbers less than its argument. Is that any help?

#### gaurami

##### Newcomer
Thanks! It's getting clearer: newfib delegates almost all work to C-functions (O( n ) calls of the lookup and the addition functions), while memoize(fib) does almost the same but calling repeatedly Lua functions - correct?

#### GavinW

##### Newcomer
Creator of RiscLua
Yes. From the mathematical point of view `f(x)` and `f[x]` are the same, but computationally they are different. Lua's meta(tables/methods) are very interesting, I think. On the face of it, they seem only to be about tweaking notation, but in fact they give the programmer more flexibility with evaluation strategies. That was really the point I was trying to get across. But meta-magic is an aspect of Lua that is probably fairly frightening for newcomers to the language. It took a while to evolve to its present generality, and I do not know of any other languages with anything similar.