Nickname for "Floyd's Cycle-Finding Algorithm" invented by Robert W. Floyd in 1967; see my update to the wikipedia entry http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm. A simple technique for detecting infinite loops inside lists, symlinks, state machines, etc. For example, to detect a loop inside a linked list: * make a pointer to the start of the list and call it the hare * make a pointer to the start of the list and call it the tortoise * advance the hare by two and the tortoise by one for every iteration * there's a loop if the tortoise and the hare meet * there's no loop if the hare reaches the end This algorithm is particularly interesting because it is O(n) time and O(1) space, which appears to be optimal; more obvious algorithms are O(n) space. ---- There is an alternative version in which the hare races ahead for '''2^n''' steps, then the tortoise teleports to him and '''n''' is increased by 1. More efficient (lower multiplicative constant) and only slightly more complex to code. '''Algorithm A, the original:''' tortoise = head rabbit = head length = 0 if rabbit == null: return length rabbit, length = step(rabbit), length+1 if rabbit == null: return length while rabbit != tortoise: rabbit, length = step(rabbit), length+1 if rabbit==null: return length rabbit, length = step(rabbit), length+1 if rabbit==null: return length tortoise = step(tortoise) return infinity '''Algorithm B, the leaping version:''' tortoise = head rabbit = head length,gap = 0, 0 if rabbit == null: return "Finite list of length "+string(length) rabbit, length, gap = step(rabbit), length+1, gap+1 if rabbit == null: return "Finite list of length "+string(length) limit = 1 while rabbit != tortoise: if gap==limit: tortoise, gap, limit = rabbit, 0, limit*2 rabbit, length, gap = step(rabbit), length+1, gap+1 if rabbit==null: return "Finite list of length "+string(length) return "List with loop of size "+string(gap) In each, '''length''' is how long the list is so far as traversed by '''rabbit'''. In the first, if '''rabbit''' takes '''2n''' steps, '''tortoise''' takes '''n''' steps. In the second '''tortoise''' never takes any steps. In linked lists stepping to the next node isn't expensive, but this loop finding algorithm can be used in places where the list is implicit (such as the Pollard Rho and Elliptic Curve methods of factoring integers) and stepping is expensive. Algorithm B then wins by a substantial margin. Here's the complete analysis: Suppose there is no loop and the list is of length '''2n'''. Then algorithm A takes '''3n''' steps, and algorithm B takes '''2n''' steps. Now suppose there is a loop, and let '''t''' be the number of steps taken to reach the loop and let '''p''' be the size of the loop. Algorithm A: * If '''t<=p''' then '''steps_A = 3p''' * If '''t>=p''' then let '''d''' be such that '''d+t=k*p'''. Note that '''0<=d
=p''' then let '''Q=2^m''' such that '''Q <= t < 2Q''', and let '''f=2Q-t''', so that '''f