Cycle Detection Algorithm

In computer science, cycle detection is the algorithmic problem of finding a cycle in a sequence of iterated function values: given a function that maps a finite set to itself and a starting value, the sequence produced by repeatedly applying the function must eventually repeat a value, and cycle detection finds where. Robert Floyd's tortoise and hare algorithm moves two pointers through the sequence at different speeds until they point to equal values, while Brent's algorithm is an alternative based on exponential search, and both use only a constant amount of memory. Applications include testing the quality of pseudorandom number generators and cryptographic hash functions, detecting infinite loops in computer programs, and detecting deadlocks in database transaction management.