Editing Cycle detection (section)

===Gosper's algorithm===
[[Bill Gosper|R. W. Gosper]]'s algorithm<ref name="gosper-impl">{{Cite web |title=Loop detectors of Floyd and Gosper |url=http://www.hackersdelight.org/hdcodetxt/loopdet.c.txt |website=[[Hacker's Delight]] |first=Henry S. Jr. |last=Warren |archive-url=https://web.archive.org/web/20160414011322/http://hackersdelight.org/hdcodetxt/loopdet.c.txt |archive-date=2016-04-14 |access-date=2017-02-08}}</ref><ref name="hakmem-132">{{Cite web |title=Hakmem -- Flows and Iterated Functions -- Draft, Not Yet Proofed |url=http://www.inwap.com/pdp10/hbaker/hakmem/flows.html |archive-url=https://web.archive.org/web/20200318230848/http://www.inwap.com/pdp10/hbaker/hakmem/flows.html |archive-date=2020-03-18 |access-date=2024-05-02}}</ref> finds the period <math>\lambda</math>, and the lower and upper bound of the starting point, <math>\mu_l</math> and <math>\mu_u</math>, of the first cycle. The difference between the lower and upper bound is of the same order as the period, i.e. <math>\mu_l + \lambda \approx \mu_h</math>.

The algorithm maintains an array of tortoises <math>T_j</math>.  For each <math>x_i</math>:
* For each <math>0 \le j \le \log_2 i,</math> compare <math>x_i</math> to <math>T_j</math>.
* If <math>x_i = T_j</math>, a cycle has been detected, of length <math>\lambda = (i - 2^j) \bmod 2^{j+1} + 1.</math>
* If no match is found, set <math>T_k \leftarrow x_i</math>, where <math>k</math> is the [[Count trailing zeros|number of trailing zeros]] in the binary representation of <math>i+1</math>.  I.e. the greatest power of 2 which divides <math>i+1</math>.

If it is inconvenient to vary the number of comparisons as <math>i</math> increases, you may initialize all of the <math>T_j = x_0</math>, but must then return <math>\lambda = i</math> if <math>x_i = T_j</math> while <math>i < 2^j</math>.

====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).

====Complexity====

Upon the <math>i</math>-th evaluation of the generator function, the algorithm compares the generated value with <math>\log_2 i</math> previous values; observe that <math>i</math> goes up to at least <math>\mu + \lambda</math> and at most <math>\mu + 2\lambda</math>. Therefore, the time complexity of this algorithm is <math>O((\mu + \lambda) \cdot \log (\mu + \lambda))</math>. Since it stores <math>\log_2 (\mu + 2\lambda)</math> values, its space complexity is <math>\Theta(\log (\mu + \lambda))</math>. This is under the usual [[transdichotomous model]], assumed throughout this article, in which the size of the function values is constant. Without this assumption, we know it requires <math>\Omega(\log (\mu + \lambda))</math> space to store <math>\mu + \lambda</math> distinct values, so the overall space complexity is <math>\Omega(\log^2 (\mu + \lambda)).</math>