Fibonacci word: Difference between revisions
Added Easylang
(Added Easylang) |
|||
| (6 intermediate revisions by 6 users not shown) | |||
Line 1:
{{task}}
[[File:Fibonacci word cutting sequence.png|thumb|Fibonacci word.]]
The Fibonacci Word may be created in a manner analogous to the Fibonacci Sequence [http://hal.archives-ouvertes.fr/docs/00/36/79/72/PDF/The_Fibonacci_word_fractal.pdf as described here]:
Line 1,204:
36 14930352 0.9594187282227428063 <too long>
37 24157817 0.9594187282227447312 <too long></pre>
=={{header|Dart}}==
{{trans|Java}}
<syntaxhighlight lang="Dart">
import 'dart:math';
class FWord {
String fWord0 = "";
String fWord1 = "";
String nextFWord() {
String result;
if (fWord1 == "") {
result = "1";
} else if (fWord0 == "") {
result = "0";
} else {
result = fWord1 + fWord0;
}
fWord0 = fWord1;
fWord1 = result;
return result;
}
static double entropy(String source) {
int length = source.length;
var counts = <String, int>{};
double result = 0.0;
for (int i = 0; i < length; i++) {
String c = source[i];
if (counts.containsKey(c)) {
counts[c] = counts[c] + 1;
} else {
counts[c] = 1;
}
}
counts.values.forEach((count) {
double proportion = count / length;
result -= proportion * (log(proportion) / log(2));
});
return result;
}
static void main() {
FWord fWord = FWord();
for (int i = 0; i < 37;) {
String word = fWord.nextFWord();
print("${++i} ${word.length} ${entropy(word)}");
}
}
}
void main() {
FWord.main();
}
</syntaxhighlight>
{{out}}
<pre>
1 1 0.0
2 1 0.0
3 2 1.0
4 3 0.9182958340544896
5 5 0.9709505944546686
6 8 0.9544340029249649
7 13 0.961236604722876
8 21 0.9587118829771318
9 34 0.9596868937742169
10 55 0.9593160320543777
11 89 0.9594579158386696
12 144 0.959403754221023
13 233 0.9594244469559867
14 377 0.9594165437404407
15 610 0.9594195626031441
16 987 0.9594184095152245
17 1597 0.9594188499578099
18 2584 0.9594186817240321
19 4181 0.9594187459836638
20 6765 0.9594187214386756
21 10946 0.9594187308140278
22 17711 0.959418727232962
23 28657 0.9594187286008073
24 46368 0.9594187280783371
25 75025 0.9594187282779029
26 121393 0.9594187282016755
27 196418 0.9594187282307918
28 317811 0.9594187282196702
29 514229 0.9594187282239184
30 832040 0.9594187282222959
31 1346269 0.9594187282229156
32 2178309 0.9594187282226789
33 3524578 0.9594187282227691
34 5702887 0.9594187282227347
35 9227465 0.9594187282227479
36 14930352 0.9594187282227429
37 24157817 0.9594187282227448
</pre>
=={{header|Delphi}}==
See [[#Pascal]]
=={{header|EasyLang}}==
{{trans|Nim}}
<syntaxhighlight>
func log2 x .
return log10 x / log10 2
.
func entropy s$ .
l = len s$
if l <= 1
return 0
.
for v$ in strchars s$
cnt0 += if v$ = "0"
.
cnt1 = l - cnt0
return -(cnt0 / l * log2 (cnt0 / l) + cnt1 / l * log2 (cnt1 / l))
.
a$ = ""
b$ = ""
func$ fibword .
if a$ = ""
a$ = "1"
return a$
.
if b$ = ""
b$ = "0"
return b$
.
a$ = b$ & a$
swap a$ b$
return b$
.
numfmt 6 8
print " n length entropy"
print " ——————————————————————"
for n to 37
s$ = fibword
print n & " " & len s$ & " " & entropy s$
.
</syntaxhighlight>
=={{header|EchoLisp}}==
Line 1,582 ⟶ 1,730:
{{FormulaeEntry|page=https://formulae.org/?script=examples/Fibonacci_word}}
'''Solution'''
[[File:Fōrmulæ - Fibonacci word 01.png]]
'''Example'''
[[File:Fōrmulæ - Fibonacci word 02.png]]
[[File:Fōrmulæ - Fibonacci word 03.png]]
'''Table of Fibonacci word lengths and entropies'''
It is not necessary to calculate the actual values for the Fibonacci words in each step.
Because the generation of a new word is the concatenation of the two previous words, its length is the sum of the two previous lengths. They are Fibonacci numbers.
For the same reason (concatenation), the number of zeros of a new word is the sum of the number of zeros of the two previous words. The same happens to ones.
The following table shows the length, the number of zeros and the number of ones of a sequence of Fibonacci words. Notice that all of them are Fibonacci sequences.
[[File:Fōrmulæ - Fibonacci word 04.png]]
[[File:Fōrmulæ - Fibonacci word 05.png]]
Also notice that:
* The number of zeros of the i-th word is the length of the (i - 1)-th word.
* The number of ones of the i-th word is the length of the (i - 2)-th word.
Since we only need the number of zeros and ones of a given Fibonacci word in order to calculate its entropy, the actual word is not necessary:
[[File:Fōrmulæ - Fibonacci word 06.png]]
[[File:Fōrmulæ - Fibonacci word 07.png]]
'''Limit of the entropy'''
Given that the entropy of the i-th Fibonacci word is:
<math display="block"> - \left( \frac{zeroes_i}{zeroes_i + ones_i} \lg \left( \frac{zeroes_i}{zeroes_i + ones_i} \right) + \frac{ones_i}{zeroes_i + ones_i} \lg \left( \frac{ones_i}{zeroes_i + ones_i} \right) \right)</math>
<math display="block"> - \left( \frac{F_{i-1}}{F_i} \lg \left( \frac{F_{i-1}}{F_i} \right) + \frac{F_{i-2}}{F_i} \lg \left( \frac{F_{i-2}}{F_i} \right) \right)</math>
<math display="block"> - \left( \frac{F_{i-1}}{F_i} \lg \left( \frac{F_{i-1}}{F_i} \right) + \frac{F_{i-2}}{F_{i-1}} \frac{F_{i-1}}{F_i} \lg \left( \frac{F_{i-2}}{F_{i-1}} \frac{F_{i-1}}{F_i} \right) \right)</math>
Because the ratio between a Fibonacci term over the next term is <math>\frac{1}{\varphi}</math> as i is bigger, the previous expression tends to be:
<math display="block"> - \left( \frac{1}{\varphi} \lg \left( \frac{1}{\varphi} \right) + \frac{1}{\varphi} \frac{1}{\varphi} \lg \left( \frac{1}{\varphi} \frac{1}{\varphi} \right) \right)</math>
<math display="block"> - \left( \frac{1}{\varphi} \lg \left( \frac{1}{\varphi} \right) + \frac{1}{\varphi^2} \lg \left( \frac{1}{\varphi^2} \right) \right)</math>
This value, with a precision of 100 digits is:
[[File:Fōrmulæ - Fibonacci word 08.png]]
[[File:Fōrmulæ - Fibonacci word 09.png]]
=={{header|Go}}==
Line 4,438 ⟶ 4,643:
</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program fibonacci_words;
print("N Length Entropy");
print("---- ---------- -------------------");
loop for n in [1..37] do
[zeroes, ones] := fibword := fib_word n;
length := zeroes + ones;
print(lpad(str n,4) + " " + lpad(str length,10) + " " + str entropy fibword);
end loop;
$ Return the amount of zeroes and ones in the N'th fibonacci word
op fib_word(n);
[a0, a1, b0, b1] := [0, 1, 1, 0];
loop for i in [2..n] do
[a0, a1, b0, b1] := [b0, b1, a0+b0, a1+b1];
end loop;
return [a0, a1];
end op;
op entropy(fibword);
[zeroes, ones] := fibword;
fzeroes := zeroes / (zeroes + ones);
fones := ones / (zeroes + ones);
if fzeroes = 0 or fones = 0 then
return 0;
end if;
return -fzeroes*log fzeroes/log 2 - fones*log fones/log 2;
end op;
end program;</syntaxhighlight>
{{out}}
<pre>N Length Entropy
---- ---------- -------------------
1 1 0
2 1 0
3 2 1
4 3 0.91829583405449
5 5 0.970950594454669
6 8 0.954434002924965
7 13 0.961236604722876
8 21 0.958711882977132
9 34 0.959686893774217
10 55 0.959316032054378
11 89 0.95945791583867
12 144 0.959403754221023
13 233 0.959424446955987
14 377 0.959416543740441
15 610 0.959419562603144
16 987 0.959418409515225
17 1597 0.95941884995781
18 2584 0.959418681724032
19 4181 0.959418745983664
20 6765 0.959418721438675
21 10946 0.959418730814028
22 17711 0.959418727232962
23 28657 0.959418728600807
24 46368 0.959418728078337
25 75025 0.959418728277903
26 121393 0.959418728201676
27 196418 0.959418728230792
28 317811 0.95941872821967
29 514229 0.959418728223918
30 832040 0.959418728222296
31 1346269 0.959418728222916
32 2178309 0.959418728222679
33 3524578 0.959418728222769
34 5702887 0.959418728222735
35 9227465 0.959418728222748
36 14930352 0.959418728222743
37 24157817 0.959418728222745</pre>
=={{header|Sidef}}==
{{trans|Ruby}}
Line 4,617 ⟶ 4,893:
36 14930352 0.959418728222743 <too long>
37 24157817 0.959418728222745 <too long>
</pre>
=={{header|Uiua}}==
Memoisation saves the day :-)
<syntaxhighlight lang="Uiua">
# Build the string recursively.
F ← |1 memo⟨⟨⊂∩F-1.-1|"0"◌⟩=2.|"1"◌⟩=1.
# General entropy formula - quite slow for this task.
Egen ← /+(¯×ₙ2.)÷/+.≡(⧻⊚=)⊃◴¤
# Specific entropy formula for a binary string.
E ← ⍥(0◌)=NaN.+∩(¯×ₙ2.)⟜(¯-1)÷⊃⧻(⧻⊚="1")
# Much faster approach -- don't even build the string, just count
# how many "0"s and "1"s the string will have.
Fx ← |1 memo⟨⟨+∩Fx-1.-1|[1 0]◌⟩=2.|[0 1]◌⟩=1.
Ex ← ⍥(0◌)=NaN./+(¯×ₙ2.)÷/+.
# Print and time it
⍜now(≡(⇌[⊃/+ (⍜(×1e8)⁅Ex)Fx.])+1⇡37)
</syntaxhighlight>
{{out}}
<pre>
╭─
╷ 1 0 1
2 0 1
3 1 2
4 0.91829583 3
5 0.97095059 5
6 0.954434 8
7 0.9612366 13
8 0.95871188 21
9 0.95968689 34
10 0.95931603 55
...etc...
35 0.95941873 9227465
36 0.95941873 14930352
37 0.95941873 24157817
╯
0.0029999999678694-ε
</pre>
=={{header|Wren}}==
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
var entropy = Fn.new { |s|
| |||