View source for Talk:Cycle detection

{{dyktalk|26 October|2007|entry=...that in [[Cycle detection#Algorithms|Floyd's algorithm]] for '''[[cycle detection]]''', the [[The Tortoise and the Hare|tortoise and hare]] move at very different speeds, but always finish at the same spot?}}
{{WikiProject banner shell|class=B|
{{WikiProject Computer science|importance=low}}
}}

== Other ==

Sorry about the mistake in the image - lambda should be 2 (the number of elements not involved in the cycle). I uploaded (and re-uploaded) a fixed image, but it doesn't seem to have taken effect. I tried emptying my cache, but the old, incorrect image is still there. Also, the new image has labels on the elements. I'll give it a few hours, and if it still hasn't worked I'm re-uploading again. --[[User:Decrypt3|Decrypt3]] 18:38, May 21, 2004 (UTC)

Fixed it by re-uploading under a different name. Any sysops who see this should delete CycleFinding.Dec3.png. --[[User:Decrypt3|Decrypt3]] 12:29, May 22, 2004 (UTC)

== Contradictions in the article ==

The article states that the worst-case performance of the algorithm is λ + μ/2 comparisons. This statement cannot be correct, since in the example where λ=2 and μ=6, λ + μ/2 = 5, but the description of a running of the algorithm states that it finishes in 6 iterations.

The article also states that the slow sequence cannot get more than halfway around the loop without meeting the fast sequence, but in the given example the sequences meet at the second half of the loop.

:Fixed. [[User:BradAustin2|BradAustin2]] 21:55, 11 March 2007 (UTC)


== Reference for the algorithm ==

The article in JACM cited:

:{cite journal|last=Floyd|first=R.W.|authorlink=Robert W. Floyd|title=Non-deterministic Algorithms|journal=J. ACM|pages=pp. 636-644|month=October|year=1967|url=http://doi.acm.org/10.1145/321420.321422}

does in fact contain a cycle-finding algorithm, but it's a backtracking algorithm for finding all cycles in a graph of a bounded size (essentially depth-first search).  It's not the tortoise-and-hare algorithm.  I'm intrigued that a little Googling for citations finds only references to the same JACM paper.  Is there a published source of the original algorithm, or are we all relying on folk-knowledge that this was first published by Floyd?  <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/163.1.125.59|163.1.125.59]] ([[User talk:163.1.125.59|talk]]) 10:56, 16 October 2007 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

Don Knuth's Art of Computer Programming, Vol 2 (Seminumerical Algorithms) attributes the idea to Bob Floyd, and has the algorithm in the exercises.  That dates it to about 1968, but does not give a published reference.[[User:163.1.125.59|163.1.125.59]] 13:38, 16 October 2007 (UTC)

:Apologies for quick revert. You gave no explanations and the reference is indeed  present in many sources.

:Did you see the 1967 paper yourself? If yes, did you read it carefully? May be it is among the passing  remarks or trivially follows from some of the remarks, because the idea itself is quite simple to describe. I remember solving it myself at a student olympiad. And indeed, this reference is given in some books in, e.g., cryptography.

:If you are right, then I would recommend to do the following, it this order (for various reasons, related with works of wikipedia).
:# Write an article about Floyd's algorithm of finding cycles in a directed graph (one of examples in the mentioned 1967 paper)
:#In the current article, mention that a number of sources refer to the 1967 paper. Point out that in fact the paper covears a ''different'' kind of cycle finding algorithm, referring to the wikipedia article
:#Mention the Knuth's "unreferenced reference".

:When I will be in a university library, I will verify the 1967 article myslef. And of course, keep looking for independent confirmation. `'[[user:mikkalai|Míkka]] 15:56, 17 October 2007 (UTC)

::The 1967 article is available as a pdf at the ULR given above, and contains a description of an application of the algorithm already described in [[Depth-first search]] to cycle-finding, although the article is '''about''' a way of presenting such an algorithm as a nondeterministic algorithm rather than about dfs.

:::You didn't read my question carefully. I don't doubt it contains what you say. My question was whether it contains ''anything else'': an idea, a hint, a footnote. For a mathematician I'd expect you be more carful with details. What is more, the article is not "available as a pdf". It is "available if you have a subscription or pay for it" Anyway, I did read the article myself after all and hereby confirm that no, I didn't see any even remote hints about the "turtle and hare" trick nor even about ''detection'' of a cycle. `'[[user:mikkalai|Míkka]] 22:23, 17 October 2007 (UTC)

::::Sorry! I did read the question: what I did was to omit the word ''only'' from my answer.  And I was unaware that the pdf wasn't free because an institutional subscription entirely hides the page calling for payment.[[User:89.243.59.31|89.243.59.31]] 05:59, 18 October 2007 (UTC)

::I suspect that the Art of Computer Programming is the ultimate source for the presentation in [[Floyd's cycle-finding algorithm]], because it uses the symbols λ and μ for the parameters, although confusingly Knuth uses λ where the article uses μ, and μ where the article has λ. 

::I'll ask Don Knuth whether he knows of an earlier published version of tortoise-and-hare when I see him next.[[User:89.243.59.31|89.243.59.31]] 20:01, 17 October 2007 (UTC)

:In the meantime I described the situation in a footnote in the article. Constructive criticism welcome, as always. —[[User:David Eppstein|David Eppstein]] 21:14, 17 October 2007 (UTC)

== Other algorithms ==

Floyd's is not the only algorithm for solving the problem of detecting cycles in a sequence or functional graph. There is also an algorithm of Brent: maintain a single pointer into the sequence, and compare it to the sequence value at the last position that was a power of two. An algorithm of Nivasch [[DOI:10.1016/j.ipl.2004.01.016]] that uses more space but fewer function evaluations, and many other people's algorithms described briefly in Nivasch's paper. I don't think we need separate Wikipedia articles for all of these different techniques, but I think it would be appropriate to have an article that covers the subject more generally, describing both the different techniques and several applications of this problem (loop detection in logic programming, Pollard's rho factorization, cycle detection for pseudorandom number generators, etc). So I suggest we move this article to [[Loop detection]] or [[Cycle detection]] or [[Cycle-finding algorithms]] or something more generically named like that and add descriptions of the other techniques. Any thoughts on this plan? —[[User:David Eppstein|David Eppstein]] 21:39, 17 October 2007 (UTC)
:I agree that it would be a good idea to make an article about the '''problem''', rather than about one particular solution. `'[[user:mikkalai|Míkka]] 22:02, 17 October 2007 (UTC)




While I am at this (not for long), I'd like to say that the description of the algorithm has two major flaws IMO. First, the algorithm must be described in terlm of the most basic model, i.e., in terms of a graph. Second, I fail to uderstand why a [[pseudo-random]] function is used in description. I don't even want to lookm into "[[pseudo-random function]]" article: the phrase "Clearly such a sequence must cycle after at most n iterations of the pseudo-random function, because there are only n possible values for an element." implies that the value of f(i) is ''deterministic'' regardless the call of the function. And the whole discussion is in fact valid for any funcions whose [[range]] belongs to its [[domain]]. Or am I missinig something here? `'[[user:mikkalai|Míkka]] 23:37, 17 October 2007 (UTC)

:I think the point of the pseudo-random function part is not that it be pseudo-random, but that it be a function. You can't use this algorithm for a sequence that is truly random (because it won't cycle), and using it for sequences that depend on more than just the previous term (such as e.g. Fibonacci modulo p) requires some modification. —[[User:David Eppstein|David Eppstein]] 23:46, 17 October 2007 (UTC)

::The ''pseudo-random'' is probably another artefact of the original source for the article being Art of Computer Programming, where the algorithm appears in the context of testing the cycle length of [[Pseudorandom number generator]]s. (The same is true of Richard Brent's article.) The link redirecting to [[pseudorandom function family]] is clearly misleading.[[User:89.243.59.31|89.243.59.31]] 05:59, 18 October 2007 (UTC)


I've 2 questions ? Can we use floyds cycle finding algorithm sequence of values which repeats itself but contains duplicate values .
Fib mod m can have values like 0,1,1,2,3... now hare and tortoise are equal at 1,1 or some other elements. Shouldn't they be unique ? I think we need to find the periodicity using KMP or something alike. Please suggest.

:There's no unambiguous way of determining a cycle in an infinite sequence that may have repetitions: any time you think you have a repetition, it could change to a longer one. For instance, your sequence could begin
::0,1,1,2,3,0,1,1,2,3,0,1,1,2,3,4,0,1,1,2,3,0,1,1,2,3,0,1,1,2,3,4,0,1,1,2,3,0,1,1,2,3,0,1,1,2,3,4,5,...
:KMP would work to find repetitions in finite strings where the whole sequence is known (or to find the repetitions up to a given point in an infinite sequence), as you suggest, but would use far greater amounts of memory than the algorithms described here. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 15:37, 27 February 2009 (UTC)

How is such algorithm called — [https://github.com/xaionaro/documentation/raw/master/openrc/earlyloopdetector/early-loop-detection.pdf early loop detection in OpenRC]? I think it should be added to the article. —[[User:Xaionaro|Xaionaro]] ([[User talk:Xaionaro|talk]]) 11:20, 24 January 2014 (UTC)

== Too much graphical-heavy image ==

The hare - tortoise image is cute, but I think it's too much 'heavy'. A more stylized and lighter image may be better. <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:79.42.205.63|79.42.205.63]] ([[User talk:79.42.205.63|talk]] • [[Special:Contributions/79.42.205.63|contribs]]) </span></small><!-- Template:Unsigned -->

I like it.--[[User:CzarKirk|CzarKirk]] ([[User talk:CzarKirk|talk]]) 03:30, 16 January 2009 (UTC)

==Example code needs fixing==
Currently both the floyd and brent code examples of the algorithm leaves out a critical component, making it nearly useless as is. both algorithms have an undefined function f(someNode) which is explained to simply return the node next to someNode. However in most graphs there isnt a single node adjacent to another, there are several. since f() isnt actually defined it doesnt tell you which of the neighbor nodes should be selected, and clearly just picking any at all wont work (or else the entire graph doesnt get traversed). This should be fixed, or perhaps someone could explain this to me and i can fix it? - [[User:Debeo Morium|Debeo Morium]]: to be morally bound ([[User Talk:Debeo Morium|Talk]] | [[Special:Contributions/Debeo Morium|Contribs]]) 04:55, 21 April 2010 (UTC)
:You seem to have mistaken this for an article about finding cycles in arbitrary graphs. For that, you probably want [[depth first search]] or something like that. This is about finding cycles in sequences defined by repeatedly calling a function. ''f'' is an input to the algorithm, and (together with the initial value) defines the sequence in which a cycle is to be found. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 05:06, 21 April 2010 (UTC)

== Cycle detection in computer science ==

In computer science, cycle detection is the problem of detecting whether a [[Graph]] has any paths that begin and end in the same vertex. I think there should be a subsection about this, or a link to another page that talks about this problem. --[[User:Erel Segal|Erel Segal]] ([[User talk:Erel Segal|talk]]) 10:09, 3 January 2011 (UTC)
:I think the "in mathematics" of our existing lede is inaccurate: the subject of the current article is computer science, just as the different subject you discuss is. If you think cycle detection in graphs is notable enough for its own article, you're welcome to write [[cycle detection (graph theory)]] and we can add a [[WP:HATNOTE|hatnote]] linking to it from this one. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 17:36, 3 January 2011 (UTC)

::I’m thinking of starting a section under something like [[Cycle (graph theory)#Cycle detection]]. [[User:Vadmium|Vadmium]] ([[User talk:Vadmium|talk]]) 10:45, 13 September 2011 (UTC).
:::Please see [[WP:NOTDICT]]. If it's not about the same problem, it should not be in the same article. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 15:39, 13 September 2011 (UTC)

::Can you elaborate? Are you saying that [[#Cycle detection in computer science]] and [[#Cycle detection in directed graphs]] are not closely enough related to the topic of [[Cycle (graph theory)]] to be mentioned in that article? My main problem was that there is bugger-all information relating cycles in directed graphs to things like [[topological sorting]], [[strongly connected component]]s, [[back edge]]s. See also [[Talk:Cycle (graph theory)#Algorithms for cycle detection in graph theory]]. [[User:Vadmium|Vadmium]] ([[User talk:Vadmium|talk]]) 02:00, 14 September 2011 (UTC).
:::Yes. I believe that the problem of finding cycles in a function or sequence (what this article is about) is very different from the problem of finding cycles in a digraph (what you seem to be talking about). They are different problems with different types of inputs, different types of outputs, different styles of analysis, and different algorithms used to solve them. I believe that it would be more confusing than helpful to conflate them. With a function or sequence input over a finite domain, one knows that cycles are always going to exist, there is a unique cycle that can be reached from any starting value, and the goal is to find that cycle using time and space much smaller than the domain of the function. The input is not a graph; it is a single starting value together with a black box for generating the value of a function. Instead, for finding cycles in digraphs, one does not generally know whether or not cycles exist, the whole digraph is given as input so there's no point in spending less than linear time, there are multiple different outgoing edges from each vertex, there can in generally be exponentially cycles, and there's no clear definition of "the cycle" that you want to find. I think you would be much better off discussing the cycle finding problem for digraphs in connection with either [[topological sorting]] or [[strongly connected component]]s — a digraph either has a topological sort or a cycle, so finding a cycle when topological sorting fails can be a useful sanity check, and the strongly connected components are exactly the sets of vertices that are part of a (not necessarily simple) cycle. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 04:09, 14 September 2011 (UTC)

::Okay, thanks for explaining. I think I misunderstood and perhaps my original comment wasn’t clear. I meant to suggest that ''another'' existing article, [[Cycle (graph theory)]], should be the place for this graph theory problem. The reason it’s all over this talk page of the iterated functions article is probably because the title ''Cycle detection'' is ambiguous without further explanation, and some graph theory pages link to it.
:: Anyway, I’ve created my section (in a different article) and added a hatnote for it. [[User:Vadmium|Vadmium]] ([[User talk:Vadmium|talk]]) 06:06, 14 September 2011 (UTC).
:::Oh, ok. Sorry for misunderstanding your intentions. Yes, the graph theoretic cycle article seems like a good place to at least mention this topic. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 06:10, 14 September 2011 (UTC)

== Cycle detection in directed graphs ==

I agree with Erel Segal.  I think this article, "cycle detection", should define cycle detection as the more general detection of cycles in a directed graph.  The special case dealt with here (functional case, where a given node/value has a single successor) deserves special attention, but as a special case, not as the full "cycle detection" problem.  

I was searching for incremental algorithms for the graph theoretic cycle detection -- i.e., where you've identified all cycles in a huge network, then one link is changed and you need to adjust the cycle identification.  Is it possible to do this more efficiently than a full reprocessing of the full network?  I don't know the answer (yet), but it would have been nice for me if the article might have addressed this.  <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Ldc|Ldc]] ([[User talk:Ldc|talk]] • [[Special:Contributions/Ldc|contribs]]) 22:29, 10 August 2011 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

== Any speeds of Hare and Tortoise? ==

Does it have to be 1x and 2x or any numbers will do? Should the numbers not be co-prime? What about 2x and 8x or 21x and 55x? [[Special:Contributions/117.198.122.24|117.198.122.24]] ([[User talk:117.198.122.24|talk]]) 07:38, 26 October 2012 (UTC)

:They need to be coprime, and the larger they are the more steps you might have to take until finding the loop. So 1 and 2 are the best choice. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 15:14, 26 October 2012 (UTC)

:: Why co-prime? What difference does it make? [[Special:Contributions/117.198.124.222|117.198.124.222]] ([[User talk:117.198.124.222|talk]]) 06:38, 28 October 2012 (UTC)

:: I'd like to note, for any future reader of this discussion, that the respective speeds of tortoise and hare don't need to be coprime; they only need to be non-zero and distinct. Let <math>s_T, s_H \in \mathbb{N}, \mathrm{s.t.}\ s_T \le s_H,</math> denote the speeds of the tortoise and hare respectively; let <math>\Delta = s_H-s_T</math>. To find a solution for any <math>\mu \geq 0</math> and <math>\lambda > 0</math>, the necessary condition imposed on <math>s_T</math> and <math>s_H</math> is that there exist <math>k, l \in \mathbb{N^{+}}</math>, such that '''(a)''' <math>k \cdot \Delta = l \cdot \lambda</math>, and '''(b)''' <math>k \cdot s_T \geq \mu</math>.

::The reasoning is this: {{Ordered list |list-style-type=lower-alpha

|In each step, the mutual distance of tortoise and hare increases by the difference of their speeds <math>\Delta</math>, so after <math>k</math> steps, their distance is <math>k \cdot \Delta</math>. We want this distance to be a positive multiple of <math>\lambda</math>: if their distance is a positive multiple of <math>\lambda</math> and they both have the same value, we've found the cycle. It's necessary to note that the multiple must be positive and not zero, because if it's zero, they are at the same position in the sequence and thus ''always'' have the same value. In such case, we obviously cannot find a cycle. This is why we must require that both <math>k</math> and <math>\Delta</math> are non-zero; the latter implying that <math>s_T</math> and <math>s_H</math> are distinct. From here on, assume <math>\Delta \neq 0</math>.

|We must assure that after the <math>k^\mathrm{th}</math> step, both tortoise and hare are inside the cycle. Hence the requirement <math>k \cdot s_T \geq \mu</math>, which ensures that after the <math>k^\mathrm{th}</math> step, the tortoise (and thus the hare as well) has entered the cycle. Note that <math>k</math> can be any positive natural number, and therefore any positive multiple of <math>\lambda</math>; let <math>k_\lambda</math> denote any such positive multiple of <math>\lambda</math>. For each <math>k_\lambda</math>, <math>k_\lambda \cdot \Delta</math> is also a positive multiple of <math>\lambda</math>, viz. <math>\exist l \in \mathbb{N^{+}}: k_\lambda \cdot \Delta = l \cdot \lambda</math>. In other words, any <math>k_\lambda</math> can satisfy equation (a). Now let's assume <math>s_T = 0</math>; then the equation (b) <math>k_\lambda \cdot s_T \geq \mu</math> implies <math>\mu = 0</math>. But since we want to allow any <math>\mu \geq 0</math>, we must require <math>s_T \ne 0</math> and thus, since <math>s_T</math> cannot be negative, <math>s_T > 0</math>. There are infinitely many <math>k_\lambda</math>, and assuming <math>s_T > 0</math>, there are also infinitely many those <math>k_\lambda</math>, for which <math>k_\lambda \cdot s_T \geq \mu</math>. In other words, if the tortoise is moving at a non-zero speed, it would eventually enter the cycle and synchronize with the hare, no matter how large <math>\mu</math> or <math>\lambda</math> or <math>s_H</math> is.
}}

::We can pick any <math>s_T</math> and <math>s_H</math>, as long as they fulfill the above conditions, namely <math>s_T \ne s_H</math> and <math>s_T > 0</math>, or simply <math>0 < s_T < s_H</math>. Whether they are coprime or not does not matter. --[[Special:Contributions/84.245.121.75|84.245.121.75]] ([[User talk:84.245.121.75|talk]]) 09:17, 3 August 2020 (UTC)

== Where do the Hare and Tortoise meet? ==

I can't seem to understand why the T and H should meet at the node, k nodes before entry point, whenever the length of the list excluding (before) the loop is k? Does this only work when the speeds are x and 2x or all the time? [[Special:Contributions/117.198.124.222|117.198.124.222]] ([[User talk:117.198.124.222|talk]]) 06:39, 28 October 2012 (UTC)
:At each step the hare gets one position farther ahead of the tortoise, because it is faster by one unit. So after k steps (when the tortoise enters the loop) the hare is k positions ahead, or equivalently L-k steps positions behind, where L is the length of the loop. And after L-k more steps, the hare has caught up to the tortoise again. At this time the tortoise will have moved L-k units past where it entered the loop; that is, k nodes before the entry point.—[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 07:19, 28 October 2012 (UTC)
::What if the speed of the tortoise and hare are x and y respectively? and the nodes before the loop is k and nodes in the loop is L?[[Special:Contributions/117.198.136.11|117.198.136.11]] ([[User talk:117.198.136.11|talk]]) 06:30, 30 October 2012 (UTC)

== Wrong equation ==

x_i = x_i + kλ cannot be true unless kλ=0. I assume it's supposed to be x_(i+1) = x_i + kλ  <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/208.54.80.171|208.54.80.171]] ([[User talk:208.54.80.171|talk]]) 23:31, 9 December 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
:Yes, that is the wrong equation. It is so wrong that it is not even in the article. Instead, what we have is x_i = x_{i+kλ}, which is not so difficult to satisfy. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 23:37, 9 December 2012 (UTC)

== Mistake in Python floyd code ==

It seems like the second loop might never end. Both Tortoise and Hare advance at the same speed. What's going on there?  <small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/31.154.17.58|31.154.17.58]] ([[User talk:31.154.17.58|talk]]) 14:28, 8 May 2016 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
:Try working through a few examples. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 17:57, 8 May 2016 (UTC)
::I tried to run an example with the following directed graph: 0 -> 1 -> 2 -> 3 -> 1. Here: ''&lambda;'' {{=}} 3 and ''&mu;'' {{=}} 1.
::Existing the first while loop, I have parameters ''power''{{=}}2, ''lam''{{=}}1.
::This means that after the for loop with ''range(lam)'', the distance between hare and tortoise is 2, and not ''&lambda;'' {{=}} 3.
::Link to an image of the execution I wrote using my iPad: https://www.dropbox.com/s/gv28mk695pjig8b/execution-python-code-brent-algorithm-section-1.png?dl=0
::I cannot find the mistake in my execution. Are you sure the algorithm is correct? [[User:M12ats 87|M12ats 87]] ([[User talk:M12ats 87|talk]]) 13:04, 20 July 2022 (UTC)

== Mistake in Brent's article ==
LCG of TI calculators is ok, because they have more than 32 bits of precision, Brent hit integer overflow in his own program rather than mistake in LCG  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/94.244.46.42|94.244.46.42]] ([[User talk:94.244.46.42#top|talk]]) 12:16, 14 February 2021 (UTC)</small> <!--Autosigned by SineBot-->


== Mistake in Python floyd code 2 ==
I tried to run an example ([1]) with the following directed graph: 0 → 1 → 2 → 3 → 1. Here: ''&lambda;'' {{=}} 3 and ''&mu;'' {{=}} 1.

Exiting the first while loop, I have parameters ''power''{{=}}2, ''lam''{{=}}1.
This means that after the for loop with ''range(lam)'', the distance between hare and tortoise is 2, and not ''&lambda;'' {{=}} 3.

I cannot find the mistake in my execution. Are you sure the algorithm is correct? 

'''Resources:'''

[1] Link to an image of the execution I wrote using my iPad: https://www.dropbox.com/s/gv28mk695pjig8b/execution-python-code-brent-algorithm-section-1.png?dl=0

[[User:M12ats 87|M12ats 87]] ([[User talk:M12ats 87|talk]]) 21:45, 10 August 2022 (UTC)

:I found my mistake:
:In an iteration where ''lam'' (which stands for lambda, i.e., ''&#x3BB;'') is zeroed, we still do ''lam += 1'' at the end of the iteration. Thus, we never have ''lam = 0'' at the end of an iteration.
:With that in mind, illustration 2 in my execution image shows the states of variables after the first iteration, and I have ''lam = 0''. This is wrong. After fixing this, the execution is okay, and we get the correct parameters.
:Two more points:
:1. The headline for my question is incorrect: My illustration represents an execution of Brent's algorithm, not Floyd's, because only Brent's algorithm has a variable named ''power''.
:2. The illustration I used is confusing. Using a table where each row represents variable state after an iteration and columns represent variable states is more comfortable. For positions of pointers, I flat the linked list and also put it in a column. Example: https://www.dropbox.com/s/ni5s3j9keuleqai/execution-python-code-brent-algorithm_version2_trimmed.png?dl=0 [[User:M12ats 87|M12ats 87]] ([[User talk:M12ats 87|talk]]) 13:58, 21 October 2022 (UTC)

== Possible typo in code comment ==

In code we can see
      Because the
    # distance between them is constant at 2ν, a multiple of λ,
    # they will agree as soon as the tortoise reaches index μ.

What is 2ν? Is it node "ν", where there two in-edge, or something else? [[User:Tookser|Tookser]] ([[User talk:Tookser|talk]]) 10:50, 24 March 2024 (UTC)

== Edit, revert, discuss. ==

{{Ping|David Eppstein}} In [[Special:Diff/1261289693|your revert]]'s edit comment, you write "Repetitions are not necessarily associated with cycles."  Er, ''what''?  Remember, this is in the context of a sequence defined by a recurrence {{math|1=''x''<sub>''i''+1</sub> = ''f''(''x<sub>i</sub>'')}}.  So each {{mvar|x<sub>i</sub>}} defines the entire sequence from that point onwards, and repetitions absolutely ''are'' associated with cycles.  The very first repetition demarcates the first cycle of an infinite number of following cycles.

All of these algorithms are "repetition detection" algorithms: They find {{mvar|i}} and {{mvar|j}} such that {{math |1=''x<sub>i</sub>'' = ''x<sub>j</sub>''}}, and then work to narrow down the period and start point.

The associative array (which, for small enough sets {{mvar|S}} can be just an array) is a completely standard technique for solving this.  If you're looking for the period of a 16-bit function, just create an array and fire away.  For a 32-bit function, random access to a 16 GB array (of 32-bit values; there are compression techniques) is slow enough that Brent's algorithm is likely to beat it, unless the {{mvar|f}} function is particularly expensive.

I appreciate the review, but unless I'm misunderstanding your edit comment, it's based on a false premise. [[Special:Contributions/97.102.205.224|97.102.205.224]] ([[User talk:97.102.205.224|talk]]) 12:25, 5 December 2024 (UTC)

:I was assuming you were computing f(1), f(2), f(3), etc, and finding the first repeated value. If you really mean f(1), f(f(1)), f(f(f(1))), etc., you need to explain that much more clearly. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 18:28, 5 December 2024 (UTC)

::{{ping|David Eppstein}} To clarify, ''I'' didn't explain it because that's literally the second paragraph of the lead:
:::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
::::<math> x_0,\ x_1=f(x_0),\ x_2=f(x_1),\ \dots,\ x_i=f(x_{i-1}),\ \dots</math>
:::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 {{mvar|x<sub>i</sub>}} to {{math|''x''<sub>''j'' &minus; 1</sub>}}. Cycle detection is the problem of finding {{mvar|i}} and {{mvar|j}}, given {{mvar|f}} and {{math|''x''<sub>0</sub>}}.
:: It's stated again in the first paragraph of the first {{alink|Example}} section ("If one starts from {{math|1=''x''<sub>0</sub> = 2}} and repeatedly applies {{mvar|f}}") and the first paragraph of the second {{alink|Definitions}} section ("For any {{math|''i'' > 0}}, let {{math|1=''x<sub>i</sub>'' = ''f''(''x''<sub>''i'' &minus; 1</sub>)}}.")
:: I don't consider the third section's lack of a fourth repetition of this fact a problem, so I didn't fix it as part of my edit.  We can discuss it if you like, but it's not something I changed in the edit, so I don't think it bears on whether the edit improved the article or not.
:: One significant problem with my edit is that I deleted the mention of "pointer algorithm" (which should be wikilinked: [[pointer algorithm]]); I was going to put that back when I ran into your mostly-revert and stopped to discuss it. [[Special:Contributions/97.102.205.224|97.102.205.224]] ([[User talk:97.102.205.224|talk]]) 21:57, 5 December 2024 (UTC)
:::Repeatedly applying f, in the statement of what we're trying to find, is different from repeatedly applying f as part of an algorithm that solves the problem. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 23:15, 5 December 2024 (UTC)
::::{{ping|David Eppstein}} Applying {{mvar|f}} is not part of the algorithm that solves the problem.  The algorithm only needs access ''somehow'' to the sequence {{mvar|x<sub>i</sub>}}.  As I said in my edit, one common way to achieve this is to invoke a subroutine to compute {{mvar|f}}.  But this is just generating the problem, not finding the solution.
:::: Given that {{mvar|f}} maps {{mvar|S}} into {{mvar|S}}, and 1 need not be a member of {{mvar|S}}, {{math|''f''(1)}} is not even well-defined.  At the beginning, we only know one element of {{mvar|S}}, namely {{math|''x''<sub>0</sub>}}.  After he first step, we also know {{math|''x''<sub>1</sub>}}.  The only new computation we can perform is {{math|''f''(''x''<sub>1</sub>)}}.  And so on.
::::(Just because we can ''represent'' a value in {{mvar|S}} doesn't mean we can ''construct'' one.  For example, the values might be points on an elliptic curve, where the {{mvar|x}} and {{mvar|y}} coordinates must satisify the curve's equation.)
::::It seems clear that your deletions were, indeed, based on false premises, and any remaining disagreement is about possibly confusing wording.  If we need to edit the text to avoid a misleading implication of that premise, that's easiest to do from the edited baseline.  So I'll revert them and we can proceed to improve it from there.
::::I don't mind using a different word than "repeatedly" if there's another that works better.  The problem is that "recurrently" is awkwardly unfamiliar, and "recursively" is correct mathematically but doesn't meet the computer science definition and so would almost certainly confuse readers.  Is there some rephrasing that would work?
::::[[Special:Contributions/97.102.205.224|97.102.205.224]] ([[User talk:97.102.205.224|talk]]) 00:15, 6 December 2024 (UTC)
:::: I [[Special:Diff/1261452378|added an additional paragraph]] to {{alink|Computer representation}} about practical implementation of the recurrence function {{mvar|f}} which is phrased to include yet another description of the sequence's definition.  Hopefully this addresses the concerns. [[Special:Contributions/97.102.205.224|97.102.205.224]] ([[User talk:97.102.205.224|talk]]) 05:26, 6 December 2024 (UTC)

== Brent Python code buggy? ==

    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)

How is this ever going to halt? Looks to me like those code snippets by highly qualified Indian "IT Experts" that flood the web nowdays... [[Special:Contributions/109.43.115.238|109.43.115.238]] ([[User talk:109.43.115.238|talk]]) 07:33, 24 February 2025 (UTC)

:That part of the algorithm occurs after the length of the cycle is known, and the hare starts that many steps ahead of the tortoise, so that they will become equal exactly when the tortoise reaches the start of the cycle. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 08:25, 24 February 2025 (UTC)