Cycle detection: Difference between revisions

From Rosetta Code
Content added Content deleted
Line 40: Line 40:
namespace DetectCycles
namespace DetectCycles
{
{
/// <summary>
/// <summary>
/// Find the length and start of a cycle in a series of objects of any IEquatable type using Brent's cycle algorithm.
/// Find the length and start of a cycle in a series of objects of any IEquatable type using Brent's cycle algorithm.
/// </summary>
/// </summary>
public class Cycles<T> where T : IEquatable<T>
public class Cycles<T> where T : IEquatable<T>
{
{
/// <summary>
/// <summary>
/// Find the cycle length and start position of a series using Brent's cycle algorithm.
/// 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
/// 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.
/// 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
/// 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.
/// with the first repeated value. The period of that cycle may be of any length.
/// </summary>
/// </summary>
/// <returns>A tuple where:
/// <returns>A tuple where:
/// Item1 is lambda (the length of the cycle)
/// Item1 is lambda (the length of the cycle)
/// Item2 is mu, the zero-based index of the item that started the first cycle.</returns>
/// 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="x0">First item in the series.</param>
/// <param name="yielder">Function delegate that generates the series by iterated execution.</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)
public static Tuple<int,int> FindCycle(T x0, Func<T,T> yielder)
{
{
int power, lambda;
int power, lambda;
T tortoise, hare;
T tortoise, hare;
power = lambda = 1;
power = lambda = 1;
tortoise = x0;
tortoise = x0;
hare = yielder(x0);
hare = yielder(x0);


// Find lambda, the cycle length
// Find lambda, the cycle length
while (!tortoise.Equals (hare)) {
while (!tortoise.Equals (hare)) {
if (power == lambda) {
if (power == lambda) {
tortoise = hare;
tortoise = hare;
power *= 2;
power *= 2;
lambda = 0;
lambda = 0;
}
}
hare = yielder (hare);
hare = yielder (hare);
lambda += 1;
lambda += 1;
}
}


// Find mu, the zero-based index of the start of the cycle
// Find mu, the zero-based index of the start of the cycle
var mu = 0;
var mu = 0;
tortoise = hare = x0;
tortoise = hare = x0;
for (var times = 0; times < lambda; times++)
for (var times = 0; times < lambda; times++)
hare = yielder (hare);
hare = yielder (hare);
while (!tortoise.Equals (hare))
while (!tortoise.Equals (hare))
{
{
tortoise = yielder (tortoise);
tortoise = yielder (tortoise);
hare = yielder (hare);
hare = yielder (hare);
mu += 1;
mu += 1;
}
}


return new Tuple<int,int> (lambda, mu);
return new Tuple<int,int> (lambda, mu);
}
}
}
}
}
}



Revision as of 17:00, 25 February 2016

Task
Cycle detection
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

Works with: ruby version 2.0

<lang Ruby>

  1. Author: Paul Anton Chernoch
  2. Purpose:
  3. Find the cycle length and start position of a numerical seried using Brent's cycle algorithm.
  4. Given a recurrence relation X[n+1] = f(X[n]) where f() has
  5. a finite range, you will eventually repeat a value that you have seen before.
  6. Once this happens, all subsequent values will form a cycle that begins
  7. with the first repeated value. The period of that cycle may be of any length.
  8. Parameters:
  9. x0 ...... First integer value in the sequence
  10. block ... Block that takes a single integer as input
  11. and returns a single integer as output.
  12. This yields a sequence of numbers that eventually repeats.
  13. Returns:
  14. Two values: lambda and mu
  15. lambda .. length of cycle
  16. 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

  1. A recurrence relation to use in testing

def f(x)

 return (x * x + 1) % 255

end

  1. Display the first 41 numbers in the test series

x = 3 print "#{x}" 40.times do

 x = f(x)
 print ",#{x}"

end print "\n"

  1. Test the findCycle function

clength, cstart = findCycle(3) { |x| f(x) }

print "Cycle length = #{clength}\nStart index = #{cstart}\n"

</lang>