Anonymous user
Cycle detection: Difference between revisions
m
→{{header|REXX}}: added/changed whitespace and comments, used a template for an output section, simplified some programs.
m (→{{header|REXX}}: added/changed whitespace and comments, used a template for an output section, simplified some programs.) |
|||
Line 2,002:
===Brent's algorithm===
<lang rexx>/*REXX program detects a cycle in an iterated function [F] using Brent's algorithm. */
init= 3;
do until length(
end /*until*/
say ' original list='
call Brent init /*invoke Brent algorithm for F*/
parse var result cycle idx /*get 2 values returned from F*/
say 'numbers in list=' words(
say ' cycle length =' cycle /*display the cycle to term*/
say ' start index =' idx " ◄─── zero index" /* " " index " " */
say 'cycle sequence =' subword(
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
Line 2,022:
end
hare= f(hare)
#= # +
end /*while*/
hare= x0
Line 2,035:
/*──────────────────────────────────────────────────────────────────────────────────────*/
f: return ( arg(1) **2 + 1) // 255 /*this defines/executes the function F.*/</lang>
<pre>
original list= 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 ...
Line 2,046:
===sequential search algorithm===
<lang rexx>/*REXX program detects a cycle in an iterated function [F] using a sequential search. */
x= 3;
do until cycle\==0; x= f(x)
cycle= wordpos(x,
end /*until*/
say 'numbers
say '
say ' cycle length =' # /*display the cycle to term*/▼
say ' start index =' cycle - 1 " ◄─── zero based" /* " " index " " */
say 'cycle sequence =' subword(
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
Line 2,071 ⟶ 2,070:
===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.
<lang rexx>/*REXX program detects a cycle in an iterated function [F] using a hash table.
do
if !.x\==. then leave /*A repeat? Then leave.
!.x=
end /*
say ' original list='
say 'numbers in list='
say ' cycle length ='
say ' start index =' !.x - 1
say 'cycle sequence =' subword(
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
Line 2,106 ⟶ 2,105:
say ' divisor =' "{2**"power'}-1 = ' divisor /* " " divisor. " " " */
say
x=3;
do n=1+words(
if n//2000==0 then do;
if !.x\==. then leave /*is this number a repeat? Leave*/
!.x= n
end /*n*/ /*N: is the size of
if n<m then say ' original list='
say 'numbers in list=' n /*display number of numbers. */
say ' cycle length =' n - !.x /*display the cycle to the term. */
say ' start index =' !.x - 1 " ◄─── zero based" /*show the index.*/
if n<m then say 'cycle sequence =' subword(
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
| |||