Cycle detection: Difference between revisions
Line 40: | Line 40: | ||
namespace DetectCycles |
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); |
|||
} |
|||
} |
|||
} |
|||
} |
} |
||
Revision as of 17:00, 25 February 2016
You are encouraged to solve this task according to the task description, using any language you may know.
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
C#
This solution uses generics, so may find cycles of any type of data, not just integers.
<lang C#>
// First file: Cycles.cs
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>
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>