Cycle detection: Difference between revisions
No edit summary |
(Add Ruby solution) |
||
Line 27: | Line 27: | ||
101,2,5,26,167 |
101,2,5,26,167 |
||
=={{header|Ruby}}== |
|||
{{works with|ruby|2.0}} |
|||
<lang Ruby> |
|||
# 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> |
Revision as of 15:39, 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
Ruby
<lang Ruby>
- 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>