You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
80 lines
1.8 KiB
80 lines
1.8 KiB
-- The Computer Language Benchmarks Game
|
|
-- http://benchmarksgame.alioth.debian.org/
|
|
-- contributed by Mike Pall
|
|
|
|
local function fannkuch(n)
|
|
local p, q, s, sign, maxflips, sum = {}, {}, {}, 1, 0, 0
|
|
for i=1,n do
|
|
p[i] = i;
|
|
q[i] = i;
|
|
s[i] = i
|
|
end
|
|
repeat
|
|
-- Copy and flip.
|
|
local q1 = p[1] -- Cache 1st element.
|
|
if q1 ~= 1 then
|
|
for i=2,n do
|
|
q[i] = p[i]
|
|
end -- Work on a copy.
|
|
local flips = 1
|
|
repeat
|
|
local qq = q[q1]
|
|
if qq == 1 then -- ... until 1st element is 1.
|
|
sum = sum + sign*flips
|
|
if flips > maxflips then
|
|
maxflips = flips
|
|
end -- New maximum?
|
|
break
|
|
end
|
|
q[q1] = q1
|
|
if q1 >= 4 then
|
|
local i, j = 2, q1 - 1
|
|
repeat
|
|
q[i], q[j] = q[j], q[i];
|
|
i = i + 1;
|
|
j = j - 1;
|
|
until i >= j
|
|
end
|
|
q1 = qq;
|
|
flips = flips + 1
|
|
until false
|
|
end
|
|
-- Permute.
|
|
if sign == 1 then
|
|
p[2], p[1] = p[1], p[2]; sign = -1 -- Rotate 1<-2.
|
|
else
|
|
p[2], p[3] = p[3], p[2]; sign = 1 -- Rotate 1<-2 and 1<-2<-3.
|
|
for i=3,n do
|
|
local sx = s[i]
|
|
if sx ~= 1 then
|
|
s[i] = sx-1;
|
|
break
|
|
end
|
|
if i == n then
|
|
return sum, maxflips
|
|
end -- Out of permutations.
|
|
s[i] = i
|
|
-- Rotate 1<-...<-i+1.
|
|
local t = p[1];
|
|
for j=1,i do
|
|
p[j] = p[j+1]
|
|
end;
|
|
p[i+1] = t
|
|
end
|
|
end
|
|
until false
|
|
end
|
|
|
|
local n = tonumber(arg and arg[1]) or 1
|
|
if ravi then
|
|
ravi.compile(fannkuch)
|
|
end
|
|
if jit then
|
|
-- luajit - warmup
|
|
fannkuch(n)
|
|
end
|
|
local t1 = os.clock()
|
|
local sum, flips = fannkuch(n)
|
|
local t2 = os.clock()
|
|
io.write(sum, "\nPfannkuchen(", n, ") = ", flips, "\n")
|
|
io.write("elapsed time in secs ", (t2-t1), "\n") |