Fibonacci word: Difference between revisions

{{task}}

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]:

 

{{trans|Python}}

 

I s.len <= 1

R 0.0

fwords [+]= reversed(fwords[(len)-2..]).join(‘’)

V v = fwords[n - 1]

 

{{out}}

 

=={{header|Ada}}==

Ada.Strings.Unbounded.Text_IO, Ada.Numerics.Long_Elementary_Functions,

Ada.Long_Float_Text_IO;

end loop;

end Fibonacci_Words;

Output

<pre> N Length Entropy Word

 

=={{header|Aime}}==

entropy(data b)

{

 

return 0;

{{out}}

<pre> 1 1 0 1

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}

 

# fibonacci word 1 = "1" #

print fibonacci word stats( 37 )

)

{{out}}

<pre>

 

=={{header|APL}}==

F_WORD←{{⍵,,/⌽¯2↑⍵}⍣(0⌈⍺-2),¨⍵}

ENTROPY←{-+/R×2⍟R←(+⌿⍵∘.=∪⍵)÷⍴⍵}

FORMAT←{'N' 'LENGTH' 'ENTROPY'⍪(⍳⍵),↑{(⍴⍵),ENTROPY ⍵}¨⍵ F_WORD 1 0}

{{out}}

<pre>

37 24157817 0.9594187282

</pre>

 

=={{header|AutoHotkey}}==

SetBatchLines, -1

OutPut := "N`tLength`t`tEntropy`n"

}

return, e

'''Output:'''

<pre>N Length Entropy

 

=={{header|C}}==

#include <stdlib.h>

#include <string.h>

free(current_word);

return 0;

{{out}}

<pre> N Length Entropy Word

</pre>

 

using SCG = System.Collections.Generic;

 

}

}

{{out}}

<pre>N Length Entropy

 

=={{header|C++}}==

#include <map>

#include <iostream>

}

return 0 ;

{{out}}

<pre>N length entropy

 

=={{header|Clojure}}==

