lua-users home
lua-l archive

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

On 16 September 2010 23:19, Mike Pall <> wrote:
Victor Poughon wrote:
> When running it until 1,000,000 it finishes in about 15 seconds. (I have a
> 1.83Ghz processor).
> I'm not really concerned about performance, and i'm sure there's a better
> algorithm for solving this problem. But an equivalent algorithm in
> C<>finishes about 6 times faster.
> Is this what one should expect from Lua ?

It runs 8.5x faster with LuaJIT.

Obviously algorithmic improvements pay off a lot here. The
following code takes 60 milliseconds on my machine with LuaJIT:

local bit = require("bit")
local bnot, bor, band = bit.bnot, bit.bor,
local shl, shr = bit.lshift, bit.rshift

local N = tonumber(arg and arg[1]) or 1000000
local cache, m, n = { 1 }, 1, 1
for i=2,N do
 local j = i
 for len=1,1000000000 do
   j = bor(band(shr(j,1), band(j,1)-1), band(shl(j,1)+j+1, bnot(band(j,1)-1)))
   local x = cache[j]; if x then j = x+len; break end
 cache[i] = j
 if j > m then m, n = j, i end
io.write("Found ", n, " (chain length: ", m, ")\n")


That code may well be faster but it is horrible code that someone learning the language should not have to look at.