Cycle detection: Difference between revisions
Content added Content deleted
(Detect the length and starting index of a periodic cycle in a series of numbers) |
No edit summary |
||
| Line 1: | Line 1: | ||
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 efficient algorithm is Brent's Cycle 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. |
||
See https://en.wikipedia.org/wiki/Cycle_detection for a discussion of the theory. |
See https://en.wikipedia.org/wiki/Cycle_detection for a discussion of the theory. |
||
Revision as of 15:07, 25 February 2016
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.
See https://en.wikipedia.org/wiki/Cycle_detection for a discussion of the theory.