Cycle detection: Difference between revisions
Content added Content deleted
(Added Quackery.) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 33: | Line 33: | ||
=={{header|11l}}== |
=={{header|11l}}== |
||
{{trans|D}} |
{{trans|D}} |
||
< |
<syntaxhighlight lang="11l">F print_result(x0, f, len, start) |
||
print(‘Cycle length = ’len) |
print(‘Cycle length = ’len) |
||
print(‘Start index = ’start) |
print(‘Start index = ’start) |
||
Line 72: | Line 72: | ||
print_result(x0, f, cycle_length, cycle_start) |
print_result(x0, f, cycle_length, cycle_start) |
||
brent(i -> (i * i + 1) % 255, 3)</ |
brent(i -> (i * i + 1) % 255, 3)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 81: | Line 81: | ||
=={{header|8086 Assembly}}== |
=={{header|8086 Assembly}}== |
||
< |
<syntaxhighlight lang="asm"> cpu 8086 |
||
org 100h |
org 100h |
||
section .text |
section .text |
||
Line 187: | Line 187: | ||
ix: db 'Index: $' |
ix: db 'Index: $' |
||
len: db 'Length: $' |
len: db 'Length: $' |
||
nl: db 13,10,'$'</ |
nl: db 13,10,'$'</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 |
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 |
||
Line 194: | Line 194: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
This implementation is split across three files. The first is the specification of a generic package: |
This implementation is split across three files. The first is the specification of a generic package: |
||
< |
<syntaxhighlight lang="ada"> |
||
generic |
generic |
||
type Element_Type is private; |
type Element_Type is private; |
||
Line 201: | Line 201: | ||
procedure Brent(F : Brent_Function; X0 : Element_Type; Lambda : out Integer; Mu : out Integer); |
procedure Brent(F : Brent_Function; X0 : Element_Type; Lambda : out Integer; Mu : out Integer); |
||
end Brent; |
end Brent; |
||
</syntaxhighlight> |
|||
</lang> |
|||
The second is the body of the generic package: |
The second is the body of the generic package: |
||
< |
<syntaxhighlight lang="ada"> |
||
package body Brent is |
package body Brent is |
||
procedure Brent (F : Brent_Function; X0 : Element_Type; Lambda : out Integer; Mu : out Integer) is |
procedure Brent (F : Brent_Function; X0 : Element_Type; Lambda : out Integer; Mu : out Integer) is |
||
Line 233: | Line 233: | ||
end Brent; |
end Brent; |
||
end Brent; |
end Brent; |
||
</syntaxhighlight> |
|||
</lang> |
|||
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: |
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 Brent; |
||
with Text_Io; |
with Text_Io; |
||
Line 277: | Line 277: | ||
end loop; |
end loop; |
||
end Main; |
end Main; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{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 |
<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 288: | Line 288: | ||
=={{header|APL}}== |
=={{header|APL}}== |
||
{{works with|Dyalog APL}} |
{{works with|Dyalog APL}} |
||
< |
<syntaxhighlight lang="apl">brent←{ |
||
f←⍺⍺ |
f←⍺⍺ |
||
lam←⊃{ |
lam←⊃{ |
||
Line 307: | Line 307: | ||
} |
} |
||
(255 | 1 + ⊢×⊢) task 3</ |
(255 | 1 + ⊢×⊢) task 3</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 |
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 |
||
Line 315: | Line 315: | ||
=={{header|BCPL}}== |
=={{header|BCPL}}== |
||
< |
<syntaxhighlight lang="bcpl">get "libhdr" |
||
// Brent's algorithm. 'fn' is a function pointer, |
// Brent's algorithm. 'fn' is a function pointer, |
||
Line 370: | Line 370: | ||
// print the cycle |
// print the cycle |
||
printRange(f, 3, mu, mu+lam) |
printRange(f, 3, mu, mu+lam) |
||
$)</ |
$)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 |
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 |
||
Line 378: | Line 378: | ||
=={{header|BQN}}== |
=={{header|BQN}}== |
||
< |
<syntaxhighlight lang="bqn">_Brent← {F _𝕣 x0: |
||
p←l←1 |
p←l←1 |
||
(I ← {p=l? |
(I ← {p=l? |
||
Line 387: | Line 387: | ||
{m+↩1 ⋄ 𝕨𝕊⍟≠○F𝕩}⟜(F⍟l) x0 |
{m+↩1 ⋄ 𝕨𝕊⍟≠○F𝕩}⟜(F⍟l) x0 |
||
l‿m‿(F⍟(m+↕l)x0) |
l‿m‿(F⍟(m+↕l)x0) |
||
}</ |
}</syntaxhighlight> |
||
{{out|Example use}} |
{{out|Example use}} |
||
<pre> (255|1+ט)_Brent 3 |
<pre> (255|1+ט)_Brent 3 |
||
Line 394: | Line 394: | ||
=={{header|C}}== |
=={{header|C}}== |
||
{{trans|Modula-2}} |
{{trans|Modula-2}} |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 472: | Line 472: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{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] |
<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 482: | Line 482: | ||
This solution uses generics, so may find cycles of any type of data, not just integers. |
This solution uses generics, so may find cycles of any type of data, not just integers. |
||
< |
<syntaxhighlight lang="csharp"> |
||
// First file: Cycles.cs |
// First file: Cycles.cs |
||
Line 578: | Line 578: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp">struct ListNode { |
||
int val; |
int val; |
||
ListNode *next; |
ListNode *next; |
||
Line 617: | Line 617: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|CLU}}== |
=={{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) |
brent = proc [T: type] (f: proctype (T) returns (T), x0: T) |
||
returns (int,int) |
returns (int,int) |
||
Line 695: | Line 695: | ||
stream$puts(po, int$unparse(i) || " ") |
stream$puts(po, int$unparse(i) || " ") |
||
end |
end |
||
end start_up</ |
end start_up</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 |
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 |
||
Line 703: | Line 703: | ||
=={{header|Cowgol}}== |
=={{header|Cowgol}}== |
||
< |
<syntaxhighlight lang="cowgol">include "cowgol.coh"; |
||
typedef N is uint8; |
typedef N is uint8; |
||
Line 761: | Line 761: | ||
print("Cycle length: "); print_i32(length as uint32); print_nl(); |
print("Cycle length: "); print_i32(length as uint32); print_nl(); |
||
print("Cycle start: "); print_i32(start as uint32); print_nl(); |
print("Cycle start: "); print_i32(start as uint32); print_nl(); |
||
PrintRange(x2_plus1_mod255, 3, start, length+start);</ |
PrintRange(x2_plus1_mod255, 3, start, length+start);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 |
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 |
||
Line 770: | Line 770: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="d">import std.range; |
||
import std.stdio; |
import std.stdio; |
||
Line 812: | Line 812: | ||
auto iterate(int start, int function(int) f) { |
auto iterate(int start, int function(int) f) { |
||
return only(start).chain(generate!(() => start=f(start))); |
return only(start).chain(generate!(() => start=f(start))); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Cycle length: 6 |
<pre>Cycle length: 6 |
||
Line 819: | Line 819: | ||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang="elixir">defmodule Cycle_detection do |
||
def find_cycle(x0, f) do |
def find_cycle(x0, f) do |
||
lambda = find_lambda(f, x0, f.(x0), 1, 1) |
lambda = find_lambda(f, x0, f.(x0), 1, 1) |
||
Line 849: | Line 849: | ||
# Test the find_cycle function |
# Test the find_cycle function |
||
{clength, cstart} = Cycle_detection.find_cycle(3, f) |
{clength, cstart} = Cycle_detection.find_cycle(3, f) |
||
IO.puts "Cycle length = #{clength}\nStart index = #{cstart}"</ |
IO.puts "Cycle length = #{clength}\nStart index = #{cstart}"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 860: | Line 860: | ||
=={{header|Factor}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang="factor">USING: formatting kernel locals make math prettyprint ; |
||
: cyclical-function ( n -- m ) dup * 1 + 255 mod ; |
: cyclical-function ( n -- m ) dup * 1 + 255 mod ; |
||
Line 890: | Line 890: | ||
3 [ 20 [ dup , cyclical-function ] times ] { } make nip . |
3 [ 20 [ dup , cyclical-function ] times ] { } make nip . |
||
3 [ cyclical-function ] brent |
3 [ cyclical-function ] brent |
||
"Cycle length: %d\nCycle start: %d\n" printf</ |
"Cycle length: %d\nCycle start: %d\n" printf</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 899: | Line 899: | ||
=={{header|FOCAL}}== |
=={{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.20 S X=X0;F I=1,20;T X;D 2 |
||
01.30 D 3;T !" START",M,!,"LENGTH",L,! |
01.30 D 3;T !" START",M,!,"LENGTH",L,! |
||
Line 921: | Line 921: | ||
03.80 I (T-H)3.9,3.99,3.9 |
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.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</ |
03.99 R</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>= 3= 10= 101= 2= 5= 26= 167= 95= 101= 2= 5= 26= 167= 95= 101= 2= 5= 26= 167= 95 |
<pre>= 3= 10= 101= 2= 5= 26= 167= 95= 101= 2= 5= 26= 167= 95= 101= 2= 5= 26= 167= 95 |
||
Line 930: | Line 930: | ||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
Works with gforth. |
Works with gforth. |
||
<syntaxhighlight lang="forth"> |
|||
<lang Forth> |
|||
: cycle-length { x0 'f -- lambda } \ Brent's algorithm stage 1 |
: cycle-length { x0 'f -- lambda } \ Brent's algorithm stage 1 |
||
1 1 x0 dup 'f execute |
1 1 x0 dup 'f execute |
||
Line 967: | Line 967: | ||
." The cycle is " 3 ' f(x) .cycle cr |
." The cycle is " 3 ' f(x) .cycle cr |
||
bye |
bye |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 977: | Line 977: | ||
===Brent's algorithm=== |
===Brent's algorithm=== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="freebasic">' version 11-01-2017 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 1,048: | Line 1,048: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> Brent's algorithm |
<pre> Brent's algorithm |
||
Line 1,057: | Line 1,057: | ||
===Tortoise and hare. Floyd's algorithm=== |
===Tortoise and hare. Floyd's algorithm=== |
||
{{trans|Wikipedia}} |
{{trans|Wikipedia}} |
||
< |
<syntaxhighlight lang="freebasic">' version 11-01-2017 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 1,137: | Line 1,137: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
Line 1,144: | Line 1,144: | ||
Run it on the [https://play.golang.org/p/unOtxuwZfg go playground], or on [https://goplay.space/#S1pQZSuJci go play space]. |
Run it on the [https://play.golang.org/p/unOtxuwZfg go playground], or on [https://goplay.space/#S1pQZSuJci go play space]. |
||
<syntaxhighlight lang="go"> |
|||
<lang Go> |
|||
package main |
package main |
||
Line 1,202: | Line 1,202: | ||
} |
} |
||
fmt.Println("Cycle:", a[µ:µ+λ]) |
fmt.Println("Cycle:", a[µ:µ+λ]) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,211: | Line 1,211: | ||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="groovy">import java.util.function.IntUnaryOperator |
||
class CycleDetection { |
class CycleDetection { |
||
Line 1,259: | Line 1,259: | ||
println() |
println() |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Cycle length: 6 |
<pre>Cycle length: 6 |
||
Line 1,270: | Line 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. |
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. |
||
< |
<syntaxhighlight lang="haskell">import Data.List (findIndex) |
||
findCycle :: Eq a => [a] -> Maybe ([a], Int, Int) |
findCycle :: Eq a => [a] -> Maybe ([a], Int, Int) |
||
Line 1,287: | Line 1,287: | ||
| pow == lam = loop (2*pow) 1 y ys |
| pow == lam = loop (2*pow) 1 y ys |
||
| otherwise = loop pow (1+lam) x ys |
| otherwise = loop pow (1+lam) x ys |
||
in loop 1 1 x xs</ |
in loop 1 1 x xs</syntaxhighlight> |
||
'''Examples''' |
'''Examples''' |
||
Line 1,316: | Line 1,316: | ||
Brute force implementation: |
Brute force implementation: |
||
< |
<syntaxhighlight lang="j">cdetect=:1 :0 |
||
r=. ~.@(,u@{:)^:_ y |
r=. ~.@(,u@{:)^:_ y |
||
n=. u{:r |
n=. u{:r |
||
(,(#r)-])r i. n |
(,(#r)-])r i. n |
||
)</ |
)</syntaxhighlight> |
||
In other words: iterate until we stop getting new values, find the repeated value, and see how it fits into the sequence. |
In other words: iterate until we stop getting new values, find the repeated value, and see how it fits into the sequence. |
||
Line 1,326: | Line 1,326: | ||
Example use: |
Example use: |
||
< |
<syntaxhighlight lang="j"> 255&|@(1 0 1&p.) cdetect 3 |
||
2 6</ |
2 6</syntaxhighlight> |
||
(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.) |
(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 1,333: | Line 1,333: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{works with|Java|8}} |
{{works with|Java|8}} |
||
< |
<syntaxhighlight lang="java">import java.util.function.*; |
||
import static java.util.stream.IntStream.*; |
import static java.util.stream.IntStream.*; |
||
Line 1,375: | Line 1,375: | ||
.forEach(n -> System.out.printf("%s ", n)); |
.forEach(n -> System.out.printf("%s ", n)); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
<pre>Cycle length: 6 |
<pre>Cycle length: 6 |
||
Line 1,384: | Line 1,384: | ||
{{works with|jq}} |
{{works with|jq}} |
||
'''Works with gojq, the Go implementation of jq''' |
'''Works with gojq, the Go implementation of jq''' |
||
< |
<syntaxhighlight lang="jq">def floyd(f; x0): |
||
{tort: (x0|f)} |
{tort: (x0|f)} |
||
| .hare = (.tort|f) |
| .hare = (.tort|f) |
||
Line 1,411: | Line 1,411: | ||
"Cycle:", |
"Cycle:", |
||
skip(.mu; limit((.lambda + .mu); 3 | recurse(f))); |
skip(.mu; limit((.lambda + .mu); 3 | recurse(f))); |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''The specific function and task''' |
'''The specific function and task''' |
||
<syntaxhighlight lang="jq"> |
|||
<lang jq> |
|||
def f: (.*. + 1) % 255; |
def f: (.*. + 1) % 255; |
||
task(f;3) |
task(f;3) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,440: | Line 1,440: | ||
Following the Wikipedia article: |
Following the Wikipedia article: |
||
< |
<syntaxhighlight lang="julia">using IterTools |
||
function floyd(f, x0) |
function floyd(f, x0) |
||
Line 1,475: | Line 1,475: | ||
x -> Iterators.take(x, λ) |> |
x -> Iterators.take(x, λ) |> |
||
collect |
collect |
||
println("Cycle length: ", λ, "\nCycle start index: ", μ, "\nCycle: ", join(cycle, ", "))</ |
println("Cycle length: ", λ, "\nCycle start index: ", μ, "\nCycle: ", join(cycle, ", "))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,483: | Line 1,483: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.1.2 |
||
typealias IntToInt = (Int) -> Int |
typealias IntToInt = (Int) -> Int |
||
Line 1,531: | Line 1,531: | ||
println("Start index = $mu") |
println("Start index = $mu") |
||
println("Cycle = $cycle") |
println("Cycle = $cycle") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,543: | Line 1,543: | ||
=={{header|Lua}}== |
=={{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. |
Fairly direct translation of the Wikipedia code, except that the sequence is stored in a table and passed back as a third return value. |
||
< |
<syntaxhighlight lang="lua">function brent (f, x0) |
||
local tortoise, hare, mu = x0, f(x0), 0 |
local tortoise, hare, mu = x0, f(x0), 0 |
||
local cycleTab, power, lam = {tortoise, hare}, 1, 1 |
local cycleTab, power, lam = {tortoise, hare}, 1, 1 |
||
Line 1,571: | Line 1,571: | ||
print("Sequence:", table.concat(sequence, " ")) |
print("Sequence:", table.concat(sequence, " ")) |
||
print("Cycle length:", cycleLength) |
print("Cycle length:", cycleLength) |
||
print("Start Index:", startIndex)</ |
print("Start Index:", startIndex)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Sequence: 3 10 101 2 5 26 167 95 101 2 5 26 167 95 |
<pre>Sequence: 3 10 101 2 5 26 167 95 101 2 5 26 167 95 |
||
Line 1,578: | Line 1,578: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{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, |
26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, |
||
2, 5, 26, 167, 95, 101, 2, 5}; |
2, 5, 26, 167, 95, 101, 2, 5}; |
||
{transient, repeat} = FindTransientRepeat[s, 2]; |
{transient, repeat} = FindTransientRepeat[s, 2]; |
||
Print["Starting index: ", Length[transient] + 1] |
Print["Starting index: ", Length[transient] + 1] |
||
Print["Cycles: ", Floor[(Length[s] - Length[transient])/Length[repeat]]]</ |
Print["Cycles: ", Floor[(Length[s] - Length[transient])/Length[repeat]]]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Starting index: 3 |
<pre>Starting index: 3 |
||
Line 1,590: | Line 1,590: | ||
=={{header|Modula-2}}== |
=={{header|Modula-2}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="modula2">MODULE CycleDetection; |
||
FROM FormatString IMPORT FormatString; |
FROM FormatString IMPORT FormatString; |
||
FROM Terminal IMPORT WriteString,WriteLn,ReadChar; |
FROM Terminal IMPORT WriteString,WriteLn,ReadChar; |
||
Line 1,685: | Line 1,685: | ||
ReadChar |
ReadChar |
||
END CycleDetection.</ |
END CycleDetection.</syntaxhighlight> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
Translation of Wikipedia Python program. |
Translation of Wikipedia Python program. |
||
< |
<syntaxhighlight lang="nim">import strutils, sugar |
||
Line 1,739: | Line 1,739: | ||
if i >= μ: cycle.add x |
if i >= μ: cycle.add x |
||
x = f(x) |
x = f(x) |
||
echo "Cycle: ", cycle.join(" ")</ |
echo "Cycle: ", cycle.join(" ")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,747: | Line 1,747: | ||
=={{header|ooRexx}}== |
=={{header|ooRexx}}== |
||
< |
<syntaxhighlight lang="oorexx">/* REXX */ |
||
x=3 |
x=3 |
||
list=x |
list=x |
||
Line 1,764: | Line 1,764: | ||
End |
End |
||
Exit |
Exit |
||
f: Return (arg(1)**2+1)//255 </ |
f: Return (arg(1)**2+1)//255 </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,775: | Line 1,775: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="perl">use utf8; |
||
sub cyclical_function { ($_[0] * $_[0] + 1) % 255 } |
sub cyclical_function { ($_[0] * $_[0] + 1) % 255 } |
||
Line 1,823: | Line 1,823: | ||
print "Cycle length $l\n"; |
print "Cycle length $l\n"; |
||
print "Cycle start index $s\n"; |
print "Cycle start index $s\n"; |
||
print show_range($s,$s+$l-1) . "\n";</ |
print show_range($s,$s+$l-1) . "\n";</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 |
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 |
||
Line 1,832: | Line 1,832: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Translation of the Wikipedia code, but using the more descriptive len and pos, instead of lambda and mu, and adding a limit. |
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;">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;">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> |
||
Line 1,884: | Line 1,884: | ||
<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: #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> |
<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}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,895: | Line 1,895: | ||
=={{header|PL/M}}== |
=={{header|PL/M}}== |
||
< |
<syntaxhighlight lang="plm">100H: |
||
/* CP/M CALLS */ |
/* CP/M CALLS */ |
||
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS; |
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS; |
||
Line 1,992: | Line 1,992: | ||
CALL PRINT$RANGE(.F$ADDR, 3, MU, MU+LAM); |
CALL PRINT$RANGE(.F$ADDR, 3, MU, MU+LAM); |
||
CALL EXIT; |
CALL EXIT; |
||
EOF</ |
EOF</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 |
<pre>3 10 101 2 5 26 167 95 101 2 5 26 167 95 101 2 5 26 167 95 |
||
Line 2,001: | Line 2,001: | ||
===Procedural=== |
===Procedural=== |
||
Function from the Wikipedia article: |
Function from the Wikipedia article: |
||
< |
<syntaxhighlight lang="python">import itertools |
||
def brent(f, x0): |
def brent(f, x0): |
||
Line 2,043: | Line 2,043: | ||
print("Cycle length: %d" % lam) |
print("Cycle length: %d" % lam) |
||
print("Cycle start index: %d" % mu) |
print("Cycle start index: %d" % mu) |
||
print("Cycle: %s" % list(itertools.islice(iterate(f, x0), mu, mu+lam)))</ |
print("Cycle: %s" % list(itertools.islice(iterate(f, x0), mu, mu+lam)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,052: | Line 2,052: | ||
A modified version of the above where the first stage is restructured for clarity: |
A modified version of the above where the first stage is restructured for clarity: |
||
< |
<syntaxhighlight lang="python">import itertools |
||
def brent_length(f, x0): |
def brent_length(f, x0): |
||
Line 2,097: | Line 2,097: | ||
print("Cycle length: %d" % lam) |
print("Cycle length: %d" % lam) |
||
print("Cycle start index: %d" % mu) |
print("Cycle start index: %d" % mu) |
||
print("Cycle: %s" % list(itertools.islice(iterate(f, x0), mu, mu+lam)))</ |
print("Cycle: %s" % list(itertools.islice(iterate(f, x0), mu, mu+lam)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Cycle length: 6 |
<pre>Cycle length: 6 |
||
Line 2,107: | Line 2,107: | ||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
< |
<syntaxhighlight lang="python">'''Cycle detection by recursion.''' |
||
from itertools import (chain, cycle, islice) |
from itertools import (chain, cycle, islice) |
||
Line 2,340: | Line 2,340: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>First cycle detected, if any: |
<pre>First cycle detected, if any: |
||
Line 2,354: | Line 2,354: | ||
Recursive ''until'': |
Recursive ''until'': |
||
< |
<syntaxhighlight lang="python"># until :: (a -> Bool) -> (a -> a) -> a -> a |
||
def until(p): |
def until(p): |
||
'''The result of repeatedly applying f until p holds. |
'''The result of repeatedly applying f until p holds. |
||
Line 2,360: | Line 2,360: | ||
def go(f, x): |
def go(f, x): |
||
return x if p(x) else go(f, f(x)) |
return x if p(x) else go(f, f(x)) |
||
return lambda f: lambda x: go(f, x)</ |
return lambda f: lambda x: go(f, x)</syntaxhighlight> |
||
''cycleLength'' refactored in terms of ''until'': |
''cycleLength'' refactored in terms of ''until'': |
||
< |
<syntaxhighlight lang="python"># cycleLength :: Eq a => [a] -> Maybe Int |
||
def cycleLength(xs): |
def cycleLength(xs): |
||
'''Just the length of the first cycle found, |
'''Just the length of the first cycle found, |
||
Line 2,389: | Line 2,389: | ||
) if ys else Nothing() |
) if ys else Nothing() |
||
else: |
else: |
||
return Nothing()</ |
return Nothing()</syntaxhighlight> |
||
Iterative reimplementation of ''until'': |
Iterative reimplementation of ''until'': |
||
< |
<syntaxhighlight lang="python"># until_ :: (a -> Bool) -> (a -> a) -> a -> a |
||
def until_(p): |
def until_(p): |
||
'''The result of repeatedly applying f until p holds. |
'''The result of repeatedly applying f until p holds. |
||
Line 2,401: | Line 2,401: | ||
v = f(v) |
v = f(v) |
||
return v |
return v |
||
return lambda f: lambda x: go(f, x)</ |
return lambda f: lambda x: go(f, x)</syntaxhighlight> |
||
Line 2,407: | Line 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: |
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}} |
{{Works with|Python|3.7}} |
||
< |
<syntaxhighlight lang="python">'''Cycle detection without recursion.''' |
||
from itertools import (chain, cycle, islice) |
from itertools import (chain, cycle, islice) |
||
Line 2,662: | Line 2,662: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>First cycle detected, if any: |
<pre>First cycle detected, if any: |
||
Line 2,674: | Line 2,674: | ||
=={{header|Quackery}}== |
=={{header|Quackery}}== |
||
< |
<syntaxhighlight lang="quackery"> [ stack ] is fun ( --> s ) |
||
[ stack ] is pow ( --> s ) |
[ stack ] is pow ( --> s ) |
||
[ stack ] is len ( --> s ) |
[ stack ] is len ( --> s ) |
||
Line 2,724: | Line 2,724: | ||
echo ] is task ( n x --> ) |
echo ] is task ( n x --> ) |
||
3 ' [ 2 ** 1+ 255 mod ] task</ |
3 ' [ 2 ** 1+ 255 mod ] task</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,737: | Line 2,737: | ||
I feel a bit bad about overloading λ, but it’s in the spirit of the algorithm. |
I feel a bit bad about overloading λ, but it’s in the spirit of the algorithm. |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket/base |
#lang racket/base |
||
Line 2,776: | Line 2,776: | ||
(let-values (([µ λ] (brent f 3))) |
(let-values (([µ λ] (brent f 3))) |
||
(printf "Cycle length = ~a~%Start Index = ~a~%" µ λ))) |
(printf "Cycle length = ~a~%Start Index = ~a~%" µ λ))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 2,790: | Line 2,790: | ||
Pretty much a line for line translation of the Python code on the Wikipedia page. |
Pretty much a line for line translation of the Python code on the Wikipedia page. |
||
<lang |
<syntaxhighlight lang="raku" line>sub cyclical-function (\x) { (x * x + 1) % 255 }; |
||
my ( $l, $s ) = brent( &cyclical-function, 3 ); |
my ( $l, $s ) = brent( &cyclical-function, 3 ); |
||
Line 2,823: | Line 2,823: | ||
} |
} |
||
return $λ, $μ; |
return $λ, $μ; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, ... |
<pre>3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, ... |
||
Line 2,832: | Line 2,832: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===Brent's algorithm=== |
===Brent's algorithm=== |
||
< |
<syntaxhighlight lang="rexx">/*REXX program detects a cycle in an iterated function [F] using Brent's algorithm. */ |
||
init= 3; $= init |
init= 3; $= init |
||
do until length($)>79; $= $ f( word($, words($) ) ) |
do until length($)>79; $= $ f( word($, words($) ) ) |
||
Line 2,865: | Line 2,865: | ||
return # mu |
return # mu |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
f: return ( arg(1) **2 + 1) // 255 /*this defines/executes the function F.*/</ |
f: return ( arg(1) **2 + 1) // 255 /*this defines/executes the function F.*/</syntaxhighlight> |
||
{{out|output|text= when using the defaults:}} |
{{out|output|text= when using the defaults:}} |
||
<pre> |
<pre> |
||
Line 2,876: | Line 2,876: | ||
===sequential search algorithm=== |
===sequential search algorithm=== |
||
< |
<syntaxhighlight lang="rexx">/*REXX program detects a cycle in an iterated function [F] using a sequential search. */ |
||
x= 3; $= x /*initial couple of variables*/ |
x= 3; $= x /*initial couple of variables*/ |
||
do until cycle\==0; x= f(x) /*calculate another number. */ |
do until cycle\==0; x= f(x) /*calculate another number. */ |
||
Line 2,889: | Line 2,889: | ||
exit /*stick a fork in it, we're all done. */ |
exit /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
f: return ( arg(1) **2 + 1) // 255 /*this defines/executes the function F.*/</ |
f: return ( arg(1) **2 + 1) // 255 /*this defines/executes the function F.*/</syntaxhighlight> |
||
{{out|output|:}} |
{{out|output|:}} |
||
<pre> |
<pre> |
||
Line 2,901: | Line 2,901: | ||
===hash table algorithm=== |
===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. |
This REXX version is a lot faster (than the sequential search algorithm) if the ''cycle length'' and/or ''start index'' is large. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program detects a cycle in an iterated function [F] using a hash table. */ |
||
!.= .; !.x= 1; x= 3; $= x /*assign initial value. */ |
!.= .; !.x= 1; x= 3; $= x /*assign initial value. */ |
||
do #=1+words($); x= f(x); $= $ x /*add the number to list.*/ |
do #=1+words($); x= f(x); $= $ x /*add the number to list.*/ |
||
Line 2,914: | Line 2,914: | ||
exit /*stick a fork in it, we're all done. */ |
exit /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
f: return ( arg(1) **2 + 1) // 255 /*this defines/executes the function F.*/</ |
f: return ( arg(1) **2 + 1) // 255 /*this defines/executes the function F.*/</syntaxhighlight> |
||
{{out|output|text= is identical to the 2<sup>nd</sup> REXX version.}} <br><br> |
{{out|output|text= is identical to the 2<sup>nd</sup> REXX version.}} <br><br> |
||
Line 2,927: | Line 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>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. |
<br>generates a cyclic sequence that contains over 1.5 million numbers. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program detects a cycle in an iterated function [F] using a robust hashing. */ |
||
parse arg power . /*obtain optional args from C.L. */ |
parse arg power . /*obtain optional args from C.L. */ |
||
if power=='' | power="," then power=8 /*Not specified? Use the default*/ |
if power=='' | power="," then power=8 /*Not specified? Use the default*/ |
||
Line 2,951: | Line 2,951: | ||
exit /*stick a fork in it, we're all done. */ |
exit /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
f: return ( arg(1) **2 + 1) // 255 /*this defines/executes the function F.*/</ |
f: return ( arg(1) **2 + 1) // 255 /*this defines/executes the function F.*/</syntaxhighlight> |
||
{{out|output|text= when the input (power of two) used is: <tt> 49 </tt>}} |
{{out|output|text= when the input (power of two) used is: <tt> 49 </tt>}} |
||
<pre> |
<pre> |
||
Line 2,967: | Line 2,967: | ||
There is more information in the "hash table"<br> |
There is more information in the "hash table"<br> |
||
and f has no "side effect". |
and f has no "side effect". |
||
< |
<syntaxhighlight lang="rexx">/*REXX pgm detects a cycle in an iterated function [F] */ |
||
x=3; list=x; p.=0; p.x=1 |
x=3; list=x; p.=0; p.x=1 |
||
Do q=2 By 1 |
Do q=2 By 1 |
||
Line 2,984: | Line 2,984: | ||
Exit |
Exit |
||
/*-------------------------------------------------------------------*/ |
/*-------------------------------------------------------------------*/ |
||
f: Return (arg(1)**2+1)// 255; /*define the function F*/</ |
f: Return (arg(1)**2+1)// 255; /*define the function F*/</syntaxhighlight> |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
{{works with|ruby|2.0}} |
{{works with|ruby|2.0}} |
||
< |
<syntaxhighlight lang="ruby"># Author: Paul Anton Chernoch |
||
# Purpose: |
# Purpose: |
||
# Find the cycle length and start position of a numerical seried using Brent's cycle algorithm. |
# Find the cycle length and start position of a numerical seried using Brent's cycle algorithm. |
||
Line 3,046: | Line 3,046: | ||
# Test the findCycle function |
# Test the findCycle function |
||
clength, cstart = findCycle(3) { |x| f(x) } |
clength, cstart = findCycle(3) { |x| f(x) } |
||
puts "Cycle length = #{clength}\nStart index = #{cstart}"</ |
puts "Cycle length = #{clength}\nStart index = #{cstart}"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,058: | Line 3,058: | ||
=== Procedural === |
=== 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)]. |
{{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)]. |
||
< |
<syntaxhighlight lang="scala">object CycleDetection extends App { |
||
def brent(f: Int => Int, x0: Int): (Int, Int) = { |
def brent(f: Int => Int, x0: Int): (Int, Int) = { |
||
Line 3,102: | Line 3,102: | ||
println(s"Cycle = ${cycle.force}") |
println(s"Cycle = ${cycle.force}") |
||
}</ |
}</syntaxhighlight> |
||
=== Functional === |
=== Functional === |
||
<syntaxhighlight lang="scala"> |
|||
<lang Scala> |
|||
import scala.annotation.tailrec |
import scala.annotation.tailrec |
||
Line 3,168: | Line 3,168: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 3,179: | Line 3,179: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="ruby">func brent (f, x0) { |
||
var power = 1 |
var power = 1 |
||
var λ = 1 |
var λ = 1 |
||
Line 3,222: | Line 3,222: | ||
say "Cycle length #{l}."; |
say "Cycle length #{l}."; |
||
say "Cycle start index #{s}." |
say "Cycle start index #{s}." |
||
say [seq[s .. (s + l - 1)]]</ |
say [seq[s .. (s + l - 1)]]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, ... |
<pre>3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, ... |
||
Line 3,231: | Line 3,231: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="vbnet">Module Module1 |
||
Function FindCycle(Of T As IEquatable(Of T))(x0 As T, yielder As Func(Of T, T)) As Tuple(Of Integer, Integer) |
Function FindCycle(Of T As IEquatable(Of T))(x0 As T, yielder As Func(Of T, T)) As Tuple(Of Integer, Integer) |
||
Line 3,289: | Line 3,289: | ||
End Sub |
End Sub |
||
End Module</ |
End Module</syntaxhighlight> |
||
{{out}} |
{{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 |
<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 3,297: | Line 3,297: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
Working from the code in the Wikipedia article: |
Working from the code in the Wikipedia article: |
||
< |
<syntaxhighlight lang="ecmascript">var brent = Fn.new { |f, x0| |
||
var lam = 1 |
var lam = 1 |
||
var power = 1 |
var power = 1 |
||
Line 3,336: | Line 3,336: | ||
System.print("Cycle length = %(lam)") |
System.print("Cycle length = %(lam)") |
||
System.print("Start index = %(mu)") |
System.print("Start index = %(mu)") |
||
System.print("Cycle = %(seq[mu...mu+lam])")</ |
System.print("Cycle = %(seq[mu...mu+lam])")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,348: | Line 3,348: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
Algorithm from the Wikipedia |
Algorithm from the Wikipedia |
||
< |
<syntaxhighlight lang="zkl">fcn cycleDetection(f,x0){ // f(int), x0 is the integer starting value of the sequence |
||
# main phase: search successive powers of two |
# main phase: search successive powers of two |
||
power:=lam:=1; |
power:=lam:=1; |
||
Line 3,370: | Line 3,370: | ||
} |
} |
||
return(lam,mu); |
return(lam,mu); |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">cycleDetection(fcn(x){ (x*x + 1)%255 }, 3).println(" == cycle length, start index");</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |