Determine whether repeated deterministic updates revisit a state, and optionally find the preperiod and cycle length. Recording all visited states uses memory proportional to the visited orbit. Floyd's cycle-finding algorithm detects repetition with constant extra memory.
For a deterministic iteration with eventual cycle length and preperiod , the Brent cycle-finding algorithm detects repetition using constant auxiliary space.
Hold a checkpoint fixed while another pointer advances through blocks of lengths . At a block boundary, move the checkpoint to the advancing pointer and double the next block length. Compare each new state to the checkpoint. Once the checkpoint lies on the cycle and its block is long enough, the first equality occurs exactly steps after the checkpoint.
To locate the entrance, restart two pointers at the initial state, advance one by steps, then move both one step at a time until they agree. Before index , the first pointer is outside the cycle; at both reach the same cyclic position. The procedure uses evaluations of and constant auxiliary space, assuming constant-cost state equality and copying. An infinite nonperiodic orbit has no finite detection guarantee.[ref]
Articles by others on the same topic
Cycle detection refers to the process of identifying cycles (or loops) within a data structure, such as a graph or a linked list. A cycle is formed when a sequence of edges leads back to the starting vertex, creating a closed loop. Cycle detection is an important concept in computer science, particularly in graph theory, algorithm design, and data structure manipulation. Here are a few key concepts related to cycle detection: ### 1.