Fibonacci word: Difference between revisions
Added Easylang
(Added Easylang) |
|||
| (5 intermediate revisions by 5 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 4,495 ⟶ 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,674 ⟶ 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|
| |||