118 lines
3.7 KiB
Text
118 lines
3.7 KiB
Text
# calculate some details of "Fibonacci Words" #
|
|
|
|
# fibonacci word 1 = "1" #
|
|
# fibonacci word 2 = "0" #
|
|
# 3 = word 2 cat word 1 = "01" #
|
|
# n = word n-1 cat word n-2 #
|
|
|
|
# note the words contain only the characters "0" and "1" #
|
|
# also #
|
|
# C(word n) = C(word n-1) + C(word n-2) #
|
|
# where C(x) = the number of characters in x #
|
|
# Similarly, #
|
|
# C0(word n) = C0(word n-1) + C0(word n-2) #
|
|
# and C1(word n) = C1(word n-1) + C1(word n-2) #
|
|
# where C0(x) = the number of "0"s in x and #
|
|
# C1(x) = the number of "1"s in x #
|
|
|
|
# we therefore don't have to calculate the words themselves #
|
|
|
|
|
|
# prints the statistics for the fibonacci words from 1 to max number #
|
|
PROC print fibonacci word stats = ( INT max number )VOID:
|
|
BEGIN
|
|
|
|
|
|
# prints some statistics for a fibonacci word: #
|
|
# the word number, its length and its entropy #
|
|
PROC print one words stats = ( INT word
|
|
, INT zeros
|
|
, INT ones
|
|
)VOID:
|
|
BEGIN
|
|
|
|
REAL probability := 0;
|
|
REAL entropy := 0;
|
|
INT word length = zeros + ones;
|
|
|
|
IF zeros > 0
|
|
THEN
|
|
# the word contains some zeros #
|
|
probability := zeros / word length;
|
|
entropy -:= probability * log( probability )
|
|
FI;
|
|
|
|
IF ones > 0
|
|
THEN
|
|
# the word contains some ones #
|
|
probability := ones / word length;
|
|
entropy -:= probability * log( probability )
|
|
FI;
|
|
|
|
# we want entropy in bits so convert to log base 2 #
|
|
entropy /:= log( 2 );
|
|
|
|
print( ( ( whole( word, -5 )
|
|
+ " "
|
|
+ whole( word length, -12 )
|
|
+ " "
|
|
+ fixed( entropy, -8, 4 )
|
|
)
|
|
, newline
|
|
)
|
|
)
|
|
|
|
|
|
END; # print one words stats #
|
|
|
|
|
|
INT zeros one = 0; # number of zeros in word 1 #
|
|
INT ones one = 1; # number of ones in word 1 #
|
|
INT zeros two = 1; # number of zeros in word 2 #
|
|
INT ones two = 0; # number of ones in word 2 #
|
|
|
|
print( ( " word length entropy", newline ) );
|
|
|
|
IF max number > 0
|
|
THEN
|
|
# we want at least one number's statistics #
|
|
print one words stats( 1, zeros one, ones one );
|
|
|
|
IF max number > 1
|
|
THEN
|
|
# we want at least 2 number's statistics #
|
|
print one words stats( 2, zeros two, ones two );
|
|
|
|
IF max number > 2
|
|
THEN
|
|
# we want more statistics #
|
|
|
|
INT zeros n minus 1 := zeros two;
|
|
INT ones n minus 1 := ones two;
|
|
INT zeros n minus 2 := zeros one;
|
|
INT ones n minus 2 := ones one;
|
|
|
|
FOR word FROM 3 TO max number DO
|
|
|
|
INT zeros n := zeros n minus 1 + zeros n minus 2;
|
|
INT ones n := ones n minus 1 + ones n minus 2;
|
|
|
|
print one words stats( word, zeros n, ones n );
|
|
|
|
zeros n minus 2 := zeros n minus 1;
|
|
ones n minus 2 := ones n minus 1;
|
|
zeros n minus 1 := zeros n;
|
|
ones n minus 1 := ones n
|
|
OD
|
|
FI
|
|
FI
|
|
FI
|
|
|
|
END; # print fibonacci word stats #
|
|
|
|
|
|
main:
|
|
(
|
|
# print the statistics for the first 37 fibonacci words #
|
|
print fibonacci word stats( 37 )
|
|
)
|