[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: Learning Lua
- From: Luiz Henrique de Figueiredo <lhf@...>
- Date: Fri, 17 Sep 2010 03:58:47 -0300
> function mesure(n)
> local i = 0
> while n ~= 1 do
> if n % 2 == 0 then n = n / 2
> else n = 3*n + 1 end
> i = i + 1
> end
> return i
> end
For this specific problem, memoization gives lots of improvement.
Here is a memoized version that runs much faster then the function above.
On a 5-year old PowerBook G4 this code runs in 3 secs while the original
code runs in 13 secs.
local cache={}
function mesure(x)
local y=cache[x]
if y==nil then
if x==1 then
y=0
elseif x%2==0 then
y=1+mesure(x/2)
else
y=1+mesure(3*x+1)
end
cache[x]=y
end
return y
end