Editing Cycle detection (section)

{{Short description|Algorithmic problem}}
{{about|iterated functions|another use|Cycle detection (graph theory)}}
{{Technical|date=February 2018}}

In [[computer science]], '''cycle detection''' or '''cycle finding''' is the [[algorithm]]ic problem of finding a cycle in a [[sequence]] of [[iterated function]] values.

For any [[function (mathematics)|function]] {{mvar|f}} that maps a [[finite set]] {{mvar|S}} to itself, and any initial value {{math|''x''<sub>0</sub>}} in {{mvar|S}}, the sequence of iterated function values

:<math> x_0,\ x_1=f(x_0),\ x_2=f(x_1),\ \dots,\ x_i=f(x_{i-1}),\ \dots</math>

must eventually use the same value twice: there must be some pair of distinct indices {{mvar|i}} and {{mvar|j}} such that {{math|1=''x<sub>i</sub>'' = ''x<sub>j</sub>''}}. Once this happens, the sequence must continue [[periodic sequence|periodically]], by repeating the same sequence of values from {{math|''x<sub>i</sub>''}} to {{math|''x''<sub>''j'' &minus; 1</sub>}}. Cycle detection is the problem of finding {{mvar|i}} and {{mvar|j}}, given {{mvar|f}} and {{math|''x''<sub>0</sub>}}.

Several algorithms are known for finding cycles quickly and with little memory. [[Robert W. Floyd]]'s [[#Floyd's_tortoise_and_hare|tortoise and hare algorithm]] moves two pointers at different speeds through the sequence of values until they both point to equal values. Alternatively, Brent's algorithm is based on the idea of [[exponential search]]. Both Floyd's and Brent's algorithms use only a constant number of memory cells, and take a number of function evaluations that is proportional to the distance from the start of the sequence to the first repetition. Several other algorithms trade off larger amounts of memory for fewer function evaluations.

The applications of cycle detection include testing the quality of [[pseudorandom number generator]]s and [[cryptographic hash function]]s, [[computational number theory]] algorithms, detection of [[infinite loop]]s in computer programs and periodic configurations in [[cellular automaton|cellular automata]],  automated [[Shape analysis (software)|shape analysis]] of [[linked list]] data structures, and detection of [[Deadlock (computer science)|deadlocks]] for [[Transaction manager|transactions management]] in [[Database|DBMS]].