Download or view cycleDetect.frink in plain text format
/** This is a library to detect cycles in a sequence.
See:
https://en.wikipedia.org/wiki/Cycle_detection
Hacker's Delight:
https://web.archive.org/web/20160414011322/http://hackersdelight.org/hdcodetxt/loopdet.c.txt
Rosetta code:
https://rosettacode.org/wiki/Cycle_detection
*/
/** Detect a cycle in a function using Brent's method.
args: [f, x0]
where
f: a function that returns the successor value to f[x]
x0: the starting value passed to the function.
returns:
[cycleStartIndex, cycleLength, cycleStartValue]
*/
detectCycleBrentFunction[f, x0] :=
{
cycleLength = undef
hare = x0
power = 1
// Main phase: search successive powers of two.
FOUND:
while true
{
tortoise = hare
for i = 1 to power-1
{
hare = f[hare]
if (tortoise == hare)
{
cycleLength = i
break FOUND
}
}
power = power * 2
}
// Find the position of the first repetition of cycleLength
tortoise = hare = x0
for i = 1 to cycleLength
hare = f[hare]
// Distance between tortoise and hare is now cycleLength
// Now the hare and tortoise move at the same speed until they agree
cycleStartIndex = 0
while tortoise != hare
{
cycleStartIndex = cycleStartIndex + 1
tortoise = f[tortoise]
hare = f[hare]
}
// tortoise contains cycle start value.
return [cycleStartIndex, cycleLength, tortoise]
}
/** Helper function to regenerate the cycle from a function,
original starting value, starting index, and cycleLength */
makeCycle[f, x0, cycleStartIndex, cycleLength] :=
{
result = new array
val = x0
for i = 1 to cycleStartIndex
val = f[val]
result.push[val]
for j = 1 to cycleLength-1
{
val = f[val]
result.push[val]
}
return result
}
// Sample test
f = {|x| (x^2 + 1) mod 255}
x0 = 3
[cycleStartIndex, cycleLength, startValue] = detectCycleBrentFunction[f, x0]
cycle = makeCycle[f, startValue, 0, cycleLength]
println["Cycle start index: $cycleStartIndex"]
println["Cycle length: $cycleLength"]
println["Cycle start value: $startValue"]
println["Cycle: $cycle"]
Download or view cycleDetect.frink in plain text format
This is a program written in the programming language Frink.
For more information, view the Frink
Documentation or see More Sample Frink Programs.
Alan Eliasen, eliasen@mindspring.com