(let [len (count s), log-2 (Math/log 2)]

(->> (frequencies s)

(doseq [i (range 1 38)

w (take 37 (fibonacci str "1" "0"))]

 

Output

36 14930352 0,959418728222743 ...

37 24157817 0,959418728222745 ...</pre>

 

=={{header|Common Lisp}}==

(loop for i from 0 below 37

for j = "0" then (concatenate 'string j k)

for n = (aref *fib* i) do

(format t "~2D ~10D ~17,15F ~A~%"

 

=={{header|D}}==

 

real entropy(T)(T[] s) pure nothrow

s.dup.representation.entropy.abs,

s.length < 25 ? s : "<too long>");

{{out}}

<pre> N Length Entropy Fibword

36 14930352 0.9594187282227428063 <too long>

37 24157817 0.9594187282227447312 <too long></pre>

=={{header|Delphi}}==

See [[#Pascal]]

 

=={{header|EchoLisp}}==

(lib 'struct)

(struct FW ( count0 count1 length string)) ;; a fibonacci word

(printf "%3d %10d %24d %a"

i (FW-length fw) (entropy fw) (FW-string fw))))

{{out}}

<pre>

{{works with|Elixir|1.3}}

{{works with|Erlang/OTP|18}}

def entropy(str) do

leng = String.length(str)

str = if len < 60, do: word, else: "<too long>"

:io.format "~3w ~8w ~17.15f ~s~n", [i+1, len, RC.entropy(word), str]

 

{{out}}

 

=={{header|F_Sharp|F#}}==

 

let fiboword =

Seq.iteri (fun i (s : string) ->

printfn "%3i %10i %10.7g %s" (i+1) s.Length (entropy s) (if s.Length < 40 then s else ""))

{{out}}

<pre> # Length Entropy Word (if length < 40)

=={{header|Factor}}==

It is not necessary to calculate each fibonacci word, since every fibonacci word less than 37 is contained in the 37th fibonacci word. In order to obtain the nth fibonacci word ( <= 37 ), we start with the 37th fibonacci word and take the subsequence from index 0 to the nth fibonacci number, as in the standard fibonacci sequence.

math.ranges math.statistics namespaces pair-rocket sequences ;

IN: rosetta-code.fibonacci-word

dup nth-fib-word [ length ] [ entropy ] bi

"%2d %8d %.8f\n" printf

{{out}}

<pre>

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre> N Length Entropy Word

36 14930352 0.959418728222743

37 24157817 0.959418728222745</pre>

 

=={{header|Go}}==

 

import (

fmt.Printf("%3d %9d %.16f\n", n, len(s), entropy(s))

}

{{out}}

[http://play.golang.org/p/e1whcGGOU1 Run in the Go Playground.]

=={{header|Haskell}}==

 

 

import Control.Monad

i l (entropy v) (if l > 40 then "..." else v))

[1..38::Int]

 

=={{header|Icon}} and {{header|Unicon}}==

words are shown, while the Fibonacci word length and [[Entropy]] are shown for all 37.

 

n := integer(A[1]) | 37

write(right("N",4)," ",right("length",15)," ",left("Entrophy",15)," ",

every (h := 0.0) -:= P[c := key(P)] * log(P[c],2)

return h

 

Sample run:

=={{header|J}}==

Implementation:

 

Also, from the [[Entropy#J|entropy]] page we need:

 

Task example:

 

1 1 0

2 1 0

35 9.22747e6 0.959419

36 1.49304e7 0.959419

 

=={{header|Java}}==

 

public class FWord {

}

}

Output:

<pre> 1 1 0.0

 

=={{header|JavaScript}}==

//that don't support console.table()

function console_table(xs) {

}

 

Output:

<pre>|N |Length |Entropy |Word |

=={{header|jq}}==

'''Entropy''':

# Output: an object with the strings as keys,

# the values of which are the corresponding frequencies.

# entropy in bits of the input string

def entropy:

'''Pretty printing''':

# return a string since it can readily be converted back to a number

def precision(n):

else rjustify(n)

end ;

'''The task''':

 

def task(n):

 

task(37)

{{Out}} (head and tail)

<pre>$ jq -n -r -f fibonacci_word.rc

{{works with|Julia|0.6}}

 

entropy(s::AbstractString) = -sum(x -> x / length(s) * log2(x / length(s)), values(counter(s)))

 

 

println(" n\tlength\tentropy")

 

{{out}}

 

=={{header|Kotlin}}==

 

fun fibWord(n: Int): String {

else println()

}

 

{{out}}

 

=={{header|Lua}}==

function log2 (x) return math.log(x) / math.log(2) end

if string.len(#v) < 8 then io.write("\t") end

print("\t" .. entropy(v))

{{out}}

<pre>n Word length Entropy

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

 

TableForm[

Quiet@Check[N[entropy /. {p -> Fibonacci[k - 1]/Fibonacci[k]}, 15],

0]}, {k, 37}],

 

{{out}}<pre>N Length Entropy

 

=={{header|Nim}}==

 

 

inc n

echo fmt"{n:2} {str.len:8} {entropy(str):.16f}"

 

{{out}}

 

=={{header|Objeck}}==

 

class FibonacciWord {

};

}

 

Output:

=={{header|Oforth}}==

 

| freq sz |

s size dup ifZero: [ return ] asFloat ->sz

ListBuffer new dup add("1") dup add("0") dup ->ws

3 n for: i [ i 1- ws at i 2 - ws at + ws add ]

 

{{out}}

=={{header|ooRexx}}==

{{trans|REXX}}

* 09.08.2014 Walter Pachl 'copied' from REXX

* lists the # of chars in fibonacci words and the words' entropy

Return left(1,d+2) /* return a left-justified "1". */

Return format(s,,d) /* normalize the number (sum or S)*/

{{out}}

<pre> N length Entropy Fibonacci word # of zeroes # of ones

 

=={{header|PARI/GP}}==

allocatemem(75<<20) \\ Allocate 75 MB stack space

F=vector(37);F[1]="1";F[2]="0";for(n=3,37,F[n]=Str(F[n-1],F[n-2]))

 

For those output fascists:

{{works with|Freepascal propably Delphi/Turbo-Pascal}}

As in Algol68 statet, you needn't to create the long string.

{$IFDEF DELPHI}

{$APPTYPE CONSOLE}

end;

END.

The same output:

<pre>No. Length Entropy Word

 

=={{header|Perl}}==

{

my ($a, $b, $count) = (1, 0, 0);

entropy($word),

$count > 9 ? '' : $word

 

=={{header|Phix}}==

{{out}}

<pre>

37: length 24157817, entropy 0.959419 ...

</pre>

 

=={{header|PL/I}}==

{{improve|PL/I| <br><br>The task's requirements are to also show the Fibonacci word's entropy. <br><br>}}

 

declare (fn, fnp1, fibword) bit (32000) varying;

declare (i, ln, lnp1, lfibword) fixed binary(31);

end;

 

<pre> 1 1 1

2 1 0

 

=={{header|PureBasic}}==

Define fwx$, n.i

NewMap uchar.i()

PrintN(" N Length Entropy Word")

For n=1 To 37 : fwx$=fw(n) : RowPrint(Str(n),Str(Len(fwx$)),StrD(ce(fwx$),15),fwx$) : Next

<pre> N Length Entropy Word

1 1 0.000000000000000 0

 

=={{header|Python}}==

>>> from collections import Counter

>>>

36 14930352 0.9594187 <too long>

37 24157817 0.9594187 <too long>

 

=={{header|R}}==

With inspiration from [http://rosettacode.org/wiki/Entropy#R here] for the entropy function:

{

if (length(s) > 1)

rownames(ret) <- NULL

return(ret)

 

Output:

 

So to start, a massively generalised version:

(provide F-Word gen-F-Word (struct-out f-word) f-word-max-length)

(require "entropy.rkt") ; save Entropy task implementation as "entropy.rkt"

(check-match (F-Word 4) (f-word "010" _ _ _))

(check-match (F-Word 5) (f-word "01001" _ _ _))

Output:

<pre> 1 1 0.000000000000 1

 

And a simpler implementation:

 

(define f-word-max-length (make-parameter 80))

(check-match (F-Word 4) (f-word "010" _ _ _))

(check-match (F-Word 5) (f-word "01001" _ _ _))

 

=={{header|Raku}}==

(formerly Perl 6)

 

sub entropy {

printf "%5d\t%10d\t%.8e\t%s\n",

(state $n)++, .chars, .&entropy, $n > 10 ?? '' !! $_;

 

That works, but is terribly slow due to all the string processing and bag creation, just to count 0's and 1's. By contrast, the following prints the table up to 100 almost instantly by tracking the values to calculate entropy in parallel with the actual strings. This works in Raku because lazy lists are calculated on demand, so if we don't actually ask for the larger string forms, we don't calculate them. Which would be relatively difficult for a string containing 573147844013817084101 characters, unless you happen to have a computer with a zettabyte or so of memory sitting in your garage.

 

constant @fib-ones = 1, 0, * + * ... *;

constant @fib-chrs = 1, 1, * + * ... *;

printf "%5d\t%21d\t%.15e\t%s\n",

$n, @fib-chrs[$n], entropy($n), $n > 9 ?? '' !! @fib-word[$n];

{{out}}

<pre> 0 1 0.000000000000000e+00 1

=={{header|REXX}}==

Programming note: &nbsp; 32-bit Regina REXX (under Windows/XP) can execute this program with &nbsp; N='''42''' &nbsp; without exhausting system resources, &nbsp; the 64-bit version of Regina can calculate bigger Fibonacci words.

d= 21; de= d + 6; numeric digits de /*use more precision (the default is 9)*/

parse arg N . /*get optional argument from the C.L. */

xx=izz; m=m+is*2**j; end /*while*/; x=x* e** -m -1; z=0; _=-1; p=z

do k=1; _=-_*x; z=z+_/k; if z=p then leave; p=z; end /*k*/

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

=={{header|Ring}}==

# Project : Fibonacci word

 

logBase =log( x) /log( 2)

return logBase

Output:

<pre>

Includes code for entropy from [[Entropy#Ruby|Entropy]] page.

 

 

def entropy(s)

words.each.with_index(1) do |word, i|

puts '%3i %9i %15.12f %s' % [i, word.length, entropy(word), word.length<60 ? word : '<too long>']

 

{{out}}

This is not implemented in any sort of generic way and is probably fairly inefficient.

 

curr: T,

next: T,

println!("{:10} {:10} {:.10} {:60}", i + 1, s.len(), get_entropy(&s.bytes().collect::<Vec<_>>()), word);

}

 

{{out}}

 

=={{header|Scala}}==

//word iterator

def fibIt = Iterator.iterate(("1","0")){case (f1,f2) => (f2,f1+f2)}.map(_._1)

val it = fibIt.zipWithIndex.map(w => (w._2, w._1.length, entropy(w._1)))

println(it.take(37).map{case (n,l,e) => s"$n).\t$l \t$e"}.mkString("\n"))

 

{{out}}

=={{header|Scheme}}==

 

(import (scheme base)

(scheme inexact)

(entropy (vector-ref *words* i)))

"\n")))

 

{{out}}

 

===Recursive function===

 

function word=fiboword(n)

 

disp('EXECUTION TIME: '+string(time)+'s.');

 

{{out}}

 

===Iterative method===

 

final_length = 37;

 

disp('EXECUTION TIME: '+string(time)+'s.');

 

{{out}}

 

=={{header|Seed7}}==

include "float.s7i";

include "math.s7i";

writeln(index lpad 2 <& length(fibWord) lpad 10 <& " " <& entropy(fibWord) digits 15);

end for;

 

{{out}}

</pre>

 

=={{header|Sidef}}==

{{trans|Ruby}}

[0] + (s.chars.freq.values »/» s.len) -> reduce { |a,b|

a - b*b.log2

entropy(word),

word.len<30 ? word : '<too long>'))

 

=={{header|Swift}}==

 

 

struct Fib: Sequence, IteratorProtocol {

 

print("i: \(i) len: \(str.count) entropy: \(ent)")

 

{{out}}

 

=={{header|Tcl}}==

set fw {1 0}

while {[llength $fw] < $n} {

foreach word [fibwords 37] {

fibwordinfo [incr i] $word

{{out}}

<pre>

36 14930352 0.959418728222743 <too long>

37 24157817 0.959418728222745 <too long>

</pre>

 

=={{header|Wren}}==

{{libheader|Wren-fmt}}

 

var entropy = Fn.new { |s|

for (k in m.keys) {

var c = m[k]

}

var l = s.count

}

 

Fmt.print("$2d $,10d $0.8f $s", i, fw.count, entropy.call(fw), Fmt.abbreviate(20, fw))

}

 

{{out}}

{{trans|D}}

{{trans|Python}}

len:=bs.len(); num1s:=(bs-"0").len();

T(num1s,len-num1s).filter().apply('wrap(p){ p=p.toFloat()/len; -p*p.log() })

"%3d %10d %2.10f %s".fmt(n,w.len(),entropy(w),

w.len()<50 and w or "<too long>").println();

{{out}}

<pre>

=={{header|ZX Spectrum Basic}}==

{{trans|FreeBASIC}}

20 PRINT "N, Length, Entropy, Word"

30 LET n=1

1070 IF t(j)>0 THEN LET prop=t(j)/sourcelen: LET entropy=entropy-(prop*LN (prop)/LN (base))

1080 NEXT j