1,564
个编辑
更改
跳到导航
跳到搜索
Moved page from wikipedia:en:Cycle detection (history)
此词条暂由彩云小译翻译，翻译字数共3415，未经人工整理和审校，带来阅读不便，请见谅。
{{about|iterated functions|another use|Cycle detection (graph theory)}}
{{Technical|date=February 2018}}
In [[computer science]], '''cycle detection''' or '''cycle finding''' is the [[algorithm]]ic problem of finding a cycle in a [[sequence]] of [[iterated function]] values.
In computer science, cycle detection or cycle finding is the algorithmic problem of finding a cycle in a sequence of iterated function values.
在计算机科学中，循环检测或循环寻找是在一系列计算问题值中寻找循环的迭代函数。
For any [[function (mathematics)|function]] {{mvar|f}} that maps a [[finite set]] {{mvar|S}} to itself, and any initial value {{math|''x''<sub>0</sub>}} in {{mvar|S}}, the sequence of iterated function values
For any function that maps a finite set to itself, and any initial value in , the sequence of iterated function values
对于任何将有限集映射到自身的函数，以及其中的任何初始值，迭代函数的序列
:<math> x_0,\ x_1=f(x_0),\ x_2=f(x_1),\ \dots,\ x_i=f(x_{i-1}),\ \dots</math>
: x_0,\ x_1=f(x_0),\ x_2=f(x_1),\ \dots,\ x_i=f(x_{i-1}),\ \dots
: x _ 0，x _ 1 = f (x _ 0) ，x _ 2 = f (x _ 1) ，点，x _ i = f (x _ { i-1}) ，点
must eventually use the same value twice: there must be some pair of distinct indices {{mvar|i}} and {{mvar|j}} such that {{math|1=''x<sub>i</sub>'' = ''x<sub>j</sub>''}}. Once this happens, the sequence must continue [[periodic sequence|periodically]], by repeating the same sequence of values from {{math|''x<sub>i</sub>''}} to {{math|''x''<sub>''j'' − 1</sub>}}. Cycle detection is the problem of finding {{mvar|i}} and {{mvar|j}}, given {{mvar|f}} and {{math|''x''<sub>0</sub>}}.
must eventually use the same value twice: there must be some pair of distinct indices and such that . Once this happens, the sequence must continue periodically, by repeating the same sequence of values from to . Cycle detection is the problem of finding and , given and .
最终必须使用相同的值两次: 必须有一对不同的索引，这样。一旦发生这种情况，序列必须通过重复相同的值序列来周期性地继续。循环检测是查找和给定的问题。
Several algorithms for finding cycles quickly and with little memory are known. [[Robert W. Floyd]]'s [[Cycle detection#Floyd's_tortoise_and_hare|tortoise and hare algorithm]] moves two pointers at different speeds through the sequence of values until they both point to equal values. Alternatively, Brent's algorithm is based on the idea of [[exponential search]]. Both Floyd's and Brent's algorithms use only a constant number of memory cells, and take a number of function evaluations that is proportional to the distance from the start of the sequence to the first repetition. Several other algorithms trade off larger amounts of memory for fewer function evaluations.
Several algorithms for finding cycles quickly and with little memory are known. Robert W. Floyd's tortoise and hare algorithm moves two pointers at different speeds through the sequence of values until they both point to equal values. Alternatively, Brent's algorithm is based on the idea of exponential search. Both Floyd's and Brent's algorithms use only a constant number of memory cells, and take a number of function evaluations that is proportional to the distance from the start of the sequence to the first repetition. Several other algorithms trade off larger amounts of memory for fewer function evaluations.
已经知道几种快速查找循环和内存不足的算法。罗伯特 · 弗洛伊德的乌龟和兔子算法以不同的速度移动两个指针通过值的序列，直到它们都指向相等的值。另外，布伦特的算法是基于指数搜索的思想。弗洛伊德和布伦特的算法都只使用固定数量的存储单元，并采取一些功能评估是成正比的距离，从序列的开始到第一次重复。其他一些算法用较少的函数计算来交换较大的内存。
The applications of cycle detection include testing the quality of [[pseudorandom number generator]]s and [[cryptographic hash function]]s, [[computational number theory]] algorithms, detection of [[infinite loop]]s in computer programs and periodic configurations in [[cellular automaton|cellular automata]], automated [[Shape analysis (software)|shape analysis]] of [[linked list]] data structures, and detection of [[Deadlock|deadlocks]] for [[Transaction manager|transactions management]] in [[Database|DBMS]].
The applications of cycle detection include testing the quality of pseudorandom number generators and cryptographic hash functions, computational number theory algorithms, detection of infinite loops in computer programs and periodic configurations in cellular automata, automated shape analysis of linked list data structures, and detection of deadlocks for transactions management in DBMS.
循环检测的应用包括测试伪随机数生成器和加密哈希函数的质量、计算数论算法、检测电脑程序中的无限循环和细胞自动机中的周期性配置、对链表数据结构进行自动形状分析，以及在数据库管理系统中检测事务管理中的死锁。
==Example==
[[File:Functional graph.svg|thumb|upright=1.5|A function from and to the set {0,1,2,3,4,5,6,7,8} and the corresponding [[functional graph]]]]
The figure shows a function {{mvar|f}} that maps the set {{math|1=''S'' = {0,1,2,3,4,5,6,7,8} }} to itself. If one starts from {{math|1=''x''<sub>0</sub> = 2}} and repeatedly applies {{mvar|f}}, one sees the sequence of values
:{{math|2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ....}}
The cycle in this value sequence is {{math|6, 3, 1}}.
The figure shows a function that maps the set to itself. If one starts from and repeatedly applies , one sees the sequence of values
:
The cycle in this value sequence is .
图中显示了一个将集合映射到自身的函数。如果开始并重复应用，就会看到值序列: 这个值序列中的循环是。
==Definitions==
==Definitions==
= = 定义 = =
Let {{mvar|S}} be any finite set, {{mvar|f}} be any function from {{mvar|S}} to itself, and {{math|''x''<sub>0</sub>}} be any element of {{mvar|S}}. For any {{math|''i'' > 0}}, let {{math|1=''x<sub>i</sub>'' = ''f''(''x''<sub>''i'' − 1</sub>)}}. Let {{mvar|μ}} be the smallest index such that the value {{math|''x''<sub>''μ''</sub>}} reappears infinitely often within the sequence of values {{math|''x<sub>i</sub>''}}, and let {{mvar|λ}} (the loop length) be the smallest positive integer such that {{math|1=''x''<sub>''μ''</sub> = ''x''<sub>''λ'' + ''μ''</sub>}}. The cycle detection problem is the task of finding {{mvar|λ}} and {{mvar|μ}}.<ref>{{citation|title=Algorithmic Cryptanalysis|first=Antoine|last=Joux|publisher=CRC Press|year=2009|isbn=9781420070033|page=223|url=https://books.google.com/books?id=buQajqt-_iUC&pg=PA223}}.</ref>
Let be any finite set, be any function from to itself, and be any element of . For any , let . Let be the smallest index such that the value reappears infinitely often within the sequence of values , and let (the loop length) be the smallest positive integer such that . The cycle detection problem is the task of finding and ..
设为任意有限集，任意函数自身，任意元素。对于任何人，让。设为最小的索引，使得该值在值序列中无限频繁地重现，并且设(循环长度)为最小的正整数，使得。循环检测问题的任务是发现和. 。
One can view the same problem [[graph theory|graph-theoretically]], by constructing a [[functional graph]] (that is, a [[directed graph]] in which each vertex has a single outgoing edge) the vertices of which are the elements of {{mvar|S}} and the edges of which map an element to the corresponding function value, as shown in the figure. The set of vertices [[Reachability|reachable]] from starting vertex {{math|''x''<sub>0</sub>}} form a subgraph with a shape resembling the [[Rho (letter)|Greek letter rho]] ({{mvar|ρ}}): a path of length {{mvar|μ}} from {{math|''x''<sub>0</sub>}} to a [[Cycle (graph theory)|cycle]] of {{mvar|λ}} vertices.<ref name="j224">{{harvtxt|Joux|2009|page=224}}.</ref>
One can view the same problem graph-theoretically, by constructing a functional graph (that is, a directed graph in which each vertex has a single outgoing edge) the vertices of which are the elements of and the edges of which map an element to the corresponding function value, as shown in the figure. The set of vertices reachable from starting vertex form a subgraph with a shape resembling the Greek letter rho (): a path of length from to a cycle of vertices..
人们可以查看相同的问题图——从理论上讲，通过构造一个函数图(也就是说，一个有向图，其中每个顶点有一个单一的出口边) ，其中的顶点是元素，其中的边将一个元素映射到相应的函数值，如图所示。从起始点到达的一组顶点形成一个子图，其形状类似于希腊字母 rho () : 从一个顶点循环到一个顶点循环的长度路径。.
==Computer representation==
Generally, {{mvar|f}} will not be specified as a table of values, the way it is shown in the figure above. Rather, a cycle detection algorithm may be given access either to the sequence of values {{math|''x<sub>i</sub>''}}, or to a subroutine for calculating {{mvar|f}}. The task is to find {{mvar|λ}} and {{mvar|μ}} while examining as few values from the sequence or performing as few subroutine calls as possible. Typically, also, the [[space complexity]] of an algorithm for the cycle detection problem is of importance: we wish to solve the problem while using an amount of memory significantly smaller than it would take to store the entire sequence.
Generally, will not be specified as a table of values, the way it is shown in the figure above. Rather, a cycle detection algorithm may be given access either to the sequence of values , or to a subroutine for calculating . The task is to find and while examining as few values from the sequence or performing as few subroutine calls as possible. Typically, also, the space complexity of an algorithm for the cycle detection problem is of importance: we wish to solve the problem while using an amount of memory significantly smaller than it would take to store the entire sequence.
= = 计算机表示 = = 通常不会被指定为值表，如上图所示。相反，循环检测算法可以访问值的序列，或者访问用于计算的子程序。任务是从序列中查找并检查尽可能少的值或执行尽可能少的子例程调用。通常，循环检测问题的算法的空间复杂度也很重要: 我们希望解决这个问题，同时使用比存储整个序列所需要的内存量小得多的内存。
In some applications, and in particular in [[Pollard's rho algorithm]] for [[integer factorization]], the algorithm has much more limited access to {{mvar|S}} and to {{mvar|f}}. In Pollard's rho algorithm, for instance, {{mvar|S}} is the set of integers modulo an unknown prime factor of the number to be factorized, so even the size of {{mvar|S}} is unknown to the algorithm.
To allow cycle detection algorithms to be used with such limited knowledge, they may be designed based on the following capabilities. Initially, the algorithm is assumed to have in its memory an object representing a [[Pointer (computer programming)|pointer]] to the starting value {{math|''x''<sub>0</sub>}}. At any step, it may perform one of three actions: it may copy any pointer it has to another object in memory, it may apply {{mvar|f}} and replace any of its pointers by a pointer to the next object in the sequence, or it may apply a subroutine for determining whether two of its pointers represent equal values in the sequence. The equality test action may involve some nontrivial computation: for instance, in Pollard's rho algorithm, it is implemented by testing whether the difference between two stored values has a nontrivial [[greatest common divisor]] with the number to be factored.<ref name="j224"/> In this context, by analogy to the [[pointer machine]] model of computation, an algorithm that only uses pointer copying, advancement within the sequence, and equality tests may be called a pointer algorithm.
In some applications, and in particular in Pollard's rho algorithm for integer factorization, the algorithm has much more limited access to and to . In Pollard's rho algorithm, for instance, is the set of integers modulo an unknown prime factor of the number to be factorized, so even the size of is unknown to the algorithm.
To allow cycle detection algorithms to be used with such limited knowledge, they may be designed based on the following capabilities. Initially, the algorithm is assumed to have in its memory an object representing a pointer to the starting value . At any step, it may perform one of three actions: it may copy any pointer it has to another object in memory, it may apply and replace any of its pointers by a pointer to the next object in the sequence, or it may apply a subroutine for determining whether two of its pointers represent equal values in the sequence. The equality test action may involve some nontrivial computation: for instance, in Pollard's rho algorithm, it is implemented by testing whether the difference between two stored values has a nontrivial greatest common divisor with the number to be factored. In this context, by analogy to the pointer machine model of computation, an algorithm that only uses pointer copying, advancement within the sequence, and equality tests may be called a pointer algorithm.
在一些应用程序中，特别是在 Pollard 的 rho 整数分解算法中，该算法的访问和访问受到更多的限制。例如，在 Pollard 的 rho 算法中，整数模的集合是一个未知素因子的数，所以即使是素因子的大小对算法来说也是未知的。为了使循环检测算法能够在如此有限的知识条件下使用，它们可以基于以下功能进行设计。最初，假定算法的内存中有一个表示指向起始值的指针的对象。在任何步骤中，它可以执行三个操作之一: 它可以复制任何指向内存中另一个对象的指针，它可以应用并用指向序列中下一个对象的指针替换它的任何指针，或者它可以应用一个子例程来确定它的两个指针在序列中是否表示相等的值。相等性测试操作可能涉及一些非平凡的计算，例如，在 Pollard 的 rho 算法中，它是通过测试两个存储值之间的差异是否与要分解的数值有一个非平凡的最大公约数来实现的。在这种情况下，类似于指针机器的计算模型，一种只使用指针复制、序列内进步和相等性测试的算法可以称为指针算法。
==Algorithms==
==Algorithms==
= = 算法 = =
If the input is given as a subroutine for calculating {{mvar|f}}, the cycle detection problem may be trivially solved using only {{math|''λ'' + ''μ''}} function applications, simply by computing the sequence of values {{math|''x<sub>i</sub>''}} and using a [[data structure]] such as a [[hash table]] to store these values and test whether each subsequent value has already been stored. However, the space complexity of this algorithm is proportional to {{math|''λ'' + ''μ''}}, unnecessarily large. Additionally, to implement this method as a [[pointer algorithm]] would require applying the equality test to each pair of values, resulting in quadratic time overall. Thus, research in this area has concentrated on two goals: using less space than this naive algorithm, and finding pointer algorithms that use fewer equality tests.
If the input is given as a subroutine for calculating , the cycle detection problem may be trivially solved using only function applications, simply by computing the sequence of values and using a data structure such as a hash table to store these values and test whether each subsequent value has already been stored. However, the space complexity of this algorithm is proportional to , unnecessarily large. Additionally, to implement this method as a pointer algorithm would require applying the equality test to each pair of values, resulting in quadratic time overall. Thus, research in this area has concentrated on two goals: using less space than this naive algorithm, and finding pointer algorithms that use fewer equality tests.
如果输入是作为计算子程序提供的，循环检测问题可以通过仅使用函数应用程序简单地解决，只需计算值的序列，并使用哈希表等数据结构来存储这些值，并测试是否已经存储了每个后续值。然而，该算法的空间复杂度是成比例的，不必要地大。此外，要将这种方法作为指针算法来实现，需要对每对值进行相等性测试，从而导致总体时间为二次型。因此，该领域的研究集中在两个目标上: 使用比这种幼稚算法更少的空间，以及寻找使用更少相等性测试的指针算法。
{{Anchor|Tortoise and hare}}
===Floyd's tortoise and hare===
[[File:Tortoise and hare algorithm.svg|thumb|upright=1.25|Floyd's "tortoise and hare" cycle detection algorithm, applied to the sequence 2, 0, 6, 3, 1, 6, 3, 1, ...]]
'''Floyd's cycle-finding algorithm''' is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. It is also called the "tortoise and the hare algorithm", alluding to Aesop's fable of [[The Tortoise and the Hare]].
thumb|upright=1.25|Floyd's "tortoise and hare" cycle detection algorithm, applied to the sequence 2, 0, 6, 3, 1, 6, 3, 1, ...
Floyd's cycle-finding algorithm is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. It is also called the "tortoise and the hare algorithm", alluding to Aesop's fable of The Tortoise and the Hare.
= = = 弗洛伊德的乌龟和兔子 = = = 拇指 | 直立 = 1.25 | 弗洛伊德的“乌龟和兔子”循环检测算法，应用于序列2,0,6,3,1,6,3,1，... 弗洛伊德的循环检测算法是一个指针算法，只使用两个指针，它们以不同的速度在序列中移动。它也被称为“乌龟和兔子算法”，暗指伊索寓言中的龟兔赛跑。
The algorithm is named after [[Robert W. Floyd]], who was credited with its invention by [[Donald Knuth]].<ref name="knuth">{{citation|first=Donald E.|last=Knuth|authorlink=Donald Knuth|title=The Art of Computer Programming, vol. II: Seminumerical Algorithms|publisher=Addison-Wesley|year=1969|page=7, exercises 6 and 7}}</ref><ref>''Handbook of Applied Cryptography,'' by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, [https://books.google.com/books?id=nSzoG72E93MC&pg=PA125 p. 125], describes this algorithm and others</ref> However, the algorithm does not appear in Floyd's published work, and this may be a misattribution: Floyd describes algorithms for listing all simple cycles in a [[directed graph]] in a 1967 paper,<ref>{{citation|last=Floyd|first=R.W.|authorlink=Robert W. Floyd|title=Nondeterministic Algorithms|journal=J. ACM|pages=636–644|volume=14|issue=4|year=1967|doi=10.1145/321420.321422|s2cid=1990464}}</ref> but this paper does not describe the cycle-finding problem in functional graphs that is the subject of this article. In fact, Knuth's statement (in 1969), attributing it to Floyd, without citation, is the first known appearance in print, and it thus may be a [[Mathematical folklore|folk theorem]], not attributable to a single individual.<ref>''The Hash Function BLAKE,'' by Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), [https://books.google.com/books?id=nhPmBQAAQBAJ&pg=PA21 p. 21], footnote 8</ref>
The algorithm is named after Robert W. Floyd, who was credited with its invention by Donald Knuth.Handbook of Applied Cryptography, by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, p. 125, describes this algorithm and others However, the algorithm does not appear in Floyd's published work, and this may be a misattribution: Floyd describes algorithms for listing all simple cycles in a directed graph in a 1967 paper, but this paper does not describe the cycle-finding problem in functional graphs that is the subject of this article. In fact, Knuth's statement (in 1969), attributing it to Floyd, without citation, is the first known appearance in print, and it thus may be a folk theorem, not attributable to a single individual.The Hash Function BLAKE, by Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), p. 21, footnote 8
该算法以罗伯特 · W · 弗洛伊德的名字命名，他被认为是唐纳德 · 克努斯发明的。应用密码学手册，作者: Alfred J。 Meneze，Paul C。 van Oorschot，Scott A。 Vanstone，p. 125，描述了这个算法和其他一些算法。然而，这个算法并没有出现在 Floyd 的出版物中，这可能是一个错误的归属: Floyd 在1967年的一篇论文中描述了在有向图中列出所有简单循环的算法，但是这篇论文并没有描述本文主题的函数图中的循环寻找问题。事实上，Knuth (在1969年)的声明，把它归因于弗洛伊德，没有引用，是第一个已知的出现在印刷品，因此它可能是一个民间定理，不归因于一个单一的个人。哈希函数 BLAKE，Jean-Philippe Aumasson，Willi Meier，Raphael C-W。Phan，Luca Henzen (2015) ，p. 21，脚注8
The key insight in the algorithm is as follows. If there is a cycle, then, for any integers {{math|''i'' ≥ ''μ''}} and {{math|''k'' ≥ 0}}, {{math|1=''x<sub>i</sub>'' = ''x''<sub>''i'' + ''kλ''</sub>}}, where {{mvar|λ}} is the length of the loop to be found, {{mvar|μ}} is the index of the first element of the cycle, and {{mvar|k}} is a whole integer representing the number of loops. Based on this, it can then be shown that {{math|1=''i'' = ''kλ'' ≥ ''μ''}} for some {{math|''k''}} if and only if {{math|1=''x<sub>i</sub>'' = ''x''<sub>2''i''</sub>}} (if {{math|1=''x<sub>i</sub>'' = ''x''<sub>2''i''</sub>}} in the cycle, then there exists some {{mvar|k}} such that {{math|1=2''i'' = ''i'' + ''kλ''}}, which implies that {{math|1=''i'' = ''kλ''}}; and if there are some {{mvar|i}} and {{mvar|k}} such that {{math|1=''i'' = ''kλ''}}, then {{math|1=''2i'' = ''i'' + ''kλ''}} and {{math|1= ''x''<sub>2''i''</sub> = ''x''<sub>''i'' + ''kλ''</sub>}}). Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period {{mvar|ν}} of a repetition that is a multiple of {{mvar|λ}}. Once {{mvar|ν}} is found, the algorithm retraces the sequence from its start to find the first repeated value {{math|''x''<sub>''μ''</sub>}} in the sequence, using the fact that {{mvar|λ}} divides {{mvar|ν}} and therefore that {{math|1=''x''<sub>''μ''</sub> = ''x''<sub>''μ'' + ''v''</sub>}}. Finally, once the value of {{mvar|μ}} is known it is trivial to find the length {{mvar|λ}} of the shortest repeating cycle, by searching for the first position {{math|''μ'' + ''λ''}} for which {{math|1=''x''<sub>''μ'' + ''λ''</sub> = ''x''<sub>''μ''</sub>}}.
The key insight in the algorithm is as follows. If there is a cycle, then, for any integers and , , where is the length of the loop to be found, is the index of the first element of the cycle, and is a whole integer representing the number of loops. Based on this, it can then be shown that for some if and only if (if in the cycle, then there exists some such that , which implies that ; and if there are some and such that , then and ). Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period of a repetition that is a multiple of . Once is found, the algorithm retraces the sequence from its start to find the first repeated value in the sequence, using the fact that divides and therefore that . Finally, once the value of is known it is trivial to find the length of the shortest repeating cycle, by searching for the first position for which .
算法中的关键内容如下。如果存在一个循环，那么对于任何整数，循环的长度是循环的第一个元素的索引，是一个整数，表示循环的数量。在此基础上，它可以被证明，对于一些当且仅当(如果在循环中，那么存在一些这样的，这意味着; 如果存在一些这样的，那么)。因此，算法只需要检查这种特殊形式的重复值，其中一个距离序列开始的距离是另一个的两倍，就可以找到一个重复周期。一旦被发现，算法从它的开始回溯序列，以找到序列中的第一个重复值，使用的事实，除，因此。最后，一旦知道了该值，通过搜索该值的第一个位置来寻找最短重复周期的长度就变得微不足道了。
The algorithm thus maintains two pointers into the given sequence, one (the tortoise) at {{math|''x<sub>i</sub>''}}, and the other (the hare) at {{math|''x''<sub>2''i''</sub>}}. At each step of the algorithm, it increases {{mvar|i}} by one, moving the tortoise one step forward and the hare two steps forward in the sequence, and then compares the sequence values at these two pointers. The smallest value of {{math|''i'' > 0}} for which the tortoise and hare point to equal values is the desired value {{mvar|ν}}.
The algorithm thus maintains two pointers into the given sequence, one (the tortoise) at , and the other (the hare) at . At each step of the algorithm, it increases by one, moving the tortoise one step forward and the hare two steps forward in the sequence, and then compares the sequence values at these two pointers. The smallest value of for which the tortoise and hare point to equal values is the desired value .
因此，算法保持两个指针指向给定的序列，一个(乌龟)在，另一个(野兔)在。在算法的每一步，它增加一个，移动乌龟一步前进和兔子两步前进的序列，然后比较这两个指针的序列值。乌龟和兔子指向相等值的最小值是期望值。
The following [[Python (programming language)|Python]] code shows how this idea may be implemented as an algorithm.
The following Python code shows how this idea may be implemented as an algorithm.
下面的 Python 代码展示了如何将这种思想实现为一种算法。
<syntaxhighlight lang="python">
def floyd(f, x0):
# Main phase of algorithm: finding a repetition x_i = x_2i.
# The hare moves twice as quickly as the tortoise and
# the distance between them increases by 1 at each step.
# Eventually they will both be inside the cycle and then,
# at some point, the distance between them will be
# divisible by the period λ.
tortoise = f(x0) # f(x0) is the element/node next to x0.
hare = f(f(x0))
while tortoise != hare:
tortoise = f(tortoise)
hare = f(f(hare))
# At this point the tortoise position, ν, which is also equal
# to the distance between hare and tortoise, is divisible by
# the period λ. So hare moving in circle one step at a time,
# and tortoise (reset to x0) moving towards the circle, will
# intersect at the beginning of the circle. Because the
# distance between them is constant at 2ν, a multiple of λ,
# they will agree as soon as the tortoise reaches index μ.
<syntaxhighlight lang="python">
def floyd(f, x0):
# Main phase of algorithm: finding a repetition x_i = x_2i.
# The hare moves twice as quickly as the tortoise and
# the distance between them increases by 1 at each step.
# Eventually they will both be inside the cycle and then,
# at some point, the distance between them will be
# divisible by the period λ.
tortoise = f(x0) # f(x0) is the element/node next to x0.
hare = f(f(x0))
while tortoise != hare:
tortoise = f(tortoise)
hare = f(f(hare))
# At this point the tortoise position, ν, which is also equal
# to the distance between hare and tortoise, is divisible by
# the period λ. So hare moving in circle one step at a time,
# and tortoise (reset to x0) moving towards the circle, will
# intersect at the beginning of the circle. Because the
# distance between them is constant at 2ν, a multiple of λ,
# they will agree as soon as the tortoise reaches index μ.
# 算法的主要阶段: 寻找一个重复 x _ i = x _ 2i。# 兔子的速度是乌龟的两倍 # 他们之间的距离每走一步就增加一倍。# 最终它们都在循环中 # 在某个时刻，它们之间的距离 # 可以被周期 λ 整除。Tortoise = f (x0) # f (x0)是 x0旁边的元素/节点。兔子 = f (f (x0))而乌龟！= hare: tortoise = f (tortoise) hare = f (f (hare)) # 此时，乌龟的位置 ν 也等于逐兔棋之间的距离，可以被周期 λ 整除。所以兔子一步一步地在圆里移动，# 和乌龟(重置为 x0)向圆移动，将 # 在圆的开始相交。因为它们之间的 # 距离在2ν 是恒定的，是 λ 的倍数，当乌龟达到指数 μ 时，它们就会一致。
# Find the position μ of first repetition.
mu = 0
tortoise = x0
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare) # Hare and tortoise move at same speed
mu += 1
# Find the length of the shortest cycle starting from x_μ
# The hare moves one step at a time while tortoise is still.
# lam is incremented until λ is found.
lam = 1
hare = f(tortoise)
while tortoise != hare:
hare = f(hare)
lam += 1
return lam, mu
</syntaxhighlight>
# Find the position μ of first repetition.
mu = 0
tortoise = x0
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare) # Hare and tortoise move at same speed
mu += 1
# Find the length of the shortest cycle starting from x_μ
# The hare moves one step at a time while tortoise is still.
# lam is incremented until λ is found.
lam = 1
hare = f(tortoise)
while tortoise != hare:
hare = f(hare)
lam += 1
return lam, mu
</syntaxhighlight>
# 找到第一次重复的位置 μ。Μ = 0乌龟 = x0而乌龟！= hare: tortoise = f (tortoise) hare = f (hare) # 逐兔棋移动速度 μ + = 1 # 从 x _ μ 开始计算最短周期的长度。# lam 是递增的，直到找到 λ。lam = 1
hare = f(tortoise)
while tortoise != hare:
hare = f(hare)
lam += 1
return lam, mu
</syntaxhighlight>
This code only accesses the sequence by storing and copying pointers, function evaluations, and equality tests; therefore, it qualifies as a pointer algorithm. The algorithm uses {{math|''O''(''λ'' + ''μ'')}} operations of these types, and {{math|''O''(1)}} storage space.<ref>{{harvtxt|Joux|2009}}, Section 7.1.1, Floyd's cycle-finding algorithm, pp. 225–226.</ref>
This code only accesses the sequence by storing and copying pointers, function evaluations, and equality tests; therefore, it qualifies as a pointer algorithm. The algorithm uses operations of these types, and storage space., Section 7.1.1, Floyd's cycle-finding algorithm, pp. 225–226.
此代码仅通过存储和复制指针、函数计算和相等性测试来访问序列; 因此，它具有指针算法的资格。该算法使用这些类型的操作和存储空间，第7.1.1节，弗洛伊德的循环寻找算法，pp。225–226.
===Brent's algorithm===
===Brent's algorithm===
===Brent's algorithm===
[[Richard Brent (scientist)|Richard P. Brent]] described an alternative cycle detection algorithm that, like the tortoise and hare algorithm, requires only two pointers into the sequence.<ref name="brent">{{citation|first=R. P.|last=Brent|authorlink=Richard Brent (scientist)|title=An improved Monte Carlo factorization algorithm|journal=[[BIT Numerical Mathematics ]]|volume=20|year=1980|pages=176–184|url=https://maths-people.anu.edu.au/~brent/pd/rpb051i.pdf|doi=10.1007/BF01933190|issue=2|s2cid=17181286}}.</ref> However, it is based on a different principle: searching for the smallest [[power of two]] {{math|2<sup>''i''</sup>}} that is larger than both {{mvar|λ}} and {{mvar|μ}}. For {{math|1=''i'' = 0, 1, 2, ...}}, the algorithm compares {{math|''x''<sub>2<sup>''i''</sup>−1</sub>}} with each subsequent sequence value up to the next power of two, stopping when it finds a match. It has two advantages compared to the tortoise and hare algorithm: it finds the correct length {{mvar|λ}} of the cycle directly, rather than needing to search for it in a subsequent stage, and its steps involve only one evaluation of {{mvar|f}} rather than three.<ref>{{harvtxt|Joux|2009}}, Section 7.1.2, Brent's cycle-finding algorithm, pp. 226–227.</ref>
Richard P. Brent described an alternative cycle detection algorithm that, like the tortoise and hare algorithm, requires only two pointers into the sequence.. However, it is based on a different principle: searching for the smallest power of two that is larger than both and . For , the algorithm compares with each subsequent sequence value up to the next power of two, stopping when it finds a match. It has two advantages compared to the tortoise and hare algorithm: it finds the correct length of the cycle directly, rather than needing to search for it in a subsequent stage, and its steps involve only one evaluation of rather than three., Section 7.1.2, Brent's cycle-finding algorithm, pp. 226–227.
理查德 · P · 布伦特(Richard P. Brent)描述了一种替代循环检测算法，它与乌龟和兔子算法一样，只需要两个指向序列的指针。.然而，它是基于一个不同的原理: 寻找比两者都大的最小二次方和。因为，该算法与每个后续序列值进行比较，直到下一次幂为2，当找到匹配时停止。与乌龟和兔子算法相比，它有两个优点: 它直接找到正确的循环长度，而不需要在后续阶段搜索它，它的步骤只涉及一个评价，而不是三个，第7.1.2节，布伦特循环找到算法，pp。226–227.
The following Python code shows how this technique works in more detail.
<syntaxhighlight lang="python">
def brent(f, x0):
# main phase: search successive powers of two
power = lam = 1
tortoise = x0
hare = f(x0) # f(x0) is the element/node next to x0.
while tortoise != hare:
if power == lam: # time to start a new power of two?
tortoise = hare
power *= 2
lam = 0
hare = f(hare)
lam += 1
The following Python code shows how this technique works in more detail.
<syntaxhighlight lang="python">
def brent(f, x0):
# main phase: search successive powers of two
power = lam = 1
tortoise = x0
hare = f(x0) # f(x0) is the element/node next to x0.
while tortoise != hare:
if power == lam: # time to start a new power of two?
tortoise = hare
power *= 2
lam = 0
hare = f(hare)
lam += 1
下面的 Python 代码更详细地说明了这种技术是如何工作的。主要阶段: 搜索两次幂的连续幂 = lam = 1 tortoise = x0 hare = f (x0) # f (x0)是 x0旁边的元素/节点。而乌龟！= hare: if power = = lam: # time to start a new power of two？tortoise = hare
power *= 2
lam = 0
hare = f(hare)
lam += 1
# Find the position of the first repetition of length λ
tortoise = hare = x0
for i in range(lam):
# range(lam) produces a list with the values 0, 1, ... , lam-1
hare = f(hare)
# The distance between the hare and tortoise is now λ.
# Find the position of the first repetition of length λ
tortoise = hare = x0
for i in range(lam):
# range(lam) produces a list with the values 0, 1, ... , lam-1
hare = f(hare)
# The distance between the hare and tortoise is now λ.
找到第一个重复长度的位置 λ 对于范围 i，tortoise = hare = x0: 范围(lam)生成一个值为0,1，... ，lam-1 hare = f (hare)的列表逐兔棋之间的距离现在是 λ。
# Next, the hare and tortoise move at same speed until they agree
mu = 0
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare)
mu += 1
return lam, mu
</syntaxhighlight>
# Next, the hare and tortoise move at same speed until they agree
mu = 0
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare)
mu += 1
return lam, mu
</syntaxhighlight>
接下来，逐兔棋以同样的速度移动直到他们同意 μ = 0，而乌龟！= 乌龟 = f (乌龟)乌龟 = f (乌龟)乌 + = 1回林，乌
Like the tortoise and hare algorithm, this is a pointer algorithm that uses {{math|''O''(''λ'' + ''μ'')}} tests and function evaluations and {{math|''O''(1)}} storage space. It is not difficult to show that the number of function evaluations can never be higher than for Floyd's algorithm. Brent claims that, on average, his cycle finding algorithm runs around 36% more quickly than Floyd's and that it speeds up the [[Pollard rho algorithm]] by around 24%. He also performs an [[Average-case complexity|average case]] analysis for a randomized version of the algorithm in which the sequence of indices traced by the slower of the two pointers is not the powers of two themselves, but rather a randomized multiple of the powers of two. Although his main intended application was in integer factorization algorithms, Brent also discusses applications in testing pseudorandom number generators.<ref name="brent"/>
Like the tortoise and hare algorithm, this is a pointer algorithm that uses tests and function evaluations and storage space. It is not difficult to show that the number of function evaluations can never be higher than for Floyd's algorithm. Brent claims that, on average, his cycle finding algorithm runs around 36% more quickly than Floyd's and that it speeds up the Pollard rho algorithm by around 24%. He also performs an average case analysis for a randomized version of the algorithm in which the sequence of indices traced by the slower of the two pointers is not the powers of two themselves, but rather a randomized multiple of the powers of two. Although his main intended application was in integer factorization algorithms, Brent also discusses applications in testing pseudorandom number generators.
像龟兔算法一样，这是一个使用测试、函数求值和存储空间的指针算法。不难看出，函数评价的数量永远不会高于弗洛伊德的算法。布伦特声称，平均而言，他的循环寻找算法比弗洛伊德的算法快36% 左右，它使 Pollard rho 算法的速度提高了24% 左右。他还对一个随机版本的算法进行了平均案例分析，在这个算法中，由两个指针中较慢的一个跟踪的指数序列不是两个指针本身的幂，而是两个指针幂的随机倍数。尽管布伦特的主要应用是整数分解算法，但他也讨论了在测试伪随机数生成器方面的应用。
===Gosper's algorithm===
[[Bill Gosper|R. W. Gosper]]'s algorithm<ref name="gosper-impl">{{Cite web |url=http://www.hackersdelight.org/hdcodetxt/loopdet.c.txt |title=Archived copy |access-date=2017-02-08 |archive-url=https://web.archive.org/web/20160414011322/http://hackersdelight.org/hdcodetxt/loopdet.c.txt |archive-date=2016-04-14 |url-status=dead }}</ref><ref>{{Cite web|url=http://www.inwap.com/pdp10/hbaker/hakmem/flows.html|title=Hakmem -- Flows and Iterated Functions -- Draft, Not Yet Proofed}}</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, eg. <math>\mu_l + \lambda \sim \mu_h</math>.
R. W. Gosper's algorithm finds the period \lambda, and the lower and upper bound of the starting point, \mu_l and \mu_u, of the first cycle. The difference between the lower and upper bound is of the same order as the period, eg. \mu_l + \lambda \sim \mu_h.
Gosper 的算法 = = R. W. Gosper 的算法找到第一个周期的周期 λ，以及第一个周期起点的上下界 μ _ l 和 μ _ u。下限和上限之间的差别与周期的顺序相同，例如。Lambda sim mu _ h.
The main feature of Gosper's algorithm is that it never backs up to reevaluate the generator function, and is economical in both space and time. It could be roughly described as a parallel version of Brent's algorithm. While Brent's algorithm gradually increases the gap between the tortoise and hare, Gosper's algorithm uses several tortoises (several previous values are saved), which are roughly exponentially spaced. According to the note in [http://www.inwap.com/pdp10/hbaker/hakmem/flows.html HAKMEM item 132], this algorithm will detect repetition before the third occurrence of any value, eg. the cycle will be iterated at most twice. This note also states that it is sufficient to store <math>\Theta(\log \lambda)</math> previous values; however, the provided implementation<ref name="gosper-impl"/> stores <math>\Theta(\log (\mu + \lambda))</math> values. For example: the function values are 32-bit integers, and it is known a priori that the ''second iteration'' of the cycle ends after at most 2<sup>32</sup> function evaluations since the beginning, viz. <math>\mu + 2\lambda \le 2^{32}</math>. Then it suffices to store 33 32-bit integers.
The main feature of Gosper's algorithm is that it never backs up to reevaluate the generator function, and is economical in both space and time. It could be roughly described as a parallel version of Brent's algorithm. While Brent's algorithm gradually increases the gap between the tortoise and hare, Gosper's algorithm uses several tortoises (several previous values are saved), which are roughly exponentially spaced. According to the note in HAKMEM item 132, this algorithm will detect repetition before the third occurrence of any value, eg. the cycle will be iterated at most twice. This note also states that it is sufficient to store \Theta(\log \lambda) previous values; however, the provided implementation stores \Theta(\log (\mu + \lambda)) values. For example: the function values are 32-bit integers, and it is known a priori that the second iteration of the cycle ends after at most 232 function evaluations since the beginning, viz. \mu + 2\lambda \le 2^{32}. Then it suffices to store 33 32-bit integers.
Gosper 算法的主要特点是不需要重新评估生成器函数，在空间和时间上都很经济。它可以粗略地描述为布伦特算法的一个并行版本。虽然布伦特的算法逐渐增加了乌龟和兔子之间的差距，但戈斯帕的算法使用了几只乌龟(保存了几个以前的值) ，这些乌龟的间隔大致是指数级的。根据 HAKMEM 条目132中的说明，该算法将在任何值的第三次出现之前检测重复，例如。循环最多重复两次。本说明还指出，存储 Θ (log lambda)以前的值就足够了; 但是，提供的实现存储 Θ (log (mu + lambda))值。例如: 函数值是32位整数，并且先验地知道循环的第二次迭代结束于自开始以来最多232次函数求值之后，即。Μ + 2 lambda le 2 ^ {32}.然后它足以存储33个32位整数。
Upon the <math>i</math>-th evaluation of the generator function, the algorithm compares the generated value with <math>O(\log 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>\Theta(\log (\mu + \lambda))</math> values, its space complexity is <math>\Theta(\log (\mu + \lambda))</math>. This is under the usual assumption, present throughout this article, that the size of the function values is constant. Without this assumption, the space complexity is <math>\Omega(\log^2 (\mu + \lambda))</math> since we need at least <math>\mu + \lambda</math> distinct values and thus the size of each value is <math>\Omega(\log (\mu + \lambda))</math>.
Upon the i-th evaluation of the generator function, the algorithm compares the generated value with O(\log i) previous values; observe that i goes up to at least \mu + \lambda and at most \mu + 2\lambda. Therefore, the time complexity of this algorithm is O((\mu + \lambda) \cdot \log (\mu + \lambda)). Since it stores \Theta(\log (\mu + \lambda)) values, its space complexity is \Theta(\log (\mu + \lambda)). This is under the usual assumption, present throughout this article, that the size of the function values is constant. Without this assumption, the space complexity is \Omega(\log^2 (\mu + \lambda)) since we need at least \mu + \lambda distinct values and thus the size of each value is \Omega(\log (\mu + \lambda)).
在对生成器函数进行第 i 次求值时，该算法将生成的值与 O (log i)之前的值进行比较; 观察到 i 至少升至 mu + lambda，至多升至 mu + 2 lambda。因此，该算法的时间复杂度为 O ((mu + lambda)) cdot log (mu + lambda)。因为它存储 Θ (log (mu + lambda))值，所以它的空间复杂度是 Θ (log (mu + lambda))。这是在本文中提出的通常假设下进行的，即函数值的大小是常数。如果没有这个假设，空间复杂度就是 Ω (log ^ 2(mu + lambda)) ，因为我们至少需要 μ + lambda 不同的值，因此每个值的大小就是 Ω (log (mu + lambda))。
===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.
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,. we survey these techniques briefly.
= = = 时间-空间权衡 = = = = 很多作者研究了周期检测技术，比弗洛伊德和布伦特的方法使用更多的内存，但检测周期更快。通常，这些方法存储几个以前计算的序列值，并测试每个新值是否等于以前计算的值之一。为了快速完成这项工作，它们通常使用哈希表或类似的数据结构来存储先前计算的值，因此不是指针算法: 特别是，它们通常不能应用于 Pollard 的 rho 算法。这些方法的不同之处在于它们如何确定要存储的值。继 Nivasch 之后。我们对这些技术进行了简要的调查。
*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|authorlink1=Claus P. Schnorr|first2=Hendrik W.|last2=Lenstra|authorlink2=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|authorlink1=Robert Sedgewick (computer scientist)|first2=Thomas G.|last2=Szymanski|first3=Andrew C.-C.|last3=Yao|authorlink3=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}}.</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|volume=434|publisher=Springer-Verlag|pages=429–434|doi=10.1007/3-540-46885-4_43|doi-access=free}}.</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.
*Brent already describes variations of his technique in which the indices of saved sequence values are powers of a number other than two. By choosing to be a number close to one, and storing the sequence values at indices that are near a sequence of consecutive powers of , a cycle detection algorithm can use a number of function evaluations that is within an arbitrarily small factor of the optimum ...
*Sedgewick, Szymanski, and Yao. provide a method that uses memory cells and requires in the worst case only (\lambda+\mu)(1+cM^{-1/2}) function evaluations, for some constant , which they show to be optimal. The technique involves maintaining a numerical parameter , storing in a table only those positions in the sequence that are multiples of , and clearing the table and doubling 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 might be stored... More simply, 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 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, 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.
* 布伦特已经描述了他的技术的变化，其中保存的序列值的指数是一个数以外的2的幂。通过选择一个接近1的数字，并将序列值存储在接近一系列连续幂的指数中，循环检测算法可以使用一系列函数评估，这些评估在最优因子的任意小范围内...
* Sedgewick，Szymanski，and Yao。提供一种使用内存单元的方法，并且在最坏的情况下只需要(lambda + mu)(1 + cM ^ {-1/2})函数求值，对于某个常数，它们表明是最优的。这种技术包括维护一个数值参数，只在表中存储序列中的那些乘以数的位置，清除表并在存储了太多值时加倍。
* 几位作者已经描述了基于涉及值的标准而不是(如 Sedgewick 等人的方法)在表中存储函数值的区分点方法根据他们的位置。例如，等于零的模数值可能会被存储... ... 更简单地说，Nivasch 相信 D.P.Woodruff 的建议，即存储一个先前看到的值的随机样本，在每一步做出适当的随机选择，使样本保持随机。
* Nivasch 描述了一种算法，它不使用固定数量的内存，但使用的预期内存数量(假设输入函数是随机的)是序列长度的对数。使用此技术，当以后的项没有较小值时，项存储在内存表中。如 Nivasch 所示，使用这种技术的项可以使用堆栈数据结构来维护，并且每个连续的序列值只需要与堆栈顶部进行比较。当找到具有最小值的重复序列元素时，算法终止。对多个堆栈运行相同的算法，使用值的随机排列重新排列每个堆栈中的值，允许类似于以前的算法的时空折衷。但是，由于需要进行比较以确定两个值中哪一个更小，因此即使这种算法的版本只有一个堆栈也不是指针算法。
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|authorlink=Faith Ellen|contribution=Lower bounds for the cycle detection problem|title=Proc. 13th ACM [[Symposium on Theory of Computing]]|year=1981|doi=10.1145/800076.802462|pages=96–105}}.</ref><ref>{{citation|first1=Eric W.|last1=Allender|authorlink1=Eric Allender|first2=Maria M.|last2=Klawe|authorlink2=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>
Any cycle detection algorithm that stores at most values from the input sequence must perform at least (\lambda+\mu)\left(1+\frac{1}{M-1}\right) function evaluations...
任何存储最多输入序列值的循环检测算法必须执行至少(lambda + mu)的左(1 + frac {1}{ M-1}右)函数计算..。
==Applications==
==Applications==
= = 应用 = =
Cycle detection has been used in many applications.
*Determining the cycle length of a [[pseudorandom number generator]] is one measure of its strength. This is the application cited by Knuth in describing Floyd's method.<ref name="knuth"/> Brent<ref name="brent"/> describes the results of testing a [[linear congruential generator]] in this fashion; its period turned out to be significantly smaller than advertised. For more complex generators, the sequence of values in which the cycle is to be found may not represent the output of the generator, but rather its internal state.
*Several [[Number theory|number-theoretic]] algorithms are based on cycle detection, including [[Pollard's rho algorithm]] for integer factorization<ref>{{citation|first=J. M.|last=Pollard|title=A Monte Carlo method for factorization|journal=BIT|volume=15|year=1975|pages=331–334|doi=10.1007/BF01933667|issue=3|s2cid=122775546}}.</ref> and his related [[Pollard's kangaroo algorithm|kangaroo algorithm]] for the [[discrete logarithm]] problem.<ref>{{citation|first=J. M.|last=Pollard|title=Monte Carlo methods for index computation {{math|(mod ''p''}})|journal=[[Mathematics of Computation]]|volume=32|issue=143|year=1978|pages=918–924|doi=10.2307/2006496|publisher=American Mathematical Society|jstor=2006496}}.</ref>
*In [[Cryptography|cryptographic]] applications, the ability to find two distinct values ''x''<sub>μ−-1</sub> and ''x''<sub>λ+μ−-1</sub> mapped by some cryptographic function ƒ to the same value ''x''<sub>μ</sub> may indicate a weakness in ƒ. For instance, Quisquater and Delescaille<ref name="qd"/> apply cycle detection algorithms in the search for a message and a pair of [[Data Encryption Standard]] keys that map that message to the same encrypted value; [[Burt Kaliski|Kaliski]], [[Ron Rivest|Rivest]], and [[Alan Sherman|Sherman]]<ref name="krs">{{citation|first1=Burton S., Jr.|last1=Kaliski|first2=Ronald L.|last2=Rivest|authorlink2=Ron Rivest|first3=Alan T.|last3=Sherman|title=Is the Data Encryption Standard a group? (Results of cycling experiments on DES)|journal=[[Journal of Cryptology]]|volume=1|issue=1|year=1988|pages=3–36|doi=10.1007/BF00206323|s2cid=17224075}}.</ref> also use cycle detection algorithms to attack DES. The technique may also be used to find a [[hash collision|collision]] in a [[cryptographic hash function]].<ref>{{harvtxt|Joux|2009}}, Section 7.5, Collisions in hash functions, pp. 242–245.</ref>
*Cycle detection may be helpful as a way of discovering [[infinite loop]]s in certain types of [[computer program]]s.<ref>{{citation|first=Allen|last=Van Gelder|title=Efficient loop detection in Prolog using the tortoise-and-hare technique|journal=Journal of Logic Programming|volume=4|issue=1|pages=23–31|year=1987|doi=10.1016/0743-1066(87)90020-3|doi-access=free}}.</ref>
*[[Oscillator (cellular automaton)|Periodic configurations]] in [[cellular automaton]] simulations may be found by applying cycle detection algorithms to the sequence of automaton states.<ref name="nivasch"/>
*[[Shape analysis (software)|Shape analysis]] of [[linked list]] data structures is a technique for verifying the correctness of an algorithm using those structures. If a node in the list incorrectly points to an earlier node in the same list, the structure will form a cycle that can be detected by these algorithms.<ref>{{citation|first1=Mikhail|last1=Auguston|first2=Miu Har|last2=Hon|contribution=Assertions for Dynamic Shape Analysis of List Data Structures|pages=37–42|title=AADEBUG '97, Proceedings of the Third International Workshop on Automatic Debugging|series=Linköping Electronic Articles in Computer and Information Science|publisher=[[Linköping University]]|url=http://www.ep.liu.se/ea/cis/1997/009/04/|year=1997}}.</ref> In [[Common Lisp]], the [[S-expression]] printer, under control of the <code>*print-circle*</code> variable, detects circular list structure and prints it compactly.
*Teske<ref name="teske"/> describes applications in [[computational group theory]]: determining the structure of an [[Abelian group]] from a set of its generators. The cryptographic algorithms of Kaliski et al.<ref name="krs"/> may also be viewed as attempting to infer the structure of an unknown group.
*{{harvtxt|Fich|1981}} briefly mentions an application to [[computer simulation]] of [[celestial mechanics]], which she attributes to [[William Kahan]]. In this application, cycle detection in the [[phase space]] of an orbital system may be used to determine whether the system is periodic to within the accuracy of the simulation.<ref name="fich"/>
*In [[Mandelbrot Set]] fractal generation some performance techniques are used to speed up the image generation. One of them is called "period checking", which consists of finding the cycles in a point orbit. This article describes the "[[wikibooks:Fractals/Iterations_in_the_complex_plane/Mandelbrot_set/mandelbrot#Periodicity_checking|period checking]]" technique. You can find another explanation [http://math.bu.edu/DYSYS/FRACGEOM/node1.html#SECTION00010000000000000000 here]. Some cycle detection algorithms have to be implemented in order to implement this technique.
Cycle detection has been used in many applications.
*Determining the cycle length of a pseudorandom number generator is one measure of its strength. This is the application cited by Knuth in describing Floyd's method. Brent describes the results of testing a linear congruential generator in this fashion; its period turned out to be significantly smaller than advertised. For more complex generators, the sequence of values in which the cycle is to be found may not represent the output of the generator, but rather its internal state.
*Several number-theoretic algorithms are based on cycle detection, including Pollard's rho algorithm for integer factorization. and his related kangaroo algorithm for the discrete logarithm problem..
*In cryptographic applications, the ability to find two distinct values xμ−-1 and xλ+μ−-1 mapped by some cryptographic function ƒ to the same value xμ may indicate a weakness in ƒ. For instance, Quisquater and Delescaille apply cycle detection algorithms in the search for a message and a pair of Data Encryption Standard keys that map that message to the same encrypted value; Kaliski, Rivest, and Sherman. also use cycle detection algorithms to attack DES. The technique may also be used to find a collision in a cryptographic hash function., Section 7.5, Collisions in hash functions, pp. 242–245.
*Cycle detection may be helpful as a way of discovering infinite loops in certain types of computer programs..
*Periodic configurations in cellular automaton simulations may be found by applying cycle detection algorithms to the sequence of automaton states.
*Shape analysis of linked list data structures is a technique for verifying the correctness of an algorithm using those structures. If a node in the list incorrectly points to an earlier node in the same list, the structure will form a cycle that can be detected by these algorithms.. In Common Lisp, the S-expression printer, under control of the *print-circle* variable, detects circular list structure and prints it compactly.
*Teske describes applications in computational group theory: determining the structure of an Abelian group from a set of its generators. The cryptographic algorithms of Kaliski et al. may also be viewed as attempting to infer the structure of an unknown group.
* briefly mentions an application to computer simulation of celestial mechanics, which she attributes to William Kahan. In this application, cycle detection in the phase space of an orbital system may be used to determine whether the system is periodic to within the accuracy of the simulation.
*In Mandelbrot Set fractal generation some performance techniques are used to speed up the image generation. One of them is called "period checking", which consists of finding the cycles in a point orbit. This article describes the "period checking" technique. You can find another explanation here. Some cycle detection algorithms have to be implemented in order to implement this technique.
循环检测在许多应用中得到了广泛的应用。
* 确定伪随机数生成器的周期长度是衡量其强度的一项指标。这是克努特在描述弗洛伊德的方法时引用的应用。布伦特用这种方式描述了测试线性同余方法的结果，结果发现它的周期比广告上说的要短得多。对于更复杂的生成器，循环的值序列可能不代表生成器的输出，而是代表其内部状态。
* 一些数论算法基于循环检测，包括 Pollard 的 rho 整数分解算法。以及他相关的袋鼠算法来解决离散对数问题。.
* 在加密应用中，能够找到由某个加密函数 f 映射到相同值 xμ 的两个不同值 xμ-1和 xλ + μ-1，可能表明 f 的弱点。例如，Quisquater 和 Delescaille 应用循环检测算法来搜索一条消息和一对数据加密标准密钥，这些密钥将消息映射到相同的加密值，如 Kaliski、 Riest 和 Sherman。也使用循环检测算法来攻击 DES。该技术还可以用于查找加密哈希函数中的冲突。242–245.
* 循环检测可能有助于在某些类型的计算机程序中发现无限循环。.
* 通过对自动机状态序列应用循环检测算法，可以发现细胞自动机模拟中的周期性配置。
* 对链表数据结构的形状分析是一种利用这些结构验证算法正确性的技术。如果列表中的一个节点不正确地指向同一列表中的一个早期节点，则该结构将形成一个循环，可由这些算法检测到。.在 Common Lisp 中，S 表达式打印机在
* print-Circle
* 变量的控制下，检测循环列表结构并将其打印得非常简洁。
* Teske 描述了计算群论中的应用: 从一组生成元中确定一个阿贝尔群的结构。Kaliski 等人的密码算法。也可以被视为试图推断一个未知群体的结构。
* 简要提到了一份计算机模拟天体力学的申请，她认为是威廉 · 卡汉提出的。在这种应用中，轨道系统相空间中的周期探测可用于确定该系统是否在模拟精度范围内是周期性的。
* 在 Mandelbrot 集分形生成中，使用了一些性能技术来加速图像生成。其中之一称为“周期检查”，即在点轨道上寻找周期。本文描述了“周期检查”技术。你可以在这里找到另一种解释。为了实现这一技术，必须实现一些循环检测算法。
==References==
{{reflist|30em}}
==External links==
*Gabriel Nivasch, [http://www.gabrielnivasch.org/fun/cycle-detection The Cycle Detection Problem and the Stack Algorithm]
*[http://wiki.c2.com/?TortoiseAndHare Tortoise and Hare], Portland Pattern Repository
*[https://web.archive.org/web/20160313063357/http://www.siafoo.net/algorithm/10 Floyd's Cycle Detection Algorithm (The Tortoise and the Hare)]
*[https://web.archive.org/web/20160304043822/http://www.siafoo.net/algorithm/11 Brent's Cycle Detection Algorithm (The Teleporting Turtle)]
*Gabriel Nivasch, The Cycle Detection Problem and the Stack Algorithm
*Tortoise and Hare, Portland Pattern Repository
*Floyd's Cycle Detection Algorithm (The Tortoise and the Hare)
*Brent's Cycle Detection Algorithm (The Teleporting Turtle)
= = 外部链接 = =
* 加布里埃尔 · 尼瓦什，循环检测问题和堆栈算法
* 乌龟和野兔，波特兰模式仓库
* 弗洛伊德的循环检测算法(龟兔赛跑)
* 布伦特的循环检测算法(瞬移海龟)
{{DEFAULTSORT:Cycle Detection}}
[[Category:Fixed points (mathematics)]]
[[Category:Combinatorial algorithms]]
[[Category:Articles with example Python (programming language) code]]
Category:Fixed points (mathematics)
Category:Combinatorial algorithms
Category:Articles with example Python (programming language) code
类别: 固定点(数学)类别: 组合算法类别: 具有示例 Python (编程语言)代码的文章
<noinclude>
<small>This page was moved from [[wikipedia:en:Cycle detection]]. Its edit history can be viewed at [[圈检测/edithistory]]</small></noinclude>
[[Category:待整理页面]]
{{about|iterated functions|another use|Cycle detection (graph theory)}}
{{Technical|date=February 2018}}
In [[computer science]], '''cycle detection''' or '''cycle finding''' is the [[algorithm]]ic problem of finding a cycle in a [[sequence]] of [[iterated function]] values.
In computer science, cycle detection or cycle finding is the algorithmic problem of finding a cycle in a sequence of iterated function values.
在计算机科学中，循环检测或循环寻找是在一系列计算问题值中寻找循环的迭代函数。
For any [[function (mathematics)|function]] {{mvar|f}} that maps a [[finite set]] {{mvar|S}} to itself, and any initial value {{math|''x''<sub>0</sub>}} in {{mvar|S}}, the sequence of iterated function values
For any function that maps a finite set to itself, and any initial value in , the sequence of iterated function values
对于任何将有限集映射到自身的函数，以及其中的任何初始值，迭代函数的序列
:<math> x_0,\ x_1=f(x_0),\ x_2=f(x_1),\ \dots,\ x_i=f(x_{i-1}),\ \dots</math>
: x_0,\ x_1=f(x_0),\ x_2=f(x_1),\ \dots,\ x_i=f(x_{i-1}),\ \dots
: x _ 0，x _ 1 = f (x _ 0) ，x _ 2 = f (x _ 1) ，点，x _ i = f (x _ { i-1}) ，点
must eventually use the same value twice: there must be some pair of distinct indices {{mvar|i}} and {{mvar|j}} such that {{math|1=''x<sub>i</sub>'' = ''x<sub>j</sub>''}}. Once this happens, the sequence must continue [[periodic sequence|periodically]], by repeating the same sequence of values from {{math|''x<sub>i</sub>''}} to {{math|''x''<sub>''j'' − 1</sub>}}. Cycle detection is the problem of finding {{mvar|i}} and {{mvar|j}}, given {{mvar|f}} and {{math|''x''<sub>0</sub>}}.
must eventually use the same value twice: there must be some pair of distinct indices and such that . Once this happens, the sequence must continue periodically, by repeating the same sequence of values from to . Cycle detection is the problem of finding and , given and .
最终必须使用相同的值两次: 必须有一对不同的索引，这样。一旦发生这种情况，序列必须通过重复相同的值序列来周期性地继续。循环检测是查找和给定的问题。
Several algorithms for finding cycles quickly and with little memory are known. [[Robert W. Floyd]]'s [[Cycle detection#Floyd's_tortoise_and_hare|tortoise and hare algorithm]] moves two pointers at different speeds through the sequence of values until they both point to equal values. Alternatively, Brent's algorithm is based on the idea of [[exponential search]]. Both Floyd's and Brent's algorithms use only a constant number of memory cells, and take a number of function evaluations that is proportional to the distance from the start of the sequence to the first repetition. Several other algorithms trade off larger amounts of memory for fewer function evaluations.
Several algorithms for finding cycles quickly and with little memory are known. Robert W. Floyd's tortoise and hare algorithm moves two pointers at different speeds through the sequence of values until they both point to equal values. Alternatively, Brent's algorithm is based on the idea of exponential search. Both Floyd's and Brent's algorithms use only a constant number of memory cells, and take a number of function evaluations that is proportional to the distance from the start of the sequence to the first repetition. Several other algorithms trade off larger amounts of memory for fewer function evaluations.
已经知道几种快速查找循环和内存不足的算法。罗伯特 · 弗洛伊德的乌龟和兔子算法以不同的速度移动两个指针通过值的序列，直到它们都指向相等的值。另外，布伦特的算法是基于指数搜索的思想。弗洛伊德和布伦特的算法都只使用固定数量的存储单元，并采取一些功能评估是成正比的距离，从序列的开始到第一次重复。其他一些算法用较少的函数计算来交换较大的内存。
The applications of cycle detection include testing the quality of [[pseudorandom number generator]]s and [[cryptographic hash function]]s, [[computational number theory]] algorithms, detection of [[infinite loop]]s in computer programs and periodic configurations in [[cellular automaton|cellular automata]], automated [[Shape analysis (software)|shape analysis]] of [[linked list]] data structures, and detection of [[Deadlock|deadlocks]] for [[Transaction manager|transactions management]] in [[Database|DBMS]].
The applications of cycle detection include testing the quality of pseudorandom number generators and cryptographic hash functions, computational number theory algorithms, detection of infinite loops in computer programs and periodic configurations in cellular automata, automated shape analysis of linked list data structures, and detection of deadlocks for transactions management in DBMS.
循环检测的应用包括测试伪随机数生成器和加密哈希函数的质量、计算数论算法、检测电脑程序中的无限循环和细胞自动机中的周期性配置、对链表数据结构进行自动形状分析，以及在数据库管理系统中检测事务管理中的死锁。
==Example==
[[File:Functional graph.svg|thumb|upright=1.5|A function from and to the set {0,1,2,3,4,5,6,7,8} and the corresponding [[functional graph]]]]
The figure shows a function {{mvar|f}} that maps the set {{math|1=''S'' = {0,1,2,3,4,5,6,7,8} }} to itself. If one starts from {{math|1=''x''<sub>0</sub> = 2}} and repeatedly applies {{mvar|f}}, one sees the sequence of values
:{{math|2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ....}}
The cycle in this value sequence is {{math|6, 3, 1}}.
The figure shows a function that maps the set to itself. If one starts from and repeatedly applies , one sees the sequence of values
:
The cycle in this value sequence is .
图中显示了一个将集合映射到自身的函数。如果开始并重复应用，就会看到值序列: 这个值序列中的循环是。
==Definitions==
==Definitions==
= = 定义 = =
Let {{mvar|S}} be any finite set, {{mvar|f}} be any function from {{mvar|S}} to itself, and {{math|''x''<sub>0</sub>}} be any element of {{mvar|S}}. For any {{math|''i'' > 0}}, let {{math|1=''x<sub>i</sub>'' = ''f''(''x''<sub>''i'' − 1</sub>)}}. Let {{mvar|μ}} be the smallest index such that the value {{math|''x''<sub>''μ''</sub>}} reappears infinitely often within the sequence of values {{math|''x<sub>i</sub>''}}, and let {{mvar|λ}} (the loop length) be the smallest positive integer such that {{math|1=''x''<sub>''μ''</sub> = ''x''<sub>''λ'' + ''μ''</sub>}}. The cycle detection problem is the task of finding {{mvar|λ}} and {{mvar|μ}}.<ref>{{citation|title=Algorithmic Cryptanalysis|first=Antoine|last=Joux|publisher=CRC Press|year=2009|isbn=9781420070033|page=223|url=https://books.google.com/books?id=buQajqt-_iUC&pg=PA223}}.</ref>
Let be any finite set, be any function from to itself, and be any element of . For any , let . Let be the smallest index such that the value reappears infinitely often within the sequence of values , and let (the loop length) be the smallest positive integer such that . The cycle detection problem is the task of finding and ..
设为任意有限集，任意函数自身，任意元素。对于任何人，让。设为最小的索引，使得该值在值序列中无限频繁地重现，并且设(循环长度)为最小的正整数，使得。循环检测问题的任务是发现和. 。
One can view the same problem [[graph theory|graph-theoretically]], by constructing a [[functional graph]] (that is, a [[directed graph]] in which each vertex has a single outgoing edge) the vertices of which are the elements of {{mvar|S}} and the edges of which map an element to the corresponding function value, as shown in the figure. The set of vertices [[Reachability|reachable]] from starting vertex {{math|''x''<sub>0</sub>}} form a subgraph with a shape resembling the [[Rho (letter)|Greek letter rho]] ({{mvar|ρ}}): a path of length {{mvar|μ}} from {{math|''x''<sub>0</sub>}} to a [[Cycle (graph theory)|cycle]] of {{mvar|λ}} vertices.<ref name="j224">{{harvtxt|Joux|2009|page=224}}.</ref>
One can view the same problem graph-theoretically, by constructing a functional graph (that is, a directed graph in which each vertex has a single outgoing edge) the vertices of which are the elements of and the edges of which map an element to the corresponding function value, as shown in the figure. The set of vertices reachable from starting vertex form a subgraph with a shape resembling the Greek letter rho (): a path of length from to a cycle of vertices..
人们可以查看相同的问题图——从理论上讲，通过构造一个函数图(也就是说，一个有向图，其中每个顶点有一个单一的出口边) ，其中的顶点是元素，其中的边将一个元素映射到相应的函数值，如图所示。从起始点到达的一组顶点形成一个子图，其形状类似于希腊字母 rho () : 从一个顶点循环到一个顶点循环的长度路径。.
==Computer representation==
Generally, {{mvar|f}} will not be specified as a table of values, the way it is shown in the figure above. Rather, a cycle detection algorithm may be given access either to the sequence of values {{math|''x<sub>i</sub>''}}, or to a subroutine for calculating {{mvar|f}}. The task is to find {{mvar|λ}} and {{mvar|μ}} while examining as few values from the sequence or performing as few subroutine calls as possible. Typically, also, the [[space complexity]] of an algorithm for the cycle detection problem is of importance: we wish to solve the problem while using an amount of memory significantly smaller than it would take to store the entire sequence.
Generally, will not be specified as a table of values, the way it is shown in the figure above. Rather, a cycle detection algorithm may be given access either to the sequence of values , or to a subroutine for calculating . The task is to find and while examining as few values from the sequence or performing as few subroutine calls as possible. Typically, also, the space complexity of an algorithm for the cycle detection problem is of importance: we wish to solve the problem while using an amount of memory significantly smaller than it would take to store the entire sequence.
= = 计算机表示 = = 通常不会被指定为值表，如上图所示。相反，循环检测算法可以访问值的序列，或者访问用于计算的子程序。任务是从序列中查找并检查尽可能少的值或执行尽可能少的子例程调用。通常，循环检测问题的算法的空间复杂度也很重要: 我们希望解决这个问题，同时使用比存储整个序列所需要的内存量小得多的内存。
In some applications, and in particular in [[Pollard's rho algorithm]] for [[integer factorization]], the algorithm has much more limited access to {{mvar|S}} and to {{mvar|f}}. In Pollard's rho algorithm, for instance, {{mvar|S}} is the set of integers modulo an unknown prime factor of the number to be factorized, so even the size of {{mvar|S}} is unknown to the algorithm.
To allow cycle detection algorithms to be used with such limited knowledge, they may be designed based on the following capabilities. Initially, the algorithm is assumed to have in its memory an object representing a [[Pointer (computer programming)|pointer]] to the starting value {{math|''x''<sub>0</sub>}}. At any step, it may perform one of three actions: it may copy any pointer it has to another object in memory, it may apply {{mvar|f}} and replace any of its pointers by a pointer to the next object in the sequence, or it may apply a subroutine for determining whether two of its pointers represent equal values in the sequence. The equality test action may involve some nontrivial computation: for instance, in Pollard's rho algorithm, it is implemented by testing whether the difference between two stored values has a nontrivial [[greatest common divisor]] with the number to be factored.<ref name="j224"/> In this context, by analogy to the [[pointer machine]] model of computation, an algorithm that only uses pointer copying, advancement within the sequence, and equality tests may be called a pointer algorithm.
In some applications, and in particular in Pollard's rho algorithm for integer factorization, the algorithm has much more limited access to and to . In Pollard's rho algorithm, for instance, is the set of integers modulo an unknown prime factor of the number to be factorized, so even the size of is unknown to the algorithm.
To allow cycle detection algorithms to be used with such limited knowledge, they may be designed based on the following capabilities. Initially, the algorithm is assumed to have in its memory an object representing a pointer to the starting value . At any step, it may perform one of three actions: it may copy any pointer it has to another object in memory, it may apply and replace any of its pointers by a pointer to the next object in the sequence, or it may apply a subroutine for determining whether two of its pointers represent equal values in the sequence. The equality test action may involve some nontrivial computation: for instance, in Pollard's rho algorithm, it is implemented by testing whether the difference between two stored values has a nontrivial greatest common divisor with the number to be factored. In this context, by analogy to the pointer machine model of computation, an algorithm that only uses pointer copying, advancement within the sequence, and equality tests may be called a pointer algorithm.
在一些应用程序中，特别是在 Pollard 的 rho 整数分解算法中，该算法的访问和访问受到更多的限制。例如，在 Pollard 的 rho 算法中，整数模的集合是一个未知素因子的数，所以即使是素因子的大小对算法来说也是未知的。为了使循环检测算法能够在如此有限的知识条件下使用，它们可以基于以下功能进行设计。最初，假定算法的内存中有一个表示指向起始值的指针的对象。在任何步骤中，它可以执行三个操作之一: 它可以复制任何指向内存中另一个对象的指针，它可以应用并用指向序列中下一个对象的指针替换它的任何指针，或者它可以应用一个子例程来确定它的两个指针在序列中是否表示相等的值。相等性测试操作可能涉及一些非平凡的计算，例如，在 Pollard 的 rho 算法中，它是通过测试两个存储值之间的差异是否与要分解的数值有一个非平凡的最大公约数来实现的。在这种情况下，类似于指针机器的计算模型，一种只使用指针复制、序列内进步和相等性测试的算法可以称为指针算法。
==Algorithms==
==Algorithms==
= = 算法 = =
If the input is given as a subroutine for calculating {{mvar|f}}, the cycle detection problem may be trivially solved using only {{math|''λ'' + ''μ''}} function applications, simply by computing the sequence of values {{math|''x<sub>i</sub>''}} and using a [[data structure]] such as a [[hash table]] to store these values and test whether each subsequent value has already been stored. However, the space complexity of this algorithm is proportional to {{math|''λ'' + ''μ''}}, unnecessarily large. Additionally, to implement this method as a [[pointer algorithm]] would require applying the equality test to each pair of values, resulting in quadratic time overall. Thus, research in this area has concentrated on two goals: using less space than this naive algorithm, and finding pointer algorithms that use fewer equality tests.
If the input is given as a subroutine for calculating , the cycle detection problem may be trivially solved using only function applications, simply by computing the sequence of values and using a data structure such as a hash table to store these values and test whether each subsequent value has already been stored. However, the space complexity of this algorithm is proportional to , unnecessarily large. Additionally, to implement this method as a pointer algorithm would require applying the equality test to each pair of values, resulting in quadratic time overall. Thus, research in this area has concentrated on two goals: using less space than this naive algorithm, and finding pointer algorithms that use fewer equality tests.
如果输入是作为计算子程序提供的，循环检测问题可以通过仅使用函数应用程序简单地解决，只需计算值的序列，并使用哈希表等数据结构来存储这些值，并测试是否已经存储了每个后续值。然而，该算法的空间复杂度是成比例的，不必要地大。此外，要将这种方法作为指针算法来实现，需要对每对值进行相等性测试，从而导致总体时间为二次型。因此，该领域的研究集中在两个目标上: 使用比这种幼稚算法更少的空间，以及寻找使用更少相等性测试的指针算法。
{{Anchor|Tortoise and hare}}
===Floyd's tortoise and hare===
[[File:Tortoise and hare algorithm.svg|thumb|upright=1.25|Floyd's "tortoise and hare" cycle detection algorithm, applied to the sequence 2, 0, 6, 3, 1, 6, 3, 1, ...]]
'''Floyd's cycle-finding algorithm''' is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. It is also called the "tortoise and the hare algorithm", alluding to Aesop's fable of [[The Tortoise and the Hare]].
thumb|upright=1.25|Floyd's "tortoise and hare" cycle detection algorithm, applied to the sequence 2, 0, 6, 3, 1, 6, 3, 1, ...
Floyd's cycle-finding algorithm is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. It is also called the "tortoise and the hare algorithm", alluding to Aesop's fable of The Tortoise and the Hare.
= = = 弗洛伊德的乌龟和兔子 = = = 拇指 | 直立 = 1.25 | 弗洛伊德的“乌龟和兔子”循环检测算法，应用于序列2,0,6,3,1,6,3,1，... 弗洛伊德的循环检测算法是一个指针算法，只使用两个指针，它们以不同的速度在序列中移动。它也被称为“乌龟和兔子算法”，暗指伊索寓言中的龟兔赛跑。
The algorithm is named after [[Robert W. Floyd]], who was credited with its invention by [[Donald Knuth]].<ref name="knuth">{{citation|first=Donald E.|last=Knuth|authorlink=Donald Knuth|title=The Art of Computer Programming, vol. II: Seminumerical Algorithms|publisher=Addison-Wesley|year=1969|page=7, exercises 6 and 7}}</ref><ref>''Handbook of Applied Cryptography,'' by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, [https://books.google.com/books?id=nSzoG72E93MC&pg=PA125 p. 125], describes this algorithm and others</ref> However, the algorithm does not appear in Floyd's published work, and this may be a misattribution: Floyd describes algorithms for listing all simple cycles in a [[directed graph]] in a 1967 paper,<ref>{{citation|last=Floyd|first=R.W.|authorlink=Robert W. Floyd|title=Nondeterministic Algorithms|journal=J. ACM|pages=636–644|volume=14|issue=4|year=1967|doi=10.1145/321420.321422|s2cid=1990464}}</ref> but this paper does not describe the cycle-finding problem in functional graphs that is the subject of this article. In fact, Knuth's statement (in 1969), attributing it to Floyd, without citation, is the first known appearance in print, and it thus may be a [[Mathematical folklore|folk theorem]], not attributable to a single individual.<ref>''The Hash Function BLAKE,'' by Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), [https://books.google.com/books?id=nhPmBQAAQBAJ&pg=PA21 p. 21], footnote 8</ref>
The algorithm is named after Robert W. Floyd, who was credited with its invention by Donald Knuth.Handbook of Applied Cryptography, by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, p. 125, describes this algorithm and others However, the algorithm does not appear in Floyd's published work, and this may be a misattribution: Floyd describes algorithms for listing all simple cycles in a directed graph in a 1967 paper, but this paper does not describe the cycle-finding problem in functional graphs that is the subject of this article. In fact, Knuth's statement (in 1969), attributing it to Floyd, without citation, is the first known appearance in print, and it thus may be a folk theorem, not attributable to a single individual.The Hash Function BLAKE, by Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), p. 21, footnote 8
该算法以罗伯特 · W · 弗洛伊德的名字命名，他被认为是唐纳德 · 克努斯发明的。应用密码学手册，作者: Alfred J。 Meneze，Paul C。 van Oorschot，Scott A。 Vanstone，p. 125，描述了这个算法和其他一些算法。然而，这个算法并没有出现在 Floyd 的出版物中，这可能是一个错误的归属: Floyd 在1967年的一篇论文中描述了在有向图中列出所有简单循环的算法，但是这篇论文并没有描述本文主题的函数图中的循环寻找问题。事实上，Knuth (在1969年)的声明，把它归因于弗洛伊德，没有引用，是第一个已知的出现在印刷品，因此它可能是一个民间定理，不归因于一个单一的个人。哈希函数 BLAKE，Jean-Philippe Aumasson，Willi Meier，Raphael C-W。Phan，Luca Henzen (2015) ，p. 21，脚注8
The key insight in the algorithm is as follows. If there is a cycle, then, for any integers {{math|''i'' ≥ ''μ''}} and {{math|''k'' ≥ 0}}, {{math|1=''x<sub>i</sub>'' = ''x''<sub>''i'' + ''kλ''</sub>}}, where {{mvar|λ}} is the length of the loop to be found, {{mvar|μ}} is the index of the first element of the cycle, and {{mvar|k}} is a whole integer representing the number of loops. Based on this, it can then be shown that {{math|1=''i'' = ''kλ'' ≥ ''μ''}} for some {{math|''k''}} if and only if {{math|1=''x<sub>i</sub>'' = ''x''<sub>2''i''</sub>}} (if {{math|1=''x<sub>i</sub>'' = ''x''<sub>2''i''</sub>}} in the cycle, then there exists some {{mvar|k}} such that {{math|1=2''i'' = ''i'' + ''kλ''}}, which implies that {{math|1=''i'' = ''kλ''}}; and if there are some {{mvar|i}} and {{mvar|k}} such that {{math|1=''i'' = ''kλ''}}, then {{math|1=''2i'' = ''i'' + ''kλ''}} and {{math|1= ''x''<sub>2''i''</sub> = ''x''<sub>''i'' + ''kλ''</sub>}}). Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period {{mvar|ν}} of a repetition that is a multiple of {{mvar|λ}}. Once {{mvar|ν}} is found, the algorithm retraces the sequence from its start to find the first repeated value {{math|''x''<sub>''μ''</sub>}} in the sequence, using the fact that {{mvar|λ}} divides {{mvar|ν}} and therefore that {{math|1=''x''<sub>''μ''</sub> = ''x''<sub>''μ'' + ''v''</sub>}}. Finally, once the value of {{mvar|μ}} is known it is trivial to find the length {{mvar|λ}} of the shortest repeating cycle, by searching for the first position {{math|''μ'' + ''λ''}} for which {{math|1=''x''<sub>''μ'' + ''λ''</sub> = ''x''<sub>''μ''</sub>}}.
The key insight in the algorithm is as follows. If there is a cycle, then, for any integers and , , where is the length of the loop to be found, is the index of the first element of the cycle, and is a whole integer representing the number of loops. Based on this, it can then be shown that for some if and only if (if in the cycle, then there exists some such that , which implies that ; and if there are some and such that , then and ). Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period of a repetition that is a multiple of . Once is found, the algorithm retraces the sequence from its start to find the first repeated value in the sequence, using the fact that divides and therefore that . Finally, once the value of is known it is trivial to find the length of the shortest repeating cycle, by searching for the first position for which .
算法中的关键内容如下。如果存在一个循环，那么对于任何整数，循环的长度是循环的第一个元素的索引，是一个整数，表示循环的数量。在此基础上，它可以被证明，对于一些当且仅当(如果在循环中，那么存在一些这样的，这意味着; 如果存在一些这样的，那么)。因此，算法只需要检查这种特殊形式的重复值，其中一个距离序列开始的距离是另一个的两倍，就可以找到一个重复周期。一旦被发现，算法从它的开始回溯序列，以找到序列中的第一个重复值，使用的事实，除，因此。最后，一旦知道了该值，通过搜索该值的第一个位置来寻找最短重复周期的长度就变得微不足道了。
The algorithm thus maintains two pointers into the given sequence, one (the tortoise) at {{math|''x<sub>i</sub>''}}, and the other (the hare) at {{math|''x''<sub>2''i''</sub>}}. At each step of the algorithm, it increases {{mvar|i}} by one, moving the tortoise one step forward and the hare two steps forward in the sequence, and then compares the sequence values at these two pointers. The smallest value of {{math|''i'' > 0}} for which the tortoise and hare point to equal values is the desired value {{mvar|ν}}.
The algorithm thus maintains two pointers into the given sequence, one (the tortoise) at , and the other (the hare) at . At each step of the algorithm, it increases by one, moving the tortoise one step forward and the hare two steps forward in the sequence, and then compares the sequence values at these two pointers. The smallest value of for which the tortoise and hare point to equal values is the desired value .
因此，算法保持两个指针指向给定的序列，一个(乌龟)在，另一个(野兔)在。在算法的每一步，它增加一个，移动乌龟一步前进和兔子两步前进的序列，然后比较这两个指针的序列值。乌龟和兔子指向相等值的最小值是期望值。
The following [[Python (programming language)|Python]] code shows how this idea may be implemented as an algorithm.
The following Python code shows how this idea may be implemented as an algorithm.
下面的 Python 代码展示了如何将这种思想实现为一种算法。
<syntaxhighlight lang="python">
def floyd(f, x0):
# Main phase of algorithm: finding a repetition x_i = x_2i.
# The hare moves twice as quickly as the tortoise and
# the distance between them increases by 1 at each step.
# Eventually they will both be inside the cycle and then,
# at some point, the distance between them will be
# divisible by the period λ.
tortoise = f(x0) # f(x0) is the element/node next to x0.
hare = f(f(x0))
while tortoise != hare:
tortoise = f(tortoise)
hare = f(f(hare))
# At this point the tortoise position, ν, which is also equal
# to the distance between hare and tortoise, is divisible by
# the period λ. So hare moving in circle one step at a time,
# and tortoise (reset to x0) moving towards the circle, will
# intersect at the beginning of the circle. Because the
# distance between them is constant at 2ν, a multiple of λ,
# they will agree as soon as the tortoise reaches index μ.
<syntaxhighlight lang="python">
def floyd(f, x0):
# Main phase of algorithm: finding a repetition x_i = x_2i.
# The hare moves twice as quickly as the tortoise and
# the distance between them increases by 1 at each step.
# Eventually they will both be inside the cycle and then,
# at some point, the distance between them will be
# divisible by the period λ.
tortoise = f(x0) # f(x0) is the element/node next to x0.
hare = f(f(x0))
while tortoise != hare:
tortoise = f(tortoise)
hare = f(f(hare))
# At this point the tortoise position, ν, which is also equal
# to the distance between hare and tortoise, is divisible by
# the period λ. So hare moving in circle one step at a time,
# and tortoise (reset to x0) moving towards the circle, will
# intersect at the beginning of the circle. Because the
# distance between them is constant at 2ν, a multiple of λ,
# they will agree as soon as the tortoise reaches index μ.
# 算法的主要阶段: 寻找一个重复 x _ i = x _ 2i。# 兔子的速度是乌龟的两倍 # 他们之间的距离每走一步就增加一倍。# 最终它们都在循环中 # 在某个时刻，它们之间的距离 # 可以被周期 λ 整除。Tortoise = f (x0) # f (x0)是 x0旁边的元素/节点。兔子 = f (f (x0))而乌龟！= hare: tortoise = f (tortoise) hare = f (f (hare)) # 此时，乌龟的位置 ν 也等于逐兔棋之间的距离，可以被周期 λ 整除。所以兔子一步一步地在圆里移动，# 和乌龟(重置为 x0)向圆移动，将 # 在圆的开始相交。因为它们之间的 # 距离在2ν 是恒定的，是 λ 的倍数，当乌龟达到指数 μ 时，它们就会一致。
# Find the position μ of first repetition.
mu = 0
tortoise = x0
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare) # Hare and tortoise move at same speed
mu += 1
# Find the length of the shortest cycle starting from x_μ
# The hare moves one step at a time while tortoise is still.
# lam is incremented until λ is found.
lam = 1
hare = f(tortoise)
while tortoise != hare:
hare = f(hare)
lam += 1
return lam, mu
</syntaxhighlight>
# Find the position μ of first repetition.
mu = 0
tortoise = x0
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare) # Hare and tortoise move at same speed
mu += 1
# Find the length of the shortest cycle starting from x_μ
# The hare moves one step at a time while tortoise is still.
# lam is incremented until λ is found.
lam = 1
hare = f(tortoise)
while tortoise != hare:
hare = f(hare)
lam += 1
return lam, mu
</syntaxhighlight>
# 找到第一次重复的位置 μ。Μ = 0乌龟 = x0而乌龟！= hare: tortoise = f (tortoise) hare = f (hare) # 逐兔棋移动速度 μ + = 1 # 从 x _ μ 开始计算最短周期的长度。# lam 是递增的，直到找到 λ。lam = 1
hare = f(tortoise)
while tortoise != hare:
hare = f(hare)
lam += 1
return lam, mu
</syntaxhighlight>
This code only accesses the sequence by storing and copying pointers, function evaluations, and equality tests; therefore, it qualifies as a pointer algorithm. The algorithm uses {{math|''O''(''λ'' + ''μ'')}} operations of these types, and {{math|''O''(1)}} storage space.<ref>{{harvtxt|Joux|2009}}, Section 7.1.1, Floyd's cycle-finding algorithm, pp. 225–226.</ref>
This code only accesses the sequence by storing and copying pointers, function evaluations, and equality tests; therefore, it qualifies as a pointer algorithm. The algorithm uses operations of these types, and storage space., Section 7.1.1, Floyd's cycle-finding algorithm, pp. 225–226.
此代码仅通过存储和复制指针、函数计算和相等性测试来访问序列; 因此，它具有指针算法的资格。该算法使用这些类型的操作和存储空间，第7.1.1节，弗洛伊德的循环寻找算法，pp。225–226.
===Brent's algorithm===
===Brent's algorithm===
===Brent's algorithm===
[[Richard Brent (scientist)|Richard P. Brent]] described an alternative cycle detection algorithm that, like the tortoise and hare algorithm, requires only two pointers into the sequence.<ref name="brent">{{citation|first=R. P.|last=Brent|authorlink=Richard Brent (scientist)|title=An improved Monte Carlo factorization algorithm|journal=[[BIT Numerical Mathematics ]]|volume=20|year=1980|pages=176–184|url=https://maths-people.anu.edu.au/~brent/pd/rpb051i.pdf|doi=10.1007/BF01933190|issue=2|s2cid=17181286}}.</ref> However, it is based on a different principle: searching for the smallest [[power of two]] {{math|2<sup>''i''</sup>}} that is larger than both {{mvar|λ}} and {{mvar|μ}}. For {{math|1=''i'' = 0, 1, 2, ...}}, the algorithm compares {{math|''x''<sub>2<sup>''i''</sup>−1</sub>}} with each subsequent sequence value up to the next power of two, stopping when it finds a match. It has two advantages compared to the tortoise and hare algorithm: it finds the correct length {{mvar|λ}} of the cycle directly, rather than needing to search for it in a subsequent stage, and its steps involve only one evaluation of {{mvar|f}} rather than three.<ref>{{harvtxt|Joux|2009}}, Section 7.1.2, Brent's cycle-finding algorithm, pp. 226–227.</ref>
Richard P. Brent described an alternative cycle detection algorithm that, like the tortoise and hare algorithm, requires only two pointers into the sequence.. However, it is based on a different principle: searching for the smallest power of two that is larger than both and . For , the algorithm compares with each subsequent sequence value up to the next power of two, stopping when it finds a match. It has two advantages compared to the tortoise and hare algorithm: it finds the correct length of the cycle directly, rather than needing to search for it in a subsequent stage, and its steps involve only one evaluation of rather than three., Section 7.1.2, Brent's cycle-finding algorithm, pp. 226–227.
理查德 · P · 布伦特(Richard P. Brent)描述了一种替代循环检测算法，它与乌龟和兔子算法一样，只需要两个指向序列的指针。.然而，它是基于一个不同的原理: 寻找比两者都大的最小二次方和。因为，该算法与每个后续序列值进行比较，直到下一次幂为2，当找到匹配时停止。与乌龟和兔子算法相比，它有两个优点: 它直接找到正确的循环长度，而不需要在后续阶段搜索它，它的步骤只涉及一个评价，而不是三个，第7.1.2节，布伦特循环找到算法，pp。226–227.
The following Python code shows how this technique works in more detail.
<syntaxhighlight lang="python">
def brent(f, x0):
# main phase: search successive powers of two
power = lam = 1
tortoise = x0
hare = f(x0) # f(x0) is the element/node next to x0.
while tortoise != hare:
if power == lam: # time to start a new power of two?
tortoise = hare
power *= 2
lam = 0
hare = f(hare)
lam += 1
The following Python code shows how this technique works in more detail.
<syntaxhighlight lang="python">
def brent(f, x0):
# main phase: search successive powers of two
power = lam = 1
tortoise = x0
hare = f(x0) # f(x0) is the element/node next to x0.
while tortoise != hare:
if power == lam: # time to start a new power of two?
tortoise = hare
power *= 2
lam = 0
hare = f(hare)
lam += 1
下面的 Python 代码更详细地说明了这种技术是如何工作的。主要阶段: 搜索两次幂的连续幂 = lam = 1 tortoise = x0 hare = f (x0) # f (x0)是 x0旁边的元素/节点。而乌龟！= hare: if power = = lam: # time to start a new power of two？tortoise = hare
power *= 2
lam = 0
hare = f(hare)
lam += 1
# Find the position of the first repetition of length λ
tortoise = hare = x0
for i in range(lam):
# range(lam) produces a list with the values 0, 1, ... , lam-1
hare = f(hare)
# The distance between the hare and tortoise is now λ.
# Find the position of the first repetition of length λ
tortoise = hare = x0
for i in range(lam):
# range(lam) produces a list with the values 0, 1, ... , lam-1
hare = f(hare)
# The distance between the hare and tortoise is now λ.
找到第一个重复长度的位置 λ 对于范围 i，tortoise = hare = x0: 范围(lam)生成一个值为0,1，... ，lam-1 hare = f (hare)的列表逐兔棋之间的距离现在是 λ。
# Next, the hare and tortoise move at same speed until they agree
mu = 0
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare)
mu += 1
return lam, mu
</syntaxhighlight>
# Next, the hare and tortoise move at same speed until they agree
mu = 0
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare)
mu += 1
return lam, mu
</syntaxhighlight>
接下来，逐兔棋以同样的速度移动直到他们同意 μ = 0，而乌龟！= 乌龟 = f (乌龟)乌龟 = f (乌龟)乌 + = 1回林，乌
Like the tortoise and hare algorithm, this is a pointer algorithm that uses {{math|''O''(''λ'' + ''μ'')}} tests and function evaluations and {{math|''O''(1)}} storage space. It is not difficult to show that the number of function evaluations can never be higher than for Floyd's algorithm. Brent claims that, on average, his cycle finding algorithm runs around 36% more quickly than Floyd's and that it speeds up the [[Pollard rho algorithm]] by around 24%. He also performs an [[Average-case complexity|average case]] analysis for a randomized version of the algorithm in which the sequence of indices traced by the slower of the two pointers is not the powers of two themselves, but rather a randomized multiple of the powers of two. Although his main intended application was in integer factorization algorithms, Brent also discusses applications in testing pseudorandom number generators.<ref name="brent"/>
Like the tortoise and hare algorithm, this is a pointer algorithm that uses tests and function evaluations and storage space. It is not difficult to show that the number of function evaluations can never be higher than for Floyd's algorithm. Brent claims that, on average, his cycle finding algorithm runs around 36% more quickly than Floyd's and that it speeds up the Pollard rho algorithm by around 24%. He also performs an average case analysis for a randomized version of the algorithm in which the sequence of indices traced by the slower of the two pointers is not the powers of two themselves, but rather a randomized multiple of the powers of two. Although his main intended application was in integer factorization algorithms, Brent also discusses applications in testing pseudorandom number generators.
像龟兔算法一样，这是一个使用测试、函数求值和存储空间的指针算法。不难看出，函数评价的数量永远不会高于弗洛伊德的算法。布伦特声称，平均而言，他的循环寻找算法比弗洛伊德的算法快36% 左右，它使 Pollard rho 算法的速度提高了24% 左右。他还对一个随机版本的算法进行了平均案例分析，在这个算法中，由两个指针中较慢的一个跟踪的指数序列不是两个指针本身的幂，而是两个指针幂的随机倍数。尽管布伦特的主要应用是整数分解算法，但他也讨论了在测试伪随机数生成器方面的应用。
===Gosper's algorithm===
[[Bill Gosper|R. W. Gosper]]'s algorithm<ref name="gosper-impl">{{Cite web |url=http://www.hackersdelight.org/hdcodetxt/loopdet.c.txt |title=Archived copy |access-date=2017-02-08 |archive-url=https://web.archive.org/web/20160414011322/http://hackersdelight.org/hdcodetxt/loopdet.c.txt |archive-date=2016-04-14 |url-status=dead }}</ref><ref>{{Cite web|url=http://www.inwap.com/pdp10/hbaker/hakmem/flows.html|title=Hakmem -- Flows and Iterated Functions -- Draft, Not Yet Proofed}}</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, eg. <math>\mu_l + \lambda \sim \mu_h</math>.
R. W. Gosper's algorithm finds the period \lambda, and the lower and upper bound of the starting point, \mu_l and \mu_u, of the first cycle. The difference between the lower and upper bound is of the same order as the period, eg. \mu_l + \lambda \sim \mu_h.
Gosper 的算法 = = R. W. Gosper 的算法找到第一个周期的周期 λ，以及第一个周期起点的上下界 μ _ l 和 μ _ u。下限和上限之间的差别与周期的顺序相同，例如。Lambda sim mu _ h.
The main feature of Gosper's algorithm is that it never backs up to reevaluate the generator function, and is economical in both space and time. It could be roughly described as a parallel version of Brent's algorithm. While Brent's algorithm gradually increases the gap between the tortoise and hare, Gosper's algorithm uses several tortoises (several previous values are saved), which are roughly exponentially spaced. According to the note in [http://www.inwap.com/pdp10/hbaker/hakmem/flows.html HAKMEM item 132], this algorithm will detect repetition before the third occurrence of any value, eg. the cycle will be iterated at most twice. This note also states that it is sufficient to store <math>\Theta(\log \lambda)</math> previous values; however, the provided implementation<ref name="gosper-impl"/> stores <math>\Theta(\log (\mu + \lambda))</math> values. For example: the function values are 32-bit integers, and it is known a priori that the ''second iteration'' of the cycle ends after at most 2<sup>32</sup> function evaluations since the beginning, viz. <math>\mu + 2\lambda \le 2^{32}</math>. Then it suffices to store 33 32-bit integers.
The main feature of Gosper's algorithm is that it never backs up to reevaluate the generator function, and is economical in both space and time. It could be roughly described as a parallel version of Brent's algorithm. While Brent's algorithm gradually increases the gap between the tortoise and hare, Gosper's algorithm uses several tortoises (several previous values are saved), which are roughly exponentially spaced. According to the note in HAKMEM item 132, this algorithm will detect repetition before the third occurrence of any value, eg. the cycle will be iterated at most twice. This note also states that it is sufficient to store \Theta(\log \lambda) previous values; however, the provided implementation stores \Theta(\log (\mu + \lambda)) values. For example: the function values are 32-bit integers, and it is known a priori that the second iteration of the cycle ends after at most 232 function evaluations since the beginning, viz. \mu + 2\lambda \le 2^{32}. Then it suffices to store 33 32-bit integers.
Gosper 算法的主要特点是不需要重新评估生成器函数，在空间和时间上都很经济。它可以粗略地描述为布伦特算法的一个并行版本。虽然布伦特的算法逐渐增加了乌龟和兔子之间的差距，但戈斯帕的算法使用了几只乌龟(保存了几个以前的值) ，这些乌龟的间隔大致是指数级的。根据 HAKMEM 条目132中的说明，该算法将在任何值的第三次出现之前检测重复，例如。循环最多重复两次。本说明还指出，存储 Θ (log lambda)以前的值就足够了; 但是，提供的实现存储 Θ (log (mu + lambda))值。例如: 函数值是32位整数，并且先验地知道循环的第二次迭代结束于自开始以来最多232次函数求值之后，即。Μ + 2 lambda le 2 ^ {32}.然后它足以存储33个32位整数。
Upon the <math>i</math>-th evaluation of the generator function, the algorithm compares the generated value with <math>O(\log 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>\Theta(\log (\mu + \lambda))</math> values, its space complexity is <math>\Theta(\log (\mu + \lambda))</math>. This is under the usual assumption, present throughout this article, that the size of the function values is constant. Without this assumption, the space complexity is <math>\Omega(\log^2 (\mu + \lambda))</math> since we need at least <math>\mu + \lambda</math> distinct values and thus the size of each value is <math>\Omega(\log (\mu + \lambda))</math>.
Upon the i-th evaluation of the generator function, the algorithm compares the generated value with O(\log i) previous values; observe that i goes up to at least \mu + \lambda and at most \mu + 2\lambda. Therefore, the time complexity of this algorithm is O((\mu + \lambda) \cdot \log (\mu + \lambda)). Since it stores \Theta(\log (\mu + \lambda)) values, its space complexity is \Theta(\log (\mu + \lambda)). This is under the usual assumption, present throughout this article, that the size of the function values is constant. Without this assumption, the space complexity is \Omega(\log^2 (\mu + \lambda)) since we need at least \mu + \lambda distinct values and thus the size of each value is \Omega(\log (\mu + \lambda)).
在对生成器函数进行第 i 次求值时，该算法将生成的值与 O (log i)之前的值进行比较; 观察到 i 至少升至 mu + lambda，至多升至 mu + 2 lambda。因此，该算法的时间复杂度为 O ((mu + lambda)) cdot log (mu + lambda)。因为它存储 Θ (log (mu + lambda))值，所以它的空间复杂度是 Θ (log (mu + lambda))。这是在本文中提出的通常假设下进行的，即函数值的大小是常数。如果没有这个假设，空间复杂度就是 Ω (log ^ 2(mu + lambda)) ，因为我们至少需要 μ + lambda 不同的值，因此每个值的大小就是 Ω (log (mu + lambda))。
===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.
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,. we survey these techniques briefly.
= = = 时间-空间权衡 = = = = 很多作者研究了周期检测技术，比弗洛伊德和布伦特的方法使用更多的内存，但检测周期更快。通常，这些方法存储几个以前计算的序列值，并测试每个新值是否等于以前计算的值之一。为了快速完成这项工作，它们通常使用哈希表或类似的数据结构来存储先前计算的值，因此不是指针算法: 特别是，它们通常不能应用于 Pollard 的 rho 算法。这些方法的不同之处在于它们如何确定要存储的值。继 Nivasch 之后。我们对这些技术进行了简要的调查。
*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|authorlink1=Claus P. Schnorr|first2=Hendrik W.|last2=Lenstra|authorlink2=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|authorlink1=Robert Sedgewick (computer scientist)|first2=Thomas G.|last2=Szymanski|first3=Andrew C.-C.|last3=Yao|authorlink3=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}}.</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|volume=434|publisher=Springer-Verlag|pages=429–434|doi=10.1007/3-540-46885-4_43|doi-access=free}}.</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.
*Brent already describes variations of his technique in which the indices of saved sequence values are powers of a number other than two. By choosing to be a number close to one, and storing the sequence values at indices that are near a sequence of consecutive powers of , a cycle detection algorithm can use a number of function evaluations that is within an arbitrarily small factor of the optimum ...
*Sedgewick, Szymanski, and Yao. provide a method that uses memory cells and requires in the worst case only (\lambda+\mu)(1+cM^{-1/2}) function evaluations, for some constant , which they show to be optimal. The technique involves maintaining a numerical parameter , storing in a table only those positions in the sequence that are multiples of , and clearing the table and doubling 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 might be stored... More simply, 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 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, 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.
* 布伦特已经描述了他的技术的变化，其中保存的序列值的指数是一个数以外的2的幂。通过选择一个接近1的数字，并将序列值存储在接近一系列连续幂的指数中，循环检测算法可以使用一系列函数评估，这些评估在最优因子的任意小范围内...
* Sedgewick，Szymanski，and Yao。提供一种使用内存单元的方法，并且在最坏的情况下只需要(lambda + mu)(1 + cM ^ {-1/2})函数求值，对于某个常数，它们表明是最优的。这种技术包括维护一个数值参数，只在表中存储序列中的那些乘以数的位置，清除表并在存储了太多值时加倍。
* 几位作者已经描述了基于涉及值的标准而不是(如 Sedgewick 等人的方法)在表中存储函数值的区分点方法根据他们的位置。例如，等于零的模数值可能会被存储... ... 更简单地说，Nivasch 相信 D.P.Woodruff 的建议，即存储一个先前看到的值的随机样本，在每一步做出适当的随机选择，使样本保持随机。
* Nivasch 描述了一种算法，它不使用固定数量的内存，但使用的预期内存数量(假设输入函数是随机的)是序列长度的对数。使用此技术，当以后的项没有较小值时，项存储在内存表中。如 Nivasch 所示，使用这种技术的项可以使用堆栈数据结构来维护，并且每个连续的序列值只需要与堆栈顶部进行比较。当找到具有最小值的重复序列元素时，算法终止。对多个堆栈运行相同的算法，使用值的随机排列重新排列每个堆栈中的值，允许类似于以前的算法的时空折衷。但是，由于需要进行比较以确定两个值中哪一个更小，因此即使这种算法的版本只有一个堆栈也不是指针算法。
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|authorlink=Faith Ellen|contribution=Lower bounds for the cycle detection problem|title=Proc. 13th ACM [[Symposium on Theory of Computing]]|year=1981|doi=10.1145/800076.802462|pages=96–105}}.</ref><ref>{{citation|first1=Eric W.|last1=Allender|authorlink1=Eric Allender|first2=Maria M.|last2=Klawe|authorlink2=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>
Any cycle detection algorithm that stores at most values from the input sequence must perform at least (\lambda+\mu)\left(1+\frac{1}{M-1}\right) function evaluations...
任何存储最多输入序列值的循环检测算法必须执行至少(lambda + mu)的左(1 + frac {1}{ M-1}右)函数计算..。
==Applications==
==Applications==
= = 应用 = =
Cycle detection has been used in many applications.
*Determining the cycle length of a [[pseudorandom number generator]] is one measure of its strength. This is the application cited by Knuth in describing Floyd's method.<ref name="knuth"/> Brent<ref name="brent"/> describes the results of testing a [[linear congruential generator]] in this fashion; its period turned out to be significantly smaller than advertised. For more complex generators, the sequence of values in which the cycle is to be found may not represent the output of the generator, but rather its internal state.
*Several [[Number theory|number-theoretic]] algorithms are based on cycle detection, including [[Pollard's rho algorithm]] for integer factorization<ref>{{citation|first=J. M.|last=Pollard|title=A Monte Carlo method for factorization|journal=BIT|volume=15|year=1975|pages=331–334|doi=10.1007/BF01933667|issue=3|s2cid=122775546}}.</ref> and his related [[Pollard's kangaroo algorithm|kangaroo algorithm]] for the [[discrete logarithm]] problem.<ref>{{citation|first=J. M.|last=Pollard|title=Monte Carlo methods for index computation {{math|(mod ''p''}})|journal=[[Mathematics of Computation]]|volume=32|issue=143|year=1978|pages=918–924|doi=10.2307/2006496|publisher=American Mathematical Society|jstor=2006496}}.</ref>
*In [[Cryptography|cryptographic]] applications, the ability to find two distinct values ''x''<sub>μ−-1</sub> and ''x''<sub>λ+μ−-1</sub> mapped by some cryptographic function ƒ to the same value ''x''<sub>μ</sub> may indicate a weakness in ƒ. For instance, Quisquater and Delescaille<ref name="qd"/> apply cycle detection algorithms in the search for a message and a pair of [[Data Encryption Standard]] keys that map that message to the same encrypted value; [[Burt Kaliski|Kaliski]], [[Ron Rivest|Rivest]], and [[Alan Sherman|Sherman]]<ref name="krs">{{citation|first1=Burton S., Jr.|last1=Kaliski|first2=Ronald L.|last2=Rivest|authorlink2=Ron Rivest|first3=Alan T.|last3=Sherman|title=Is the Data Encryption Standard a group? (Results of cycling experiments on DES)|journal=[[Journal of Cryptology]]|volume=1|issue=1|year=1988|pages=3–36|doi=10.1007/BF00206323|s2cid=17224075}}.</ref> also use cycle detection algorithms to attack DES. The technique may also be used to find a [[hash collision|collision]] in a [[cryptographic hash function]].<ref>{{harvtxt|Joux|2009}}, Section 7.5, Collisions in hash functions, pp. 242–245.</ref>
*Cycle detection may be helpful as a way of discovering [[infinite loop]]s in certain types of [[computer program]]s.<ref>{{citation|first=Allen|last=Van Gelder|title=Efficient loop detection in Prolog using the tortoise-and-hare technique|journal=Journal of Logic Programming|volume=4|issue=1|pages=23–31|year=1987|doi=10.1016/0743-1066(87)90020-3|doi-access=free}}.</ref>
*[[Oscillator (cellular automaton)|Periodic configurations]] in [[cellular automaton]] simulations may be found by applying cycle detection algorithms to the sequence of automaton states.<ref name="nivasch"/>
*[[Shape analysis (software)|Shape analysis]] of [[linked list]] data structures is a technique for verifying the correctness of an algorithm using those structures. If a node in the list incorrectly points to an earlier node in the same list, the structure will form a cycle that can be detected by these algorithms.<ref>{{citation|first1=Mikhail|last1=Auguston|first2=Miu Har|last2=Hon|contribution=Assertions for Dynamic Shape Analysis of List Data Structures|pages=37–42|title=AADEBUG '97, Proceedings of the Third International Workshop on Automatic Debugging|series=Linköping Electronic Articles in Computer and Information Science|publisher=[[Linköping University]]|url=http://www.ep.liu.se/ea/cis/1997/009/04/|year=1997}}.</ref> In [[Common Lisp]], the [[S-expression]] printer, under control of the <code>*print-circle*</code> variable, detects circular list structure and prints it compactly.
*Teske<ref name="teske"/> describes applications in [[computational group theory]]: determining the structure of an [[Abelian group]] from a set of its generators. The cryptographic algorithms of Kaliski et al.<ref name="krs"/> may also be viewed as attempting to infer the structure of an unknown group.
*{{harvtxt|Fich|1981}} briefly mentions an application to [[computer simulation]] of [[celestial mechanics]], which she attributes to [[William Kahan]]. In this application, cycle detection in the [[phase space]] of an orbital system may be used to determine whether the system is periodic to within the accuracy of the simulation.<ref name="fich"/>
*In [[Mandelbrot Set]] fractal generation some performance techniques are used to speed up the image generation. One of them is called "period checking", which consists of finding the cycles in a point orbit. This article describes the "[[wikibooks:Fractals/Iterations_in_the_complex_plane/Mandelbrot_set/mandelbrot#Periodicity_checking|period checking]]" technique. You can find another explanation [http://math.bu.edu/DYSYS/FRACGEOM/node1.html#SECTION00010000000000000000 here]. Some cycle detection algorithms have to be implemented in order to implement this technique.
Cycle detection has been used in many applications.
*Determining the cycle length of a pseudorandom number generator is one measure of its strength. This is the application cited by Knuth in describing Floyd's method. Brent describes the results of testing a linear congruential generator in this fashion; its period turned out to be significantly smaller than advertised. For more complex generators, the sequence of values in which the cycle is to be found may not represent the output of the generator, but rather its internal state.
*Several number-theoretic algorithms are based on cycle detection, including Pollard's rho algorithm for integer factorization. and his related kangaroo algorithm for the discrete logarithm problem..
*In cryptographic applications, the ability to find two distinct values xμ−-1 and xλ+μ−-1 mapped by some cryptographic function ƒ to the same value xμ may indicate a weakness in ƒ. For instance, Quisquater and Delescaille apply cycle detection algorithms in the search for a message and a pair of Data Encryption Standard keys that map that message to the same encrypted value; Kaliski, Rivest, and Sherman. also use cycle detection algorithms to attack DES. The technique may also be used to find a collision in a cryptographic hash function., Section 7.5, Collisions in hash functions, pp. 242–245.
*Cycle detection may be helpful as a way of discovering infinite loops in certain types of computer programs..
*Periodic configurations in cellular automaton simulations may be found by applying cycle detection algorithms to the sequence of automaton states.
*Shape analysis of linked list data structures is a technique for verifying the correctness of an algorithm using those structures. If a node in the list incorrectly points to an earlier node in the same list, the structure will form a cycle that can be detected by these algorithms.. In Common Lisp, the S-expression printer, under control of the *print-circle* variable, detects circular list structure and prints it compactly.
*Teske describes applications in computational group theory: determining the structure of an Abelian group from a set of its generators. The cryptographic algorithms of Kaliski et al. may also be viewed as attempting to infer the structure of an unknown group.
* briefly mentions an application to computer simulation of celestial mechanics, which she attributes to William Kahan. In this application, cycle detection in the phase space of an orbital system may be used to determine whether the system is periodic to within the accuracy of the simulation.
*In Mandelbrot Set fractal generation some performance techniques are used to speed up the image generation. One of them is called "period checking", which consists of finding the cycles in a point orbit. This article describes the "period checking" technique. You can find another explanation here. Some cycle detection algorithms have to be implemented in order to implement this technique.
循环检测在许多应用中得到了广泛的应用。
* 确定伪随机数生成器的周期长度是衡量其强度的一项指标。这是克努特在描述弗洛伊德的方法时引用的应用。布伦特用这种方式描述了测试线性同余方法的结果，结果发现它的周期比广告上说的要短得多。对于更复杂的生成器，循环的值序列可能不代表生成器的输出，而是代表其内部状态。
* 一些数论算法基于循环检测，包括 Pollard 的 rho 整数分解算法。以及他相关的袋鼠算法来解决离散对数问题。.
* 在加密应用中，能够找到由某个加密函数 f 映射到相同值 xμ 的两个不同值 xμ-1和 xλ + μ-1，可能表明 f 的弱点。例如，Quisquater 和 Delescaille 应用循环检测算法来搜索一条消息和一对数据加密标准密钥，这些密钥将消息映射到相同的加密值，如 Kaliski、 Riest 和 Sherman。也使用循环检测算法来攻击 DES。该技术还可以用于查找加密哈希函数中的冲突。242–245.
* 循环检测可能有助于在某些类型的计算机程序中发现无限循环。.
* 通过对自动机状态序列应用循环检测算法，可以发现细胞自动机模拟中的周期性配置。
* 对链表数据结构的形状分析是一种利用这些结构验证算法正确性的技术。如果列表中的一个节点不正确地指向同一列表中的一个早期节点，则该结构将形成一个循环，可由这些算法检测到。.在 Common Lisp 中，S 表达式打印机在
* print-Circle
* 变量的控制下，检测循环列表结构并将其打印得非常简洁。
* Teske 描述了计算群论中的应用: 从一组生成元中确定一个阿贝尔群的结构。Kaliski 等人的密码算法。也可以被视为试图推断一个未知群体的结构。
* 简要提到了一份计算机模拟天体力学的申请，她认为是威廉 · 卡汉提出的。在这种应用中，轨道系统相空间中的周期探测可用于确定该系统是否在模拟精度范围内是周期性的。
* 在 Mandelbrot 集分形生成中，使用了一些性能技术来加速图像生成。其中之一称为“周期检查”，即在点轨道上寻找周期。本文描述了“周期检查”技术。你可以在这里找到另一种解释。为了实现这一技术，必须实现一些循环检测算法。
==References==
{{reflist|30em}}
==External links==
*Gabriel Nivasch, [http://www.gabrielnivasch.org/fun/cycle-detection The Cycle Detection Problem and the Stack Algorithm]
*[http://wiki.c2.com/?TortoiseAndHare Tortoise and Hare], Portland Pattern Repository
*[https://web.archive.org/web/20160313063357/http://www.siafoo.net/algorithm/10 Floyd's Cycle Detection Algorithm (The Tortoise and the Hare)]
*[https://web.archive.org/web/20160304043822/http://www.siafoo.net/algorithm/11 Brent's Cycle Detection Algorithm (The Teleporting Turtle)]
*Gabriel Nivasch, The Cycle Detection Problem and the Stack Algorithm
*Tortoise and Hare, Portland Pattern Repository
*Floyd's Cycle Detection Algorithm (The Tortoise and the Hare)
*Brent's Cycle Detection Algorithm (The Teleporting Turtle)
= = 外部链接 = =
* 加布里埃尔 · 尼瓦什，循环检测问题和堆栈算法
* 乌龟和野兔，波特兰模式仓库
* 弗洛伊德的循环检测算法(龟兔赛跑)
* 布伦特的循环检测算法(瞬移海龟)
{{DEFAULTSORT:Cycle Detection}}
[[Category:Fixed points (mathematics)]]
[[Category:Combinatorial algorithms]]
[[Category:Articles with example Python (programming language) code]]
Category:Fixed points (mathematics)
Category:Combinatorial algorithms
Category:Articles with example Python (programming language) code
类别: 固定点(数学)类别: 组合算法类别: 具有示例 Python (编程语言)代码的文章
<noinclude>
<small>This page was moved from [[wikipedia:en:Cycle detection]]. Its edit history can be viewed at [[圈检测/edithistory]]</small></noinclude>
[[Category:待整理页面]]