Cycle detection: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
(→{{header|Scala}}: add functional version) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
(24 intermediate revisions by 14 users not shown) | |||
Line 1:
{{
;Task:
Line 33:
=={{header|11l}}==
{{trans|D}}
<
print(‘Cycle length = ’len)
print(‘Start index = ’start)
V i = x0
L 1..start
i = f(i)
V cycle = [0] * len
L 0.<len
cycle[L.index] = i
i = f(i)
print(‘Cycle: ’, end' ‘’)
print(cycle)
F brent(f, x0)
Int cycle_length
V hare = x0
Line 59 ⟶ 72:
print_result(x0, f, cycle_length, cycle_start)
brent(i -> (i * i + 1) % 255, 3)</syntaxhighlight>
{{out}}
<pre>
Line 79:
Cycle: [101, 2, 5, 26, 167, 95]
</pre>
=={{header|8086 Assembly}}==
<syntaxhighlight lang="asm"> cpu 8086
org 100h
section .text
mov ax,3 ; Print the first 20 values in the sequence
mov bx,f
xor cx,cx
mov dx,20
call seq
mov ax,3 ; Use Brent's algorithm to find the cycle
mov bx,f
call brent
mov bp,ax ; BP = start of cycle
mov di,dx ; DI = length of cycle
mov dx,nl ; Print a newline
call prstr
mov dx,len ; Print "Length: "
call prstr
mov ax,di ; Print the length
call prnum
mov dx,ix ; Print "Index: "
call prstr
mov ax,bp ; Print the index
call prnum
mov dx,nl ; Print another newline
call prstr
mov ax,3 ; Print the cycle
mov bx,f
mov cx,bp
mov dx,di
jmp seq
;;; Brent's algorithm
;;; Input: AX = x0, BX = address of function
;;; Output: AX = mu, DX = lambda, CX, SI, BP destroyed
;;; The routine in BX must preserve BX, CX, DX, SI, BP
brent: mov bp,ax ; BP = x0
mov cx,ax ; CX = tortoise
xor dx,dx ; DX = lambda
mov si,1 ; SI = power
.lam: call bx ; Apply function (AX = hare)
inc dx ; Lambda += 1
cmp ax,cx ; Done yet?
je .mu
cmp dx,si ; Time to start a new power of two?
jne .lam
mov cx,ax ; Tortoise = hare
shl si,1 ; power *= 2
xor dx,dx ; lambda = 0
jmp .lam
.mu: mov ax,bp ; Find position of first repetition
mov cx,dx ; CX = lambda
.apply: call bx
loop .apply
mov cx,bp ; CX = tortoise
xor si,si ; SI = mu
.lmu: cmp ax,cx ; Done yet?
je .done
call bx ; hare = f(hare)
xchg ax,cx ; tortoise = f(tortoise)
call bx
xchg ax,cx
inc si
jmp .lmu
.done: mov ax,si
ret
;;; Function to use
;;; AX = (AX*AX+1) mod 255
f: mul al ; AX = AL*AL (we know anything mod 255 is <256)
inc ax ; + 1
div byte [fdsor] ; This is faster than freeing up a byte register
xchg al,ah ; Remainder into AL
xor ah,ah ; Pad to 16 bits
ret
;;; -- Utility routines --
;;; Print decimal value of AL. Destroys AX, DX.
prnum: mov dx,nbuf ; Number output buffer
xchg bx,dx
.dgt: aam ; Extract digit
add al,'0' ; Make ASCII digit
dec bx
mov [bx],al ; Store in buffer
xchg ah,al ; Continue with rest of digits
test al,al ; As long as there are digits
jnz .dgt
xchg bx,dx ; Put buffer pointer back in DX
prstr: mov ah,9 ; Print using MS-DOS call.
int 21h
ret
;;; Print DX values in sequence x, f(x), f(f(x))... starting at CX.
;;; AX = x0, BX = function. AX, CX, DX, SI destroyed.
seq: test cx,cx ; CX = 0?
jz .print
.skip: call bx ; Otherwise skip CX numbers
loop .skip
.print: mov cx,dx ; Amount of numbers to print
.loop: mov si,ax ; Keep a copy of AX (print routine trashes it)
call prnum
mov ax,si ; Restore x
call bx ; Find the next value
loop .loop
ret
section .data
fdsor: db 255 ; This 255 is used for the modulus calculation
db '...' ; Buffer for byte-sized numeric output
nbuf: db ' $'
ix: db 'Index: $'
len: db 'Length: $'
nl: db 13,10,'$'</syntaxhighlight>
{{out}}
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95
Length: 6 Index: 2
101 2 5 26 167 95 </pre>
=={{header|Ada}}==
This implementation is split across three files. The first is the specification of a generic package:
<syntaxhighlight lang="ada">
generic
type Element_Type is private;
package Brent is
type Brent_Function is access function (X : Element_Type) return Element_Type;
procedure Brent(F : Brent_Function; X0 : Element_Type; Lambda : out Integer; Mu : out Integer);
end Brent;
</syntaxhighlight>
The second is the body of the generic package:
<syntaxhighlight lang="ada">
package body Brent is
procedure Brent (F : Brent_Function; X0 : Element_Type; Lambda : out Integer; Mu : out Integer) is
Power : Integer := 1;
Tortoise : Element_Type := X0;
Hare : Element_Type := F(X0);
begin
Lambda := 1;
Mu := 0;
while Tortoise /= Hare loop
if Power = Lambda then
Tortoise := Hare;
Power := Power * 2;
Lambda := 0;
end if;
Hare := F(Hare);
Lambda := Lambda + 1;
end loop;
Tortoise := X0;
Hare := X0;
for I in 0..(Lambda-1) loop
Hare := F(Hare);
end loop;
while Hare /= Tortoise loop
Tortoise := F(Tortoise);
Hare := F(Hare);
Mu := Mu + 1;
end loop;
end Brent;
end Brent;
</syntaxhighlight>
By using a generic package, this implementation can be made to work for any unary function, not just integers. As a demonstration two instances of the test function are created and two instances of the generic package. These are produced inside the main procedure:
<syntaxhighlight lang="ada">
with Brent;
with Text_Io;
use Text_Io;
procedure Main is
package Integer_Brent is new Brent(Element_Type => Integer);
use Integer_Brent;
function F (X : Integer) return Integer is
((X * X + 1) mod 255);
type Mod255 is mod 255;
package Mod255_Brent is new Brent(Element_Type => Mod255);
function F255 (X : Mod255) return Mod255 is
(X * X + 1);
lambda : Integer;
Mu : Integer;
X : Integer := 3;
begin
for I in 1..41 loop
Put(Integer'Image(X));
if I < 41 then
Put(",");
end if;
X := F(X);
end loop;
New_Line;
Integer_Brent.Brent(F'Access, 3, Lambda, Mu);
Put_Line("Cycle Length: " & Integer'Image(Lambda));
Put_Line("Start Index : " & Integer'Image(Mu));
Mod255_Brent.Brent(F255'Access, 3, Lambda, Mu);
Put_Line("Cycle Length: " & Integer'Image(Lambda));
Put_Line("Start Index : " & Integer'Image(Mu));
Put("Cycle : ");
X := 3;
for I in 0..(Mu + Lambda) loop
if Mu <= I and I < (Lambda + Mu) then
Put(Integer'Image(X));
end if;
X := F(X);
end loop;
end Main;
</syntaxhighlight>
{{out}}
<pre> 3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5
Cycle Length: 6
Start Index : 2
Cycle Length: 6
Start Index : 2
Cycle : 101 2 5 26 167 95</pre>
=={{header|APL}}==
{{works with|Dyalog APL}}
<syntaxhighlight lang="apl">brent←{
f←⍺⍺
lam←⊃{
l p t h←⍵
p=l: 1 (p×2) h (f h) ⋄ (l+1) p t (f h)
}⍣{=/2↓⍺} ⊢ 1 1 ⍵ (f ⍵)
mu←⊃{
(⊃⍵+1),f¨1↓⍵
}⍣{=/1↓⍺} ⊢ 0 ⍵ (f⍣lam⊢⍵)
mu lam
}
task←{
seq←{f←⍺⍺ ⋄ (⊃⍺)↓{⍵,f⊃⌽⍵}⍣(1-⍨+/⍺)⊢⍵}
⎕←0 20 ⍺⍺ seq ⍵ ⍝ First 20 elements
⎕←(↑'Index' 'Length'),⍺⍺ brent ⍵ ⍝ Index and length of cycle
⎕←(⍺⍺ brent ⍺⍺ seq⊢)⍵ ⍝ Cycle
}
(255 | 1 + ⊢×⊢) task 3</syntaxhighlight>
{{out}}
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95
Index 2
Length 6
101 2 5 26 167 95</pre>
=={{header|BCPL}}==
<syntaxhighlight lang="bcpl">get "libhdr"
// Brent's algorithm. 'fn' is a function pointer,
// 'lam' and 'mu' are output pointers.
let brent(fn, x0, lam, mu) be
$( let power, tort, hare = 1, x0, fn(x0)
!lam := 1
until tort = hare do
$( if power = !lam then
$( tort := hare
power := power * 2
!lam := 0
$)
hare := fn(hare)
!lam := !lam + 1
$)
tort := x0
hare := x0
for i = 1 to !lam do
hare := fn(hare)
!mu := 0
until tort = hare do
$( tort := fn(tort)
hare := fn(hare)
!mu := !mu + 1
$)
$)
// Print fn^m(x0) to fn^n(x0)
let printRange(fn, x0, m, n) be
$( for i = 0 to n-1 do
$( if m<=i then writef("%N ", x0)
x0 := fn(x0)
$)
wrch('*N')
$)
let start() be
$( let lam, mu = 0, 0
// the function to find a cycle in
let f(x) = (x*x + 1) rem 255
// print the first 20 values
printRange(f, 3, 0, 20)
// find the cycle
brent(f, 3, @lam, @mu)
writef("Length: %N*NIndex: %N*N", lam, mu)
// print the cycle
printRange(f, 3, mu, mu+lam)
$)</syntaxhighlight>
{{out}}
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95
Length: 6
Index: 2
101 2 5 26 167 95</pre>
=={{header|BQN}}==
<syntaxhighlight lang="bqn">_Brent← {F _𝕣 x0:
p←l←1
(I ← {p=l?
l↩1 ⋄ p×↩2 ⋄ 𝕩I𝕩 ;
l+↩1 ⋄ 𝕨I𝕩
}⍟≠⟜F) x0
m←0
{m+↩1 ⋄ 𝕨𝕊⍟≠○F𝕩}⟜(F⍟l) x0
l‿m‿(F⍟(m+↕l)x0)
}</syntaxhighlight>
{{out|Example use}}
<pre> (255|1+ט)_Brent 3
⟨ 6 2 ⟨ 101 2 5 26 167 95 ⟩ ⟩</pre>
=={{header|C}}==
{{trans|Modula-2}}
<
#include <stdlib.h>
Line 160 ⟶ 472:
return 0;
}</
{{out}}
<pre>[3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5]
Line 167 ⟶ 479:
Cycle = [101, 2, 5, 26, 167, 95]</pre>
=={{header|C_sharp|C#
This solution uses generics, so may find cycles of any type of data, not just integers.
<
// First file: Cycles.cs
Line 266 ⟶ 578:
}
</syntaxhighlight>
=={{header|C++}}==
<
int val;
ListNode *next;
Line 305 ⟶ 617:
}
}
}</
=={{header|CLU}}==
<syntaxhighlight lang="clu">% Find a cycle in f starting at x0 using Brent's algorithm
brent = proc [T: type] (f: proctype (T) returns (T), x0: T)
returns (int,int)
where T has equal: proctype (T,T) returns (bool)
pow: int := 1
lam: int := 1
tort: T := x0
hare: T := f(x0)
while tort ~= hare do
if pow = lam then
tort := hare
pow := pow * 2
lam := 0
end
hare := f(hare)
lam := lam + 1
end
tort := x0
hare := x0
for i: int in int$from_to(1,lam) do
hare := f(hare)
end
mu: int := 0
while tort ~= hare do
tort := f(tort)
hare := f(hare)
mu := mu + 1
end
return(lam, mu)
end brent
% Iterate over a function starting at x0 for N steps,
% starting at a given index
iterfunc = iter [T: type] (f: proctype (T) returns (T), x0: T, n, start: int)
yields (T)
for i: int in int$from_to(1, start) do
x0 := f(x0)
end
for i: int in int$from_to(1, n) do
yield(x0)
x0 := f(x0)
end
end iterfunc
% Iterated function
step_fn = proc (x: int) returns (int)
return((x*x + 1) // 255)
end step_fn
start_up = proc ()
po: stream := stream$primary_output()
% Print the first 20 items of the sequence
for i: int in iterfunc[int](step_fn, 3, 20, 0) do
stream$puts(po, int$unparse(i) || " ")
end
stream$putl(po, "")
% Find a cycle
lam, mu: int := brent[int](step_fn, 3)
% Print the length and index
stream$putl(po, "Cycle length: " || int$unparse(lam))
stream$putl(po, "Start index: " || int$unparse(mu))
% Print the cycle
stream$puts(po, "Cycle: ")
for i: int in iterfunc[int](step_fn, 3, lam, mu) do
stream$puts(po, int$unparse(i) || " ")
end
end start_up</syntaxhighlight>
{{out}}
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95
Cycle length: 6
Start index: 2
Cycle: 101 2 5 26 167 95</pre>
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
typedef N is uint8;
interface BrentFn(x: N): (r: N);
sub Brent(f: BrentFn, x0: N): (lam: N, mu: N) is
var power: N := 1;
var tortoise := x0;
var hare := f(x0);
while tortoise != hare loop
if power == lam then
tortoise := hare;
power := power << 1;
lam := 0;
end if;
hare := f(hare);
lam := lam + 1;
end loop;
tortoise := x0;
hare := x0;
var i: N := 0;
while i < lam loop
i := i + 1;
hare := f(hare);
end loop;
mu := 0;
while tortoise != hare loop
tortoise := f(tortoise);
hare := f(hare);
mu := mu + 1;
end loop;
end sub;
sub PrintRange(f: BrentFn, x0: N, start: N, end_: N) is
var i: N := 0;
while i < end_ loop
if i >= start then
print_i32(x0 as uint32);
print_char(' ');
end if;
i := i + 1;
x0 := f(x0);
end loop;
print_nl();
end sub;
sub x2_plus1_mod255 implements BrentFn is
r := ((x as uint16 * x as uint16 + 1) % 255) as uint8;
end sub;
PrintRange(x2_plus1_mod255, 3, 0, 20);
var length: N;
var start: N;
(length, start) := Brent(x2_plus1_mod255, 3);
print("Cycle length: "); print_i32(length as uint32); print_nl();
print("Cycle start: "); print_i32(start as uint32); print_nl();
PrintRange(x2_plus1_mod255, 3, start, length+start);</syntaxhighlight>
{{out}}
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95
Cycle length: 6
Cycle start: 2
101 2 5 26 167 95</pre>
=={{header|D}}==
{{trans|Java}}
<
import std.stdio;
Line 351 ⟶ 812:
auto iterate(int start, int function(int) f) {
return only(start).chain(generate!(() => start=f(start)));
}</
{{out}}
<pre>Cycle length: 6
Line 358 ⟶ 819:
=={{header|Elixir}}==
{{trans|Ruby}}
<
def find_cycle(x0, f) do
lambda = find_lambda(f, x0, f.(x0), 1, 1)
Line 388 ⟶ 849:
# Test the find_cycle function
{clength, cstart} = Cycle_detection.find_cycle(3, f)
IO.puts "Cycle length = #{clength}\nStart index = #{cstart}"</
{{out}}
Line 399 ⟶ 860:
=={{header|Factor}}==
This is a strict translation of the Python code from the Wikipedia article. Perhaps a more idiomatic version could be added in the future, although there is value in showing how Factor's lexical variables differ from most languages. A variable binding with <code>!</code> at the end is mutable, and subsequent uses of that name followed by <code>!</code> change the value of the variable to the value at the top of the data stack.
<
: cyclical-function ( n -- m ) dup * 1 + 255 mod ;
Line 429 ⟶ 890:
3 [ 20 [ dup , cyclical-function ] times ] { } make nip .
3 [ cyclical-function ] brent
"Cycle length: %d\nCycle start: %d\n" printf</
{{out}}
<pre>
Line 435 ⟶ 896:
Cycle length: 6
Cycle start: 2
</pre>
=={{header|FOCAL}}==
<syntaxhighlight lang="focal">01.10 S X0=3;T %3
01.20 S X=X0;F I=1,20;T X;D 2
01.30 D 3;T !" START",M,!,"LENGTH",L,!
01.40 S X=X0;F I=1,M;D 2
01.50 F I=1,L;T X;D 2
01.60 T !
01.70 Q
02.01 C -- X = X*X+1 MOD 255
02.10 S X=X*X+1
02.20 S X=X-255*FITR(X/255)
03.01 C -- BRENT'S ALGORITHM ON ROUTINE 2
03.10 S X=X0;S P=1;S L=1;S T=X0;D 2
03.20 I (T-X)3.3,3.6,3.3
03.30 I (P-L)3.5,3.4,3.5
03.40 S T=X;S P=P*2;S L=0
03.50 D 2;S L=L+1;G 3.2
03.60 S T=X0;S X=X0;F I=1,L;D 2
03.70 S H=X;S M=0
03.80 I (T-H)3.9,3.99,3.9
03.90 S X=T;D 2;S T=X;S X=H;D 2;S H=X;S M=M+1;G 3.8
03.99 R</syntaxhighlight>
{{out}}
<pre>= 3= 10= 101= 2= 5= 26= 167= 95= 101= 2= 5= 26= 167= 95= 101= 2= 5= 26= 167= 95
START= 2
LENGTH= 6
= 101= 2= 5= 26= 167= 95</pre>
=={{header|Forth}}==
Works with gforth.
<syntaxhighlight lang="forth">
: cycle-length { x0 'f -- lambda } \ Brent's algorithm stage 1
1 1 x0 dup 'f execute
begin 2dup <> while
2over = if
2swap nip 2* 0
2swap nip dup
then
'f execute rot 1+ -rot
repeat 2drop nip ;
: iterations ( x f n -- x )
>r swap r> 0 ?do over execute loop nip ;
: cycle-start { x0 'f lambda -- mu } \ Brent's algorithm stage 2
0 x0 dup 'f lambda iterations
begin 2dup <> while
swap 'f execute swap 'f execute rot 1+ -rot
repeat 2drop ;
: find-cycle ( x0 'f -- mu lambda ) \ Brent's algorithm
2dup cycle-length dup >r cycle-start r> ;
\ --- usage ---
: .cycle { start len x0 'f -- }
x0
start 1- 0 do 'f execute loop
len 0 do 'f execute dup . loop
drop ;
: f(x) dup * 1+ 255 mod ;
3 ' f(x) find-cycle
." The cycle starts at offset " over . ." and has a length of " dup . cr
." The cycle is " 3 ' f(x) .cycle cr
bye
</syntaxhighlight>
{{Out}}
<pre>
The cycle starts at offset 2 and has a length of 6
The cycle is 101 2 5 26 167 95
</pre>
Line 440 ⟶ 977:
===Brent's algorithm===
{{trans|Python}}
<
' compile with: fbc -s console
Line 511 ⟶ 1,048:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre> Brent's algorithm
Line 520 ⟶ 1,057:
===Tortoise and hare. Floyd's algorithm===
{{trans|Wikipedia}}
<
' compile with: fbc -s console
Line 600 ⟶ 1,137:
Print : Print "hit any key to end program"
Sleep
End</
=={{header|Go}}==
Line 607 ⟶ 1,144:
Run it on the [https://play.golang.org/p/unOtxuwZfg go playground], or on [https://goplay.space/#S1pQZSuJci go play space].
<syntaxhighlight lang="go">
package main
Line 665 ⟶ 1,202:
}
fmt.Println("Cycle:", a[µ:µ+λ])
}</
{{out}}
Line 674 ⟶ 1,211:
=={{header|Groovy}}==
{{trans|Java}}
<
class CycleDetection {
Line 722 ⟶ 1,259:
println()
}
}</
{{out}}
<pre>Cycle length: 6
Line 733 ⟶ 1,270:
Haskellers, being able to handle conceptually infinite structures, traditionally consider totality as an important issue. The following solution is total for total inputs (modulo totality of iterated function) and allows nontermination only if input is explicitly infinite.
<
findCycle :: Eq a => [a] -> Maybe ([a], Int, Int)
Line 750 ⟶ 1,287:
| pow == lam = loop (2*pow) 1 y ys
| otherwise = loop pow (1+lam) x ys
in loop 1 1 x xs</
'''Examples'''
Line 779 ⟶ 1,316:
Brute force implementation:
<
r=. ~.@(,u@{:)^:_ y
n=. u{:r
(,(#r)-])r i. n
)</
In other words: iterate until we stop getting new values, find the repeated value, and see how it fits into the sequence.
Line 789 ⟶ 1,326:
Example use:
<
2 6</
(Note that 1 0 1 are the coefficients of the polynomial <code>1 + (0 * x) + (1 * x * x)</code> or, if you prefer <code>(1 * x ^ 0) + (0 * x ^ 1) + (1 * x ^ 2)</code> - it's easier and probably more efficient to just hand the coefficients to p. than it is to write out some other expression which produces the same result.)
Line 796 ⟶ 1,333:
=={{header|Java}}==
{{works with|Java|8}}
<
import static java.util.stream.IntStream.*;
Line 838 ⟶ 1,375:
.forEach(n -> System.out.printf("%s ", n));
}
}</
<pre>Cycle length: 6
Cycle: 101 2 5 26 167 95</pre>
=={{header|jq}}==
{{trans|Julia}}
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<syntaxhighlight lang="jq">def floyd(f; x0):
{tort: (x0|f)}
| .hare = (.tort|f)
| until( .tort == .hare;
.tort |= f
| .hare |= (f|f) )
| .mu = 0
| .tort = x0
| until( .tort == .hare;
.tort |= f
| .hare |= f
| .mu += 1)
| .lambda = 1
| .hare = (.tort|f)
| until (.tort == .hare;
.hare |= f
| .lambda += 1 )
| {lambda, mu} ;
def task(f; x0):
def skip($n; stream):
foreach stream as $s (0; .+1; select(. > $n) | $s);
floyd(f; x0)
| .,
"Cycle:",
skip(.mu; limit((.lambda + .mu); 3 | recurse(f)));
</syntaxhighlight>
'''The specific function and task'''
<syntaxhighlight lang="jq">
def f: (.*. + 1) % 255;
task(f;3)
</syntaxhighlight>
{{out}}
<pre>
{
"lambda": 6,
"mu": 2
}
Cycle:
3
10
101
2
5
26
167
95
</pre>
=={{header|Julia}}==
Line 848 ⟶ 1,440:
Following the Wikipedia article:
<
function floyd(f, x0)
Line 883 ⟶ 1,475:
x -> Iterators.take(x, λ) |>
collect
println("Cycle length: ", λ, "\nCycle start index: ", μ, "\nCycle: ", join(cycle, ", "))</
{{out}}
Line 891 ⟶ 1,483:
=={{header|Kotlin}}==
<
typealias IntToInt = (Int) -> Int
Line 939 ⟶ 1,531:
println("Start index = $mu")
println("Cycle = $cycle")
}</
{{out}}
Line 951 ⟶ 1,543:
=={{header|Lua}}==
Fairly direct translation of the Wikipedia code, except that the sequence is stored in a table and passed back as a third return value.
<
local tortoise, hare, mu = x0, f(x0), 0
local cycleTab, power, lam = {tortoise, hare}, 1, 1
Line 979 ⟶ 1,571:
print("Sequence:", table.concat(sequence, " "))
print("Cycle length:", cycleLength)
print("Start Index:", startIndex)</
{{out}}
<pre>Sequence: 3 10 101 2 5 26 167 95 101 2 5 26 167 95
Cycle length: 6
Start Index: 2</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">s = {3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5,
26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101,
2, 5, 26, 167, 95, 101, 2, 5};
{transient, repeat} = FindTransientRepeat[s, 2];
Print["Starting index: ", Length[transient] + 1]
Print["Cycles: ", Floor[(Length[s] - Length[transient])/Length[repeat]]]</syntaxhighlight>
{{out}}
<pre>Starting index: 3
Cycles: 6</pre>
=={{header|Modula-2}}==
{{trans|Kotlin}}
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 1,082 ⟶ 1,685:
ReadChar
END CycleDetection.</
=={{header|Nim}}==
Translation of Wikipedia Python program.
<syntaxhighlight lang="nim">import strutils, sugar
func brent(f: int -> int; x0: int): (int, int) =
# Main phase: search successive powers of two.
var
power, λ = 1
tortoise = x0
hare = f(x0)
while tortoise != hare:
if power == λ:
# Time to start a new power of two.
tortoise = hare
power *= 2
λ = 0
hare = f(hare)
inc λ
# Find the position of the first repetition of length λ.
tortoise = x0
hare = x0
for i in 0..<λ:
hare = f(hare)
# The distance between the hare and tortoise is now λ.
# Next, the hare and tortoise move at same speed until they agree.
var μ = 0
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare)
inc μ
result = (λ, μ)
when isMainModule:
func f(x: int): int = (x * x + 1) mod 255
let x0 = 3
let (λ, μ) = brent(f, x0)
echo "Cycle length: ", λ
echo "Cycle start index: ", μ
var cycle: seq[int]
var x = x0
for i in 0..<λ+μ:
if i >= μ: cycle.add x
x = f(x)
echo "Cycle: ", cycle.join(" ")</syntaxhighlight>
{{out}}
<pre>Cycle length: 6
Cycle start index: 2
Cycle: 101 2 5 26 167 95</pre>
=={{header|ooRexx}}==
<
x=3
list=x
Line 1,102 ⟶ 1,764:
End
Exit
f: Return (arg(1)**2+1)//255 </
{{out}}
<pre>
Line 1,113 ⟶ 1,775:
=={{header|Perl}}==
{{trans|Raku}}
<
sub cyclical_function { ($_[0] * $_[0] + 1) % 255 }
Line 1,161 ⟶ 1,823:
print "Cycle length $l\n";
print "Cycle start index $s\n";
print show_range($s,$s+$l-1) . "\n";</
{{out}}
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95
Line 1,170 ⟶ 1,832:
=={{header|Phix}}==
Translation of the Wikipedia code, but using the more descriptive len and pos, instead of lambda and mu, and adding a limit.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">function</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">*</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">255</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">brent</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x0</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">pow2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">tortoise</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x0</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">hare</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x0</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">tortoise</span><span style="color: #0000FF;">,</span><span style="color: #000000;">hare</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- (kept for output only)
-- main phase: search successive powers of two</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">tortoise</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">hare</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pow2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">len</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">tortoise</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">hare</span>
<span style="color: #000000;">pow2</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pow2</span><span style="color: #0000FF;">></span><span style="color: #000000;">16</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">hare</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hare</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">hare</span>
<span style="color: #000000;">len</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000080;font-style:italic;">-- Find the position of the first repetition of length len</span>
<span style="color: #000000;">tortoise</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x0</span>
<span style="color: #000000;">hare</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">len</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">hare</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hare</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- The distance between the hare and tortoise is now len.
-- Next, the hare and tortoise move at same speed until they agree</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">tortoise</span><span style="color: #0000FF;"><></span><span style="color: #000000;">hare</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">tortoise</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tortoise</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">hare</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hare</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">pos</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x0</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">3</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">brent</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x0</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" Brent's algorithm\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">s</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" Cycle starts at position: %d (1-based)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" The length of the Cycle = %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">len</span><span style="color: #0000FF;">})</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">..</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">+</span><span style="color: #000000;">len</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,229 ⟶ 1,893:
{101,2,5,26,167,95}
</pre>
=={{header|PL/M}}==
<syntaxhighlight lang="plm">100H:
/* CP/M CALLS */
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT;
PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9,S); END PRINT;
/* THIS IS A HACK TO CALL A FUNCTION GIVEN ITS ADDRESS */
APPLY: PROCEDURE (FN, ARG) ADDRESS;
DECLARE (FN, ARG) ADDRESS;
INNER: PROCEDURE (X) ADDRESS; /* THIS SETS UP THE ARGUMENTS IN MEMORY */
DECLARE X ADDRESS;
GO TO FN; /* THEN WE JUMP TO THE ADDRESS GIVEN */
END INNER;
RETURN INNER(ARG);
END APPLY;
/* THIS IS ANOTHER HACK - THE SINGLE 0 (WHICH IS AN 8080 NOP) WILL BE
STORED AS A CONSTANT RIGHT BEFORE THE FUNCTION.
PL/M-80 DOES NOT ALLOW THE PROGRAMMER TO DIRECTLY GET THE ADDRESS
OF A FUNCTION, BUT THE ADDRESS OF THIS CONSTANT WILL BE RIGHT IN
FRONT OF IT AND CAN BE USED INSTEAD. */
DECLARE F$ADDR DATA (0);
/* F(X) FROM THE TASK */
F: PROCEDURE (X) ADDRESS;
DECLARE X ADDRESS;
RETURN (X*X + 1) MOD 255;
END F;
/* PRINT A NUMBER */
PRINT$NUMBER: PROCEDURE (N);
DECLARE S (7) BYTE INITIAL ('..... $');
DECLARE (N, P) ADDRESS, C BASED P BYTE;
P = .S(5);
DIGIT:
P = P - 1;
C = N MOD 10 + '0';
N = N / 10;
IF N > 0 THEN GO TO DIGIT;
CALL PRINT(P);
END PRINT$NUMBER;
/* PRINT F^M(X0) TO F^N(X0) */
PRINT$RANGE: PROCEDURE (FN, X0, M, N);
DECLARE (FN, X0, M, N, I) ADDRESS;
DO I=0 TO N-1;
IF I>=M THEN CALL PRINT$NUMBER(X0);
X0 = APPLY(FN,X0);
END;
CALL PRINT(.(13,10,'$'));
END PRINT$RANGE;
/* BRENT'S ALGORITHM */
BRENT: PROCEDURE (FN, X0, MU$A, LAM$A);
DECLARE (FN, X0, MU$A, LAM$A) ADDRESS;
DECLARE (MU BASED MU$A, LAM BASED LAM$A) ADDRESS;
DECLARE (TORT, HARE, POW, I) ADDRESS;
POW, LAM = 1;
TORT = X0;
HARE = APPLY(FN,X0);
DO WHILE TORT <> HARE;
IF POW = LAM THEN DO;
TORT = HARE;
POW = SHL(POW, 1);
LAM = 0;
END;
HARE = APPLY(FN,HARE);
LAM = LAM + 1;
END;
TORT, HARE = X0;
DO I=1 TO LAM;
HARE = APPLY(FN,HARE);
END;
MU = 0;
DO WHILE TORT <> HARE;
TORT = APPLY(FN,TORT);
HARE = APPLY(FN,HARE);
MU = MU + 1;
END;
END BRENT;
DECLARE (MU, LAM) ADDRESS;
/* PRINT THE FIRST 20 VALUES IN THE SEQUENCE */
CALL PRINT$RANGE(.F$ADDR, 3, 0, 20);
/* FIND THE CYCLE */
CALL BRENT(.F$ADDR, 3, .MU, .LAM);
CALL PRINT(.'LENGTH: $');
CALL PRINT$NUMBER(LAM);
CALL PRINT(.'START: $');
CALL PRINT$NUMBER(MU);
CALL PRINT(.(13,10,'$'));
/* PRINT THE CYCLE */
CALL PRINT$RANGE(.F$ADDR, 3, MU, MU+LAM);
CALL EXIT;
EOF</syntaxhighlight>
{{out}}
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95
LENGTH: 6 START: 2
101 2 5 26 167 95 </pre>
=={{header|Python}}==
===Procedural===
Function from the Wikipedia article:
<
def brent(f, x0):
Line 1,275 ⟶ 2,043:
print("Cycle length: %d" % lam)
print("Cycle start index: %d" % mu)
print("Cycle: %s" % list(itertools.islice(iterate(f, x0), mu, mu+lam)))</
{{out}}
<pre>
Line 1,284 ⟶ 2,052:
A modified version of the above where the first stage is restructured for clarity:
<
def brent_length(f, x0):
Line 1,329 ⟶ 2,097:
print("Cycle length: %d" % lam)
print("Cycle start index: %d" % mu)
print("Cycle: %s" % list(itertools.islice(iterate(f, x0), mu, mu+lam)))</
{{out}}
<pre>Cycle length: 6
Line 1,339 ⟶ 2,107:
{{Trans|Haskell}}
{{Works with|Python|3.7}}
<
from itertools import (chain, cycle, islice)
Line 1,572 ⟶ 2,340:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>First cycle detected, if any:
Line 1,586 ⟶ 2,354:
Recursive ''until'':
<
def until(p):
'''The result of repeatedly applying f until p holds.
Line 1,592 ⟶ 2,360:
def go(f, x):
return x if p(x) else go(f, f(x))
return lambda f: lambda x: go(f, x)</
''cycleLength'' refactored in terms of ''until'':
<
def cycleLength(xs):
'''Just the length of the first cycle found,
Line 1,621 ⟶ 2,389:
) if ys else Nothing()
else:
return Nothing()</
Iterative reimplementation of ''until'':
<
def until_(p):
'''The result of repeatedly applying f until p holds.
Line 1,633 ⟶ 2,401:
v = f(v)
return v
return lambda f: lambda x: go(f, x)</
Line 1,639 ⟶ 2,407:
The Python no longer falls out of the tree at the sight of an ouroboros, and we can happily search for cycles in lists of several thousand items:
{{Works with|Python|3.7}}
<
from itertools import (chain, cycle, islice)
Line 1,894 ⟶ 2,662:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>First cycle detected, if any:
Line 1,902 ⟶ 2,670:
[1..10000] -> No cycle found
f(x) = (x*x + 1) modulo 255 -> [101,2,5,26,167,95] (from:2, length:6)</pre>
=={{header|Quackery}}==
<syntaxhighlight lang="quackery"> [ stack ] is fun ( --> s )
[ stack ] is pow ( --> s )
[ stack ] is len ( --> s )
[ fun put
1 pow put
1 len put
dup fun share do
[ 2dup != while
len share
pow share = if
[ nip dup
pow share
pow tally
0 len replace ]
fun share do
1 len tally
again ]
2drop
fun release
pow release
len take ] is cyclelen ( n x --> n )
[ 0 temp put
dip [ fun put dup ]
times [ fun share do ]
[ 2dup != while
fun share do
dip [ fun share do ]
1 temp tally
again ]
2drop
fun release
temp take ] is cyclepos ( n x n --> n )
[ 2dup cyclelen
dup dip cyclepos ] is brent ( n x --> n n )
[ 2dup
20 times
[ over echo sp
tuck do swap ]
cr cr
2drop
brent
say "cycle length is "
echo cr
say "cycle starts at "
echo ] is task ( n x --> )
3 ' [ 2 ** 1+ 255 mod ] task</syntaxhighlight>
{{out}}
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95
cycle length is 6
cycle starts at 2
</pre>
=={{header|Racket}}==
I feel a bit bad about overloading λ, but it’s in the spirit of the algorithm.
<
#lang racket/base
Line 1,945 ⟶ 2,776:
(let-values (([µ λ] (brent f 3)))
(printf "Cycle length = ~a~%Start Index = ~a~%" µ λ)))
</syntaxhighlight>
{{out}}
Line 1,959 ⟶ 2,790:
Pretty much a line for line translation of the Python code on the Wikipedia page.
<syntaxhighlight lang="raku"
my ( $l, $s ) = brent( &cyclical-function, 3 );
Line 1,992 ⟶ 2,823:
}
return $λ, $μ;
}</
{{out}}
<pre>3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, ...
Line 2,001 ⟶ 2,832:
=={{header|REXX}}==
===Brent's algorithm===
<
init= 3; $= init
do until length($)>79; $= $ f( word($, words($) ) )
Line 2,034 ⟶ 2,865:
return # mu
/*──────────────────────────────────────────────────────────────────────────────────────*/
f: return ( arg(1) **2 + 1) // 255 /*this defines/executes the function F.*/</
{{out|output|text= when using the defaults:}}
<pre>
Line 2,045 ⟶ 2,876:
===sequential search algorithm===
<
x= 3; $= x /*initial couple of variables*/
do until cycle\==0; x= f(x) /*calculate another number. */
Line 2,058 ⟶ 2,889:
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
f: return ( arg(1) **2 + 1) // 255 /*this defines/executes the function F.*/</
{{out|output|:}}
<pre>
Line 2,070 ⟶ 2,901:
===hash table algorithm===
This REXX version is a lot faster (than the sequential search algorithm) if the ''cycle length'' and/or ''start index'' is large.
<
!.= .; !.x= 1; x= 3; $= x /*assign initial value. */
do #=1+words($); x= f(x); $= $ x /*add the number to list.*/
Line 2,083 ⟶ 2,914:
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
f: return ( arg(1) **2 + 1) // 255 /*this defines/executes the function F.*/</
{{out|output|text= is identical to the 2<sup>nd</sup> REXX version.}} <br><br>
Line 2,096 ⟶ 2,927:
<br>test the hash table algorithm. A divisor which is <big> ''two raised to the 49<sup>th</sup> power'' </big> was chosen; it
<br>generates a cyclic sequence that contains over 1.5 million numbers.
<
parse arg power . /*obtain optional args from C.L. */
if power=='' | power="," then power=8 /*Not specified? Use the default*/
Line 2,120 ⟶ 2,951:
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
f: return ( arg(1) **2 + 1) // 255 /*this defines/executes the function F.*/</
{{out|output|text= when the input (power of two) used is: <tt> 49 </tt>}}
<pre>
Line 2,136 ⟶ 2,967:
There is more information in the "hash table"<br>
and f has no "side effect".
<
x=3; list=x; p.=0; p.x=1
Do q=2 By 1
Line 2,153 ⟶ 2,984:
Exit
/*-------------------------------------------------------------------*/
f: Return (arg(1)**2+1)// 255; /*define the function F*/</
=={{header|RPL}}==
Translation of the Brent algorithm given in Wikipedia.
{{works with|HP|48}}
≪ 1 1 0 → f x0 power lam mu
≪ x0 DUP f EVAL <span style="color:grey">@ Main phase: search successive powers of two</span>
'''WHILE''' DUP2 ≠ '''REPEAT'''
'''IF''' power lam == '''THEN''' <span style="color:grey">@ time to start a new power of two?</span>
SWAP DROP DUP
2 'power' STO*
0 'lam' STO
'''END'''
f EVAL
1 'lam' STO+
'''END'''
DROP2 x0 DUP <span style="color:grey">@ Find the position of the first repetition of length λ</span>
0 lam 1 - '''START'''
f EVAL '''NEXT''' <span style="color:grey">@ distance between the hare and tortoise is now λ</span>
'''WHILE''' DUP2 ≠ '''REPEAT''' <span style="color:grey">@ the hare and tortoise move at same speed until they agree</span>
f EVAL SWAP
f EVAL SWAP
1 'mu' STO+
'''END'''
DROP2 lam mu
≫ ≫ '<span style="color:blue">CYCLEB</span>' STO
≪ SQ 1 + 255 MOD ≫ 0 <span style="color:blue">CYCLEB</span>
{{out}}
<pre>
2: 6
1: 2
</pre>
=={{header|Ruby}}==
{{works with|ruby|2.0}}
<
# Purpose:
# Find the cycle length and start position of a numerical seried using Brent's cycle algorithm.
Line 2,215 ⟶ 3,078:
# Test the findCycle function
clength, cstart = findCycle(3) { |x| f(x) }
puts "Cycle length = #{clength}\nStart index = #{cstart}"</
{{out}}
Line 2,227 ⟶ 3,090:
=== Procedural ===
{{Out}}Best seen in running your browser either by [https://scalafiddle.io/sf/6O7WjnO/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/kPCg0fxOQQCZPkOnmMR0Kg Scastie (remote JVM)].
<
def brent(f: Int => Int, x0: Int): (Int, Int) = {
Line 2,271 ⟶ 3,134:
println(s"Cycle = ${cycle.force}")
}</
=== Functional ===
<syntaxhighlight lang="scala">
import scala.annotation.tailrec
Line 2,337 ⟶ 3,200:
}
</syntaxhighlight>
{{out}}
Line 2,348 ⟶ 3,211:
=={{header|Sidef}}==
{{trans|Raku}}
<
var power = 1
var λ = 1
Line 2,391 ⟶ 3,254:
say "Cycle length #{l}.";
say "Cycle start index #{s}."
say [seq[s .. (s + l - 1)]]</
{{out}}
<pre>3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, ...
Line 2,400 ⟶ 3,263:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Function FindCycle(Of T As IEquatable(Of T))(x0 As T, yielder As Func(Of T, T)) As Tuple(Of Integer, Integer)
Line 2,458 ⟶ 3,321:
End Sub
End Module</
{{out}}
<pre>3,10,101,2,5,26,167,95,101,2,5,26,167,95,101,2,5,26,167,95,101,2,5,26,167,95,101,2,5,26,167,95,101,2,5,26,167,95,101,2,5
Cycle length = 6
Start index = 2</pre>
=={{header|Wren}}==
Working from the code in the Wikipedia article:
<syntaxhighlight lang="wren">var brent = Fn.new { |f, x0|
var lam = 1
var power = 1
var tortoise = x0
var hare = f.call(x0)
while (tortoise != hare) {
if (power == lam) {
tortoise = hare
power = power * 2
lam = 0
}
hare = f.call(hare)
lam = lam + 1
}
tortoise = hare = x0
for (i in 0...lam) hare = f.call(hare)
var mu = 0
while (tortoise != hare) {
tortoise = f.call(tortoise)
hare = f.call(hare)
mu = mu + 1
}
return [lam, mu]
}
var f = Fn.new { |x| (x*x + 1) % 255 }
var x0 = 3
var x = x0
var seq = List.filled(21, 0) // limit to first 21 terms say
for (i in 0..20) {
seq[i] = x
x = f.call(x)
}
var res = brent.call(f, x0)
var lam = res[0]
var mu = res[1]
System.print("Sequence = %(seq)")
System.print("Cycle length = %(lam)")
System.print("Start index = %(mu)")
System.print("Cycle = %(seq[mu...mu+lam])")</syntaxhighlight>
{{out}}
<pre>
Sequence = [3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101]
Cycle length = 6
Start index = 2
Cycle = [101, 2, 5, 26, 167, 95]
</pre>
=={{header|zkl}}==
Algorithm from the Wikipedia
<
# main phase: search successive powers of two
power:=lam:=1;
Line 2,488 ⟶ 3,402:
}
return(lam,mu);
}</
<
{{out}}
<pre>
|