Re: luajit2 BUG
- From: David Davidović <geosoft.corp@xxxxxxxxx>
- To: luajit@xxxxxxxxxxxxx
- Date: Mon, 14 Sep 2015 12:17:42 +0200
On Thu, Sep 10, 2015 at 9:10 AM, zzz654321 <zzz654321@xxxxxxx> wrote:
local function fib(n )
if n < 3 then return n - 1 end
return fib(n - 2) + fib(n - 1)
end
local t1= os.clock() local t2= fib(32 ) t1=os.clock()- t1
on android, the code is very slow, please check the bug.
Although that particular slowness probably isn't related to this (since it
doesn't manifest everywhere, as you say)---you're using a horribly inefficient
implementation of fib(n). You are essentially calling the function twice for
every n, which makes the complexity of your algorithm O(2**n). A basic
iterative solution, such as
function fib(n)
local a = 1
local b = 1
for i=3,n do
local tmp = b
b = b + a
a = tmp
end
return b
end
Will run in O(n) time, which will allow you to compute these values
efficiently. Your implementation, on my system, takes 1.5s to compute fib(40),
which is, of course, egregious.
- David
Other related posts:
