Cycle detection: Difference between revisions

 

;Task:

=={{header|11l}}==

{{trans|D}}

Int cycle_length

V hare = x0

print_result(x0, f, cycle_length, cycle_start)

 

{{out}}

<pre>

 

=={{header|8086 Assembly}}==

org 100h

section .text

ix: db 'Index: $'

len: db 'Length: $'

{{out}}

<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95

=={{header|Ada}}==

This implementation is split across three files. The first is the specification of a generic package:

generic

type Element_Type is private;

procedure Brent(F : Brent_Function; X0 : Element_Type; Lambda : out Integer; Mu : out Integer);

end Brent;

The second is the body of the generic package:

package body Brent is

procedure Brent (F : Brent_Function; X0 : Element_Type; Lambda : out Integer; Mu : out Integer) is

end Brent;

end Brent;

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:

with Brent;

with Text_Io;

end loop;

end Main;

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

=={{header|APL}}==

{{works with|Dyalog APL}}

f←⍺⍺

lam←⊃{

}

 

{{out}}

<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95

 

=={{header|BCPL}}==

 

// Brent's algorithm. 'fn' is a function pointer,

// print the cycle

printRange(f, 3, mu, mu+lam)

{{out}}

<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95

Index: 2

101 2 5 26 167 95</pre>

 

=={{header|C}}==

{{trans|Modula-2}}

#include <stdlib.h>

 

 

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]

Cycle = [101, 2, 5, 26, 167, 95]</pre>

 

This solution uses generics, so may find cycles of any type of data, not just integers.

 

 

// First file: Cycles.cs

}

 

 

=={{header|C++}}==

int val;

ListNode *next;

}

}

 

=={{header|Cowgol}}==

 

typedef N is uint8;

print("Cycle length: "); print_i32(length as uint32); print_nl();

print("Cycle start: "); print_i32(start as uint32); print_nl();

{{out}}

<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95

=={{header|D}}==

{{trans|Java}}

import std.stdio;

 

auto iterate(int start, int function(int) f) {

return only(start).chain(generate!(() => start=f(start)));

{{out}}

<pre>Cycle length: 6

=={{header|Elixir}}==

{{trans|Ruby}}

def find_cycle(x0, f) do

lambda = find_lambda(f, x0, f.(x0), 1, 1)

# Test the find_cycle function

{clength, cstart} = Cycle_detection.find_cycle(3, f)

 

{{out}}

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

3 [ 20 [ dup , cyclical-function ] times ] { } make nip .

3 [ cyclical-function ] brent

{{out}}

<pre>

 

=={{header|FOCAL}}==

01.20 S X=X0;F I=1,20;T X;D 2

01.30 D 3;T !" START",M,!,"LENGTH",L,!

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

{{out}}

<pre>= 3= 10= 101= 2= 5= 26= 167= 95= 101= 2= 5= 26= 167= 95= 101= 2= 5= 26= 167= 95

=={{header|Forth}}==

Works with gforth.

: cycle-length { x0 'f -- lambda } \ Brent's algorithm stage 1

1 1 x0 dup 'f execute

." The cycle is " 3 ' f(x) .cycle cr

bye

{{Out}}

<pre>

===Brent's algorithm===

{{trans|Python}}

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre> Brent's algorithm

===Tortoise and hare. Floyd's algorithm===

{{trans|Wikipedia}}

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

 

=={{header|Go}}==

 

Run it on the [https://play.golang.org/p/unOtxuwZfg go playground], or on [https://goplay.space/#S1pQZSuJci go play space].

package main

 

}

fmt.Println("Cycle:", a[µ:µ+λ])

 

{{out}}

=={{header|Groovy}}==

{{trans|Java}}

 

class CycleDetection {

println()

}

{{out}}

<pre>Cycle length: 6

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)

| pow == lam = loop (2*pow) 1 y ys

| otherwise = loop pow (1+lam) x ys

 

'''Examples'''

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.

Example use:

 

 

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

=={{header|Java}}==

{{works with|Java|8}}

import static java.util.stream.IntStream.*;

 

.forEach(n -> System.out.printf("%s ", n));

}

 

<pre>Cycle length: 6

Cycle: 101 2 5 26 167 95</pre>

 

=={{header|Julia}}==

Following the Wikipedia article:

 

 

function floyd(f, x0)

x -> Iterators.take(x, λ) |>

collect

 

{{out}}

 

=={{header|Kotlin}}==

 

typealias IntToInt = (Int) -> Int

println("Start index = $mu")

println("Cycle = $cycle")

 

{{out}}

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

print("Sequence:", table.concat(sequence, " "))

print("Cycle length:", cycleLength)

{{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|Modula-2}}==

{{trans|Kotlin}}

FROM FormatString IMPORT FormatString;

FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

 

ReadChar

 

=={{header|ooRexx}}==

x=3

list=x

End

Exit

{{out}}

<pre>

=={{header|Perl}}==

{{trans|Raku}}

 

sub cyclical_function { ($_[0] * $_[0] + 1) % 255 }

print "Cycle length $l\n";

print "Cycle start index $s\n";

{{out}}

<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95

=={{header|Phix}}==

Translation of the Wikipedia code, but using the more descriptive len and pos, instead of lambda and mu, and adding a limit.

{{out}}

<pre>

 

=={{header|PL/M}}==

/* CP/M CALLS */

BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;

CALL PRINT$RANGE(.F$ADDR, 3, MU, MU+LAM);

CALL EXIT;

{{out}}

<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95

===Procedural===

Function from the Wikipedia article:

 

def brent(f, x0):

print("Cycle length: %d" % lam)

print("Cycle start index: %d" % mu)

{{out}}

<pre>

 

A modified version of the above where the first stage is restructured for clarity:

 

def brent_length(f, x0):

print("Cycle length: %d" % lam)

print("Cycle start index: %d" % mu)

{{out}}

<pre>Cycle length: 6

{{Trans|Haskell}}

{{Works with|Python|3.7}}

 

from itertools import (chain, cycle, islice)

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>First cycle detected, if any:

 

Recursive ''until'':

def until(p):

'''The result of repeatedly applying f until p holds.

def go(f, x):

return x if p(x) else go(f, f(x))

 

''cycleLength'' refactored in terms of ''until'':

def cycleLength(xs):

'''Just the length of the first cycle found,

) if ys else Nothing()

else:

 

Iterative reimplementation of ''until'':

def until_(p):

'''The result of repeatedly applying f until p holds.

v = f(v)

return v

 

 

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)

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>First cycle detected, if any:

[1..10000] -> No cycle found

f(x) = (x*x + 1) modulo 255 -> [101,2,5,26,167,95] (from:2, length:6)</pre>

 

=={{header|Racket}}==

 

I feel a bit bad about overloading λ, but it&rsquo;s in the spirit of the algorithm.

#lang racket/base

 

(let-values (([µ λ] (brent f 3)))

(printf "Cycle length = ~a~%Start Index = ~a~%" µ λ)))

 

{{out}}

Pretty much a line for line translation of the Python code on the Wikipedia page.

 

 

my ( $l, $s ) = brent( &cyclical-function, 3 );

}

return $λ, $μ;

{{out}}

<pre>3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, ...

=={{header|REXX}}==

===Brent's algorithm===

init= 3; $= init

do until length($)>79; $= $ f( word($, words($) ) )

return # mu

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the defaults:}}

<pre>

 

===sequential search algorithm===

x= 3; $= x /*initial couple of variables*/

do until cycle\==0; x= f(x) /*calculate another number. */

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|:}}

<pre>

===hash table algorithm===

This REXX version is a lot faster &nbsp; (than the sequential search algorithm) &nbsp; if the &nbsp; ''cycle length'' &nbsp; and/or &nbsp; ''start index'' &nbsp; is large.

!.= .; !.x= 1; x= 3; $= x /*assign initial value. */

do #=1+words($); x= f(x); $= $ x /*add the number to list.*/

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; is identical to the 2^nd REXX version.}} <br><br>

 

<br>test the hash table algorithm. &nbsp; A divisor which is &nbsp; <big> ''two raised to the 49^th power'' </big> &nbsp; was chosen; &nbsp; 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*/

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text= &nbsp; when the input (power of two) used is: &nbsp; &nbsp; <tt> 49 </tt>}}

<pre>

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

Exit

/*-------------------------------------------------------------------*/

 

=={{header|Ruby}}==

{{works with|ruby|2.0}}

 

# Purpose:

# Find the cycle length and start position of a numerical seried using Brent's cycle algorithm.

# Test the findCycle function

clength, cstart = findCycle(3) { |x| f(x) }

 

{{out}}

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

println(s"Cycle = ${cycle.force}")

 

 

=== Functional ===

import scala.annotation.tailrec

 

 

}

 

{{out}}

=={{header|Sidef}}==

{{trans|Raku}}

var power = 1

var λ = 1

say "Cycle length #{l}.";

say "Cycle start index #{s}."

{{out}}

<pre>3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, ...

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

End Sub

 

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

=={{header|Wren}}==

Working from the code in the Wikipedia article:

var lam = 1

var power = 1

System.print("Cycle length = %(lam)")

System.print("Start index = %(mu)")

 

{{out}}

=={{header|zkl}}==

Algorithm from the Wikipedia

# main phase: search successive powers of two

power:=lam:=1;

}

return(lam,mu);

{{out}}

<pre>