Cycle detection: Difference between revisions
No edit summary |
(Describe expected output) |
||
Line 1: | Line 1: | ||
{{task}} Detect a cycle in an iterated function using Brent's algorithm |
{{task}} 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. |
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. |
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 |
Revision as of 15:26, 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