Cycle detection: Difference between revisions

101 2 5 26 167 95</pre>

=={{header|BCPL}}==

<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)

$)</lang>

{{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