77 lines
1.7 KiB
Text
77 lines
1.7 KiB
Text
include "cowgol.coh";
|
|
|
|
# Redefining these is enough to change the type and length everywhere,
|
|
# but arrays are 0-based so you need one extra element.
|
|
typedef Stern is uint8; # 8-bit math is enough for the numbers we need
|
|
var stern: Stern[1201]; # Array containing Stern-Brocot sequence
|
|
|
|
# Fill up the Stern-Brocot array
|
|
sub GenStern() is
|
|
stern[1] := 1;
|
|
stern[2] := 1;
|
|
|
|
var i: @indexof stern := 1;
|
|
var last: @indexof stern := @sizeof stern / 2;
|
|
while i <= last loop
|
|
stern[i*2-1] := stern[i] + stern[i-1];
|
|
stern[i*2] := stern[i];
|
|
i := i + 1;
|
|
end loop;
|
|
end sub;
|
|
|
|
# Find the first location of a given number
|
|
sub FindFirst(n: Stern): (i: @indexof stern) is
|
|
i := 1;
|
|
while i < @sizeof stern and stern[i] != n loop
|
|
i := i + 1;
|
|
end loop;
|
|
end sub;
|
|
|
|
GenStern(); # Generate sequence
|
|
|
|
# Print the first 15 numbers
|
|
var i: @indexof stern := 1;
|
|
while i <= 15 loop
|
|
print_i32(stern[i] as uint32);
|
|
print_char(' ');
|
|
i := i + 1;
|
|
end loop;
|
|
print_nl();
|
|
|
|
# Print the first occurrence of 1..10
|
|
var j: Stern := 1;
|
|
while j <= 10 loop
|
|
print_i32(FindFirst(j) as uint32);
|
|
print_char(' ');
|
|
j := j + 1;
|
|
end loop;
|
|
print_nl();
|
|
|
|
# Print the first occurrence of 100
|
|
print_i32(FindFirst(100) as uint32);
|
|
print_nl();
|
|
|
|
# Check that all GCDs of consecutive pairs are 1
|
|
sub gcd(a: Stern, b: Stern): (r: Stern) is
|
|
while a != b loop
|
|
if a > b then
|
|
a := a - b;
|
|
else
|
|
b := b - a;
|
|
end if;
|
|
end loop;
|
|
r := a;
|
|
end sub;
|
|
|
|
i := 1;
|
|
while i < @sizeof stern / 2 loop
|
|
if gcd(stern[i], stern[i+1]) != 1 then
|
|
print("GCD not 1 at: ");
|
|
print_i32(i as uint32);
|
|
print_nl();
|
|
ExitWithError();
|
|
end if;
|
|
i := i + 1;
|
|
end loop;
|
|
|
|
print("All GCDs are 1.\n");
|