Cycle detection
Detect a cycle in an iterated function using Brent's algorithm.
Detecting cycles in iterated function sequences is a sub-problem in many computer algorithms, such as factoring prime numbers. Some such algorithms are highly space efficient, such as Floyd's cycle-finding algorithm, also called the "tortoise and the hare algorithm". A more time efficient algorithm than "tortoise and hare" is Brent's Cycle algorithm. This task will implement Brent's algorithm.
See https://en.wikipedia.org/wiki/Cycle_detection for a discussion of the theory and discussions of other algorithms that are used to solve the problem.
When testing the cycle detecting function, you need two things:
1) An iterated function
2) A starting value
The iterated function used in this example is: f(x) = (x*x + 1) modulo 255.
The starting value used is 3.
With these as inputs, a sample program output would be:
3,10,101,2,5,26,167,95,101,2,5,26,167,95,101,2,5,26,167,95,101,2,5,26,167,95,101,2,5,26,167,95,101,2,5,26,167,95,101,2,5
Cycle length = 6
Start index = 2
The output prints the first several items in the number series produced by the iterated function, then identifies how long the cycle is (6) followed by the zero-based index of the start of the first cycle (2). From this you can see that the cycle is:
101,2,5,26,167,95
C#
This solution uses generics, so may find cycles of any type of data, not just integers.
<lang C#>
// First file: Cycles.cs // Author: Paul Anton Chernoch
using System;
namespace DetectCycles {
/// <summary> /// Find the length and start of a cycle in a series of objects of any IEquatable type using Brent's cycle algorithm. /// </summary> public class Cycles<T> where T : IEquatable<T> { /// <summary> /// Find the cycle length and start position of a series using Brent's cycle algorithm. /// /// Given a recurrence relation X[n+1] = f(X[n]) where f() has /// a finite range, you will eventually repeat a value that you have seen before. /// Once this happens, all subsequent values will form a cycle that begins /// with the first repeated value. The period of that cycle may be of any length. /// </summary> /// <returns>A tuple where: /// Item1 is lambda (the length of the cycle) /// Item2 is mu, the zero-based index of the item that started the first cycle.</returns> /// <param name="x0">First item in the series.</param> /// <param name="yielder">Function delegate that generates the series by iterated execution.</param> public static Tuple<int,int> FindCycle(T x0, Func<T,T> yielder) { int power, lambda; T tortoise, hare; power = lambda = 1; tortoise = x0; hare = yielder(x0);
// Find lambda, the cycle length while (!tortoise.Equals (hare)) { if (power == lambda) { tortoise = hare; power *= 2; lambda = 0; } hare = yielder (hare); lambda += 1; }
// Find mu, the zero-based index of the start of the cycle var mu = 0; tortoise = hare = x0; for (var times = 0; times < lambda; times++) hare = yielder (hare); while (!tortoise.Equals (hare)) { tortoise = yielder (tortoise); hare = yielder (hare); mu += 1; }
return new Tuple<int,int> (lambda, mu); } }
}
// Second file: Program.cs
using System;
namespace DetectCycles { class MainClass { public static void Main (string[] args) { // A recurrence relation to use in testing Func<int,int> sequence = (int _x) => (_x * _x + 1) % 255;
// Display the first 41 numbers in the test series var x = 3; Console.Write(x); for (var times = 0; times < 40; times++) { x = sequence(x); Console.Write(String.Format(",{0}", x)); } Console.WriteLine();
// Test the FindCycle method var cycle = Cycles<int>.FindCycle(3, sequence); var clength = cycle.Item1; var cstart = cycle.Item2; Console.Write(String.Format("Cycle length = {0}\nStart index = {1}\n", clength, cstart)); } } }
</lang>
J
Brute force implementation:
<lang J>cdetect=:1 :0
r=. ~.@(,u@{:)^:_ y n=. u{:r (,(#r)-])r i. n
)</lang>
In other words: iterate until we stop getting new values, find the repeated value, and see how it fits into the sequence.
Example use:
<lang J> 255&|@(1 0 1&p.) cdetect 3 2 6</lang>
(Note that 1 0 1 are the coefficients of the polynomial 1 + (0 * x) + (1 * x * x)
- it's easier and probably more efficient to just hand the coefficients to p. than it is to write out some other expression which produces the same result.)
Java
<lang java>import java.util.function.*; import static java.util.stream.IntStream.*;
public class CycleDetection {
public static void main(String[] args) { brent(i -> (i * i + 1) % 255, 3); }
static void brent(IntUnaryOperator f, int x0) { int power = 1; int cycleLength = 1; int tortoise = x0;
int hare = f.applyAsInt(x0); for (;tortoise != hare; cycleLength++) { if (power == cycleLength) { tortoise = hare; power *= 2; cycleLength = 0; } hare = f.applyAsInt(hare); }
tortoise = hare = x0; for (int i = 0; i < cycleLength; i++) hare = f.applyAsInt(hare);
int cycleStart = 0; for (; tortoise != hare; cycleStart++) { tortoise = f.applyAsInt(tortoise); hare = f.applyAsInt(hare); }
printResult(x0, f, cycleLength, cycleStart); }
static void printResult(int x0, IntUnaryOperator f, int len, int start) { System.out.printf("Cycle length: %d%nCycle: ", len); iterate(x0, f).skip(start).limit(len) .forEach(n -> System.out.printf("%s ", n)); }
}</lang>
Cycle length: 6 Cycle: 101 2 5 26 167 95
ooRexx
<lang ooRexx>/* REXX */ x=3 list=x Do i=1 By 1
x=f(x) p=wordpos(x,list) If p>0 Then Do list=list x Say 'list ='list '...' Say 'Start index = ' (wordpos(x,list)-1) '(zero based)' Say 'Cycle length =' (words(list)-p) Say 'Cycle =' subword(list,p,(words(list)-p)) Leave End list=list x End
Exit f: Return (arg(1)**2+1)//255 </lang>
- Output:
list =3 10 101 2 5 26 167 95 101 ... Start index = 2 (zero based) Cycle length = 6 Cycle = 101 2 5 26 167 95
REXX
Brent's algorithm
<lang rexx>/*REXX pgm detects a cycle in an iterated function [F] using Brent's algorithm*/ init=3; @=init /* [↓] show a line of function values.*/
do until length(@)>79; @=@ f(word(@,words(@))); end; say @ ...
call Brent init /*invoke Brent algorithm for func F. */ parse var result cycle idx /*obtain the two values returned from F*/ say 'cycle length = ' cycle /*display the cycle. */ say 'start index = ' idx " ◄─── zero index" /* " " index. */ say 'the sequence = ' subword(@, idx+1, cycle) /* " " sequence.*/ exit /*stick a fork in it, we're all done. */ /*────────────────────────────────────────────────────────────────────────────*/ Brent: procedure; parse arg x0 1 tort; pow=1; #=1 /*tort is set to X0*/ hare=f(x0) /*get 1st value for the func. */
do while tort\==hare if pow==# then do; tort=hare /*set value of TORT to HARE. */ pow=pow+pow /*double the value of POW. */ #=0 /*reset # to zero (lambda).*/ end hare=f(hare) #=#+1 /*bump the lambda count value.*/ end /*while*/
hare=x0
do #; hare=f(hare) /*generate number of F values.*/ end /*j*/
tort=x0 /*find position of the 1st rep*/
do mu=0 while tort\==hare /*MU is a zero─based index.*/ tort=f(tort) hare=f(hare) end /*mu*/
return # mu /*────────────────────────────────────────────────────────────────────────────*/ f: return (arg(1)**2 + 1) // 255 /*this defines/executes the function F.*/</lang> output using the defaults:
3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 101 ... cycle length = 6 start index = 2 (zero index) start index = 2 ◄─── zero index the sequence = 101 2 5 26 167 95
sequential search algorithm
<lang rexx>/*REXX pgm detects a cycle in an iterated function [F] using sequential search*/ x=3; @=x
do until cycle\==0; x=f(x) /*calculate another num*/ cycle=wordpos(x,@) /*is this a repeat ? */ @=@ x /*append number to list*/ end /*until*/
- =words(@)-cycle /*compute cycle length.*/
say ' original list=' @ ... /*display the sequence.*/
say 'numbers in list=' words(@) /*display number of #s.*/
say ' cycle length =' # /*display the cycle. */
say ' start index =' cycle-1 " ◄─── zero based" /* " " index. */
say 'cycle sequence =' subword(@,cycle,#) /* " " sequence.*/
exit /*stick a fork in it, we're all done. */
/*────────────────────────────────────────────────────────────────────────────*/
f: return (arg(1)**2 + 1) // 255 /*this defines/executes the function F.*/</lang>
output is the same as the 1st REXX version (sequential search).
hash table algorithm
This REXX version is a lot faster (than the sequential search algorithm) if the cycle length and/or start index is large. <lang rexx>/*REXX pgm detects a cycle in an iterated function [F] using a hash table. */ x=3; @=x; !.=.; !.x=1
do n=1+words(@); x=f(x); @=@ x /*add number to list. */ if !.x\==. then leave /*A repeat? Then leave*/ !.x=n /*N: numbers in @ list*/ end /*n*/
say ' original list=' @ ... /*maybe show the list.*/
say 'numbers in list=' n /*display num of nums.*/
say ' cycle length =' n-!.x /* " " cycle. */
say ' start index =' !.x-1 ' ◄─── zero based' /* " " index. */
say 'cycle sequence =' subword(@, !.x, n-!.x) /* " " sequence*/
exit /*stick a fork in it, we're all done. */
/*────────────────────────────────────────────────────────────────────────────*/
f: return (arg(1)**2 + 1) // 255 /*this defines/executes the function F.*/</lang>
output is the same as the 1st REXX version (sequential search).
Variant of above (hash table algorithm)
There is more information in the "hash table"
and f has no "side effect".
<lang rexx>/*REXX pgm detects a cycle in an iterated function [F] */
x=3; list=x; p.=0; p.x=1
Do q=2 By 1
x=f(x) /* the next value */ list=list x /* append it to the list */ If p.x>0 Then Do /* x was in the list */ cLen=q-p.x /* cycle length */ Leave End p.x=q /* note position of x in the list */ End
Say 'original list=' list ... Say 'cycle length =' cLen /*display the cycle len */ Say 'start index =' p.x-1 " (zero based)" /* " " index. */ Say 'the sequence =' subword(list,p.x,cLen) /* " " sequence. */ Exit /*-------------------------------------------------------------------*/ f: Return (arg(1)**2+1)// 255; /*define the function F*/</lang>
Ruby
<lang Ruby>
- Author: Paul Anton Chernoch
- Purpose:
- Find the cycle length and start position of a numerical seried using Brent's cycle algorithm.
- Given a recurrence relation X[n+1] = f(X[n]) where f() has
- a finite range, you will eventually repeat a value that you have seen before.
- Once this happens, all subsequent values will form a cycle that begins
- with the first repeated value. The period of that cycle may be of any length.
- Parameters:
- x0 ...... First integer value in the sequence
- block ... Block that takes a single integer as input
- and returns a single integer as output.
- This yields a sequence of numbers that eventually repeats.
- Returns:
- Two values: lambda and mu
- lambda .. length of cycle
- mu ...... zero-based index of start of cycle
def findCycle(x0)
power = lambda = 1 tortoise = x0 hare = yield(x0) # Find lambda, the cycle length while tortoise != hare if power == lambda tortoise = hare power *= 2 lambda = 0 end hare = yield(hare) lambda += 1 end # Find mu, the zero-based index of the start of the cycle mu = 0 tortoise = hare = x0 lambda.times do hare = yield(hare) end while tortoise != hare tortoise = yield(tortoise) hare = yield(hare) mu += 1 end return lambda, mu
end
- A recurrence relation to use in testing
def f(x)
return (x * x + 1) % 255
end
- Display the first 41 numbers in the test series
x = 3 print "#{x}" 40.times do
x = f(x) print ",#{x}"
end print "\n"
- Test the findCycle function
clength, cstart = findCycle(3) { |x| f(x) }
print "Cycle length = #{clength}\nStart index = #{cstart}\n"
</lang>
zkl
Algorithm from the Wikipedia <lang zkl>fcn cycleDetection(f,x0){ // f(int), x0 is the integer starting value of the sequence
# main phase: search successive powers of two power:=lam:=1; tortoise,hare:=x0,f(x0); # f(x0) is the element/node next to x0. while(tortoise!=hare){ if(power==lam){ # time to start a new power of two?
tortoise,lam=hare,0; power*=2;
} hare=f(hare); lam+=1; } # Find the position of the first repetition of length λ mu:=0; tortoise=hare=x0; do(lam){ hare=f(hare) } # The distance between the hare and tortoise is now λ
# Next, the hare and tortoise move at same speed till they agree while(tortoise!=hare){ tortoise,hare=f(tortoise),f(hare); mu+=1; } return(lam,mu);
}</lang> <lang zkl>cycleDetection(fcn(x){ (x*x + 1)%255 }, 3).println(" == cycle length, start index");</lang>
- Output:
L(6,2) == cycle length, start index