## brent cycle detection algorithm

in lua

### Source Code

``````-- Brent cycle finding algorithm
-- See: http://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algorithm

-- Detects cycle in a given sequence
-- f       : a function which returns the next element (i.e f(x0) = x1, f(x1) = x2, ...)
-- x0      : the initial element
-- returns : the cycle (loop) position, or tail
-- returns : the cycle (loop) length
return function (f, x0)
local pow, lambda, tortoise, hare = 1, 1, x0, f(x0)

while tortoise ~= hare do
if not tortoise or not hare then return nil end
if pow == lambda then
tortoise, pow, lambda = hare, pow * 2, 0
end
hare, lambda = f(hare), lambda + 1
end

local mu = 0
tortoise, hare = x0, x0
for i = 0, lambda - 1 do hare = f(hare) end

while tortoise ~= hare do
tortoise = f(tortoise)
hare = f(hare)
mu = mu + 1
end

return lambda, mu
end
``````
``````-- Tests for brent.lua
local brent = require 'brent'

local total, pass = 0, 0

local function dec(str, len)
return #str < len
and str .. (('.'):rep(len-#str))
or str:sub(1,len)
end

local function run(message, f)
total = total + 1
local ok, err = pcall(f)
if ok then pass = pass + 1 end
local status = ok and 'PASSED' or 'FAILED'
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Brent cycle detection test', function()
local t = {}
for i = 1,7 do t[i] = {} end
for i = 1,6 do t[i].next = t[i+1] end
t[7].next = t[2]

local function f(n) return n and n.next end
local len, tail = brent(f, t[1])
assert(len == 6 and tail == 1)

t[7].next = t[5]
len, tail = brent(f, t[1])
assert(len == 3 and tail == 4)

t[7].next = nil
assert(brent(f, t[1]) == nil)
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
:format(total, pass, total-pass, (pass*100/total)))
``````