Editing Cycle detection (section)

===Time–space tradeoffs===
A number of authors have studied techniques for cycle detection that use more memory than Floyd's and Brent's methods, but detect cycles more quickly. In general these methods store several previously-computed sequence values, and test whether each new value equals one of the previously-computed values. In order to do so quickly, they typically use a [[hash table]] or similar data structure for storing the previously-computed values, and therefore are not pointer algorithms: in particular, they usually cannot be applied to Pollard's rho algorithm. Where these methods differ is in how they determine which values to store. Following Nivasch,<ref name="nivasch">{{citation|first=Gabriel|last=Nivasch|title=Cycle detection using a stack|journal=[[Information Processing Letters]]|volume=90|year=2004|pages=135–140|doi=10.1016/j.ipl.2004.01.016|issue=3}}.</ref> we survey these techniques briefly.

*Brent<ref name="brent"/> already describes variations of his technique in which the indices of saved sequence values are powers of a number {{mvar|R}} other than two. By choosing {{mvar|R}} to be a number close to one, and storing the sequence values at indices that are near a sequence of consecutive powers of {{mvar|R}}, a cycle detection algorithm can use a number of function evaluations that is within an arbitrarily small factor of the optimum {{math|''λ'' + ''μ''}}.<ref>{{citation|first1=Claus P.|last1=Schnorr|author-link1=Claus P. Schnorr|first2=Hendrik W.|last2=Lenstra|author-link2=Hendrik Lenstra|title=A Monte Carlo factoring algorithm with linear storage|journal=[[Mathematics of Computation]]|volume=43|issue=167|year=1984|pages=289–311|doi=10.2307/2007414|jstor=2007414|hdl=1887/3815|hdl-access=free}}.</ref><ref name="teske">{{citation|first=Edlyn|last=Teske|title=A space-efficient algorithm for group structure computation|journal=[[Mathematics of Computation]]|volume=67|issue=224|year=1998|pages=1637–1663|doi=10.1090/S0025-5718-98-00968-5|bibcode=1998MaCom..67.1637T|doi-access=free}}.</ref>
*Sedgewick, Szymanski, and Yao<ref>{{citation|first1=Robert|last1=Sedgewick|author-link1=Robert Sedgewick (computer scientist)|first2=Thomas G.|last2=Szymanski|first3=Andrew C.-C.|last3=Yao|author-link3=Andrew Yao|title=The complexity of finding cycles in periodic functions|journal=[[SIAM Journal on Computing]]|volume=11|issue=2|year=1982|pages=376–390|doi=10.1137/0211030}}.</ref>  provide a method that uses {{mvar|M}} memory cells and requires in the worst case only <math>(\lambda+\mu)(1+cM^{-1/2})</math> function evaluations, for some constant {{mvar|c}}, which they show to be optimal. The technique involves maintaining a numerical parameter {{mvar|d}}, storing in a table only those positions in the sequence that are multiples of {{mvar|d}}, and clearing the table and doubling {{mvar|d}} whenever too many values have been stored.
*Several authors have described ''distinguished point'' methods that store function values in a table based on a criterion involving the values, rather than (as in the method of Sedgewick et al.) based on their positions. For instance, values equal to zero modulo some value {{mvar|d}} might be stored.<ref>{{citation|first1=Paul C.|last1=van Oorschot|first2=Michael J.|last2=Wiener|title=Parallel collision search with cryptanalytic applications|journal=[[Journal of Cryptology]]|volume=12|issue=1|year=1999|pages=1–28|doi=10.1007/PL00003816|s2cid=5091635|url=https://ir.library.carleton.ca/pub/19076|doi-access=free}}.</ref><ref name="qd">{{citation|first1=J.-J.|last1=Quisquater|first2=J.-P.|last2=Delescaille|contribution=How easy is collision search? Application to DES|title=Advances in Cryptology – EUROCRYPT '89, Workshop on the Theory and Application of Cryptographic Techniques|series=Lecture Notes in Computer Science|date=1990 |volume=434|publisher=Springer-Verlag|pages=429–434|doi=10.1007/3-540-46885-4_43|doi-access=free|isbn=978-3-540-53433-4 }}.</ref> More simply, Nivasch<ref name="nivasch"/> credits D. P. Woodruff with the suggestion of storing a random sample of previously seen values, making an appropriate random choice at each step so that the sample remains random.
*Nivasch<ref name="nivasch"/> describes an algorithm that does not use a fixed amount of memory, but for which the expected amount of memory used (under the assumption that the input function is random) is logarithmic in the sequence length. An item is stored in the memory table, with this technique, when no later item has a smaller value. As Nivasch shows, the items with this technique can be maintained using a [[Stack (data structure)|stack data structure]], and each successive sequence value need be compared only to the top of the stack. The algorithm terminates when the repeated sequence element with smallest value is found. Running the same algorithm with multiple stacks, using random permutations of the values to reorder the values within each stack, allows a time–space tradeoff similar to the previous algorithms. However, even the version of this algorithm with a single stack is not a pointer algorithm, due to the comparisons needed to determine which of two values is smaller.

Any cycle detection algorithm that stores at most {{mvar|M}} values from the input sequence must perform at least <math>(\lambda+\mu)\left(1+\frac{1}{M-1}\right)</math> function evaluations.<ref name="fich">{{citation|first=Faith Ellen|last=Fich|author-link=Faith Ellen|contribution=Lower bounds for the cycle detection problem|title=Proc. 13th ACM [[Symposium on Theory of Computing]]|series=Stoc '81 |year=1981|doi=10.1145/800076.802462|pages=96–105|isbn=978-1-4503-7392-0 |s2cid=119742106 }}.</ref><ref>{{citation|first1=Eric W.|last1=Allender|author-link1=Eric Allender|first2=Maria M.|last2=Klawe|author-link2=Maria Klawe|title=Improved lower bounds for the cycle detection problem|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=36|issue=2–3|pages=231–237|year=1985|doi=10.1016/0304-3975(85)90044-1|doi-access=free}}.</ref>