fbpx

C++: Fibonacci Word

Bjarne-stroustrup
 

The Fibonacci Word may be created in a manner analogous to the Fibonacci Sequence as described here:

Define F_Word1 as 1;
Define F_Word2 as 0;
Form F_Word3 as F_Word2 concatenated with F_Word1 i.e “01”
Form F_Wordn as F_Wordn-1 concatenated with F_wordn-2

For this task we shall do this for n = 37. You may display the first few but not the larger values of n, doing so will get me into trouble with them what be (again!).

Instead create a table for F_Words 1 to 37 which shows:

The number of characters in the word
The word’s Entropy.

#include <string>
#include <map>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>

double log2( double number ) {
	return ( log( number ) / log( 2 ) ) ;
}

double find_entropy( std::string & fiboword ) {
	std::map<char , int> frequencies ;
	std::for_each( fiboword.begin( ) , fiboword.end( ) ,
	[ & frequencies ]( char c ) { frequencies[ c ]++ ; } ) ; 
	int numlen = fiboword.length( ) ;
	double infocontent = 0 ;
	for ( std::pair<char , int> p : frequencies ) {
		double freq = static_cast<double>( p.second ) / numlen ;
		infocontent += freq * log2( freq ) ;
	}
	infocontent *= -1 ;
	return infocontent ;
}

void printLine( std::string &fiboword , int n ) {
	std::cout << std::setw( 5 ) << std::left << n ;
	std::cout << std::setw( 12 ) << std::right << fiboword.size( ) ;
	std::cout << "  " << std::setw( 16 ) << std::setprecision( 13 ) 
	<< std::left << find_entropy( fiboword ) ;
	std::cout << "\n" ;
}

int main( ) {
	std::cout << std::setw( 5 ) << std::left << "N" ;
	std::cout << std::setw( 12 ) << std::right << "length" ;
	std::cout << "  " << std::setw( 16 ) << std::left << "entropy" ; 
	std::cout << "\n" ;
	std::string firststring ( "1" ) ;
	int n = 1 ;
	printLine( firststring , n ) ;
	std::string secondstring( "0" ) ;
	n++ ;
	printLine( secondstring , n ) ;
	while ( n < 37 ) {
		std::string resultstring = firststring + secondstring ;
		firststring.assign( secondstring ) ;
		secondstring.assign( resultstring ) ;
		n++ ;
		printLine( resultstring , n ) ;
	}
	return 0 ;
}
Output:
N          length  entropy         
1               1  -0              
2               1  -0              
3               2  1               
4               3  0.9182958340545 
5               5  0.9709505944547 
6               8  0.954434002925  
7              13  0.9612366047229 
8              21  0.9587118829771 
9              34  0.9596868937742 
10             55  0.9593160320544 
11             89  0.9594579158387 
12            144  0.959403754221  
13            233  0.959424446956  
14            377  0.9594165437404 
15            610  0.9594195626031 
16            987  0.9594184095152 
17           1597  0.9594188499578 
18           2584  0.959418681724  
19           4181  0.9594187459837 
20           6765  0.9594187214387 
21          10946  0.959418730814  
22          17711  0.959418727233  
23          28657  0.9594187286008 
24          46368  0.9594187280783 
25          75025  0.9594187282779 
26         121393  0.9594187282017 
27         196418  0.9594187282308 
28         317811  0.9594187282197 
29         514229  0.9594187282239 
30         832040  0.9594187282223 
31        1346269  0.9594187282229 
32        2178309  0.9594187282227 
33        3524578  0.9594187282228 
34        5702887  0.9594187282227 
35        9227465  0.9594187282227 
36       14930352  0.9594187282227 
37       24157817  0.9594187282227

SOURCE

Content is available under GNU Free Documentation License 1.2.