The Brent algorithm, when also equipped with some post processing
shown on Wikipedia, can determine the start μ of a cycle and
the length λ of a cycle. This is for the linear case of a list.
In general the start and length are not unique, unless one requires
that the start is the minimal index and the length is minimal as well.
Here is an example of two different starts, illustrated
with a rational number:
10/81 = 0.(123456790) /* μ = 0, λ = 9 */
= 0.12345679(02345679) /* μ = 8, λ = 9 */
Derived from the rational numbers 10/81 and 1/7, I found a
mishap in compare/3 for rational trees aka cyclic terms.
I am blaming some effect with Brent algorithm since is the
dominant algorithm in Prolog systems that became popular:
/* SWI-Prolog 9.1.7 and Scryer Prolog 0.9.1-207 */
?- X = X-0-9-7-6-5-4-3-2-1, Y = Y-7-5-8-2-4-1, X @< Y.
true.
?- H = H-9-7-6-5-4-3-2-1-0, Z = H-9-7-6-5-4-3-2-1,
Y = Y-7-5-8-2-4-1, Z @< Y.
false.
Can this be fixed? It might also not directly related to the
Brent algorithm, and more the methods that are used inside
unify for example, with recording some visited terms in the functor.
This methods have a similar ambiguity.