Cycle detection

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

Ruby

Works with: ruby version 2.0

<lang Ruby>

1. Find the cycle length and start position of a numerical seried using Brent's cycle algorithm.
3. Given a recurrence relation X[n+1] = f(X[n]) where f() has
4. a finite range, you will eventually repeat a value that you have seen before.
5. Once this happens, all subsequent values will form a cycle that begins
6. 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>