Editing Cycle detection (section)

====Advantages====

The main features of Gosper's algorithm are that it is economical in space, very economical in evaluations of the generator function, and always finds the exact cycle length (never a multiple). The cost is a large number of equality comparisons.  It could be roughly described as a concurrent version of Brent's algorithm. While Brent's algorithm uses a single tortoise, repositioned every time the hare passes a power of two, Gosper's algorithm uses several tortoises (several previous values are saved), which are roughly exponentially spaced. According to the note in [[HAKMEM]] item 132,<ref name="hakmem-132" /> this algorithm will detect repetition before the third occurrence of any value, i.e. the cycle will be iterated at most twice. HAKMEM also states that it is sufficient to store <math>\lceil\log_2\lambda\rceil</math> previous values; however, this only offers a saving if we know ''a priori'' that <math>\lambda</math> is significantly smaller than <math>\mu</math>.  The standard implementations<ref name="gosper-impl"/> store <math>\lceil\log_2 (\mu + 2\lambda)\rceil</math> values. For example, assume the function values are 32-bit integers, so <math>\mu + \lambda \le 2^{32}</math> and <math>\mu + 2\lambda \le 2^{33}.</math>  Then Gosper's algorithm will find the cycle after less than <math>\mu + 2\lambda</math> function evaluations (in fact, the most possible is <math>3\cdot 2^{31} - 1</math>), while consuming the space of 33 values (each value being a 32-bit integer).