lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


> 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