Cycle detection: Difference between revisions
Add Cowgol
(→{{header|Ada}}: Ada implementation) |
Not a robot (talk | contribs) (Add Cowgol) |
||
Line 399:
}
}</lang>
=={{header|Cowgol}}==
<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);</lang>
{{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}}==
| |||