brent cycle detection algorithm


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Tags

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)))