63 lines
2.0 KiB
C++
63 lines
2.0 KiB
C++
//to cope with the big numbers , I used the Class Library for Numbers( CLN )
|
|
//if used prepackaged you can compile writing "g++ -std=c++11 -lcln yourprogram.cpp -o yourprogram"
|
|
#include <cln/integer.h>
|
|
#include <cln/integer_io.h>
|
|
#include <iostream>
|
|
#include <algorithm>
|
|
#include <vector>
|
|
#include <iomanip>
|
|
#include <sstream>
|
|
#include <string>
|
|
#include <cstdlib>
|
|
#include <cmath>
|
|
#include <map>
|
|
using namespace cln ;
|
|
|
|
class NextNum {
|
|
public :
|
|
NextNum ( cl_I & a , cl_I & b ) : first( a ) , second ( b ) { }
|
|
cl_I operator( )( ) {
|
|
cl_I result = first + second ;
|
|
first = second ;
|
|
second = result ;
|
|
return result ;
|
|
}
|
|
private :
|
|
cl_I first ;
|
|
cl_I second ;
|
|
} ;
|
|
|
|
void findFrequencies( const std::vector<cl_I> & fibos , std::map<int , int> &numberfrequencies ) {
|
|
for ( cl_I bignumber : fibos ) {
|
|
std::ostringstream os ;
|
|
fprintdecimal ( os , bignumber ) ;//from header file cln/integer_io.h
|
|
int firstdigit = std::atoi( os.str( ).substr( 0 , 1 ).c_str( )) ;
|
|
auto result = numberfrequencies.insert( std::make_pair( firstdigit , 1 ) ) ;
|
|
if ( ! result.second )
|
|
numberfrequencies[ firstdigit ]++ ;
|
|
}
|
|
}
|
|
|
|
int main( ) {
|
|
std::vector<cl_I> fibonaccis( 1000 ) ;
|
|
fibonaccis[ 0 ] = 0 ;
|
|
fibonaccis[ 1 ] = 1 ;
|
|
cl_I a = 0 ;
|
|
cl_I b = 1 ;
|
|
//since a and b are passed as references to the generator's constructor
|
|
//they are constantly changed !
|
|
std::generate_n( fibonaccis.begin( ) + 2 , 998 , NextNum( a , b ) ) ;
|
|
std::cout << std::endl ;
|
|
std::map<int , int> frequencies ;
|
|
findFrequencies( fibonaccis , frequencies ) ;
|
|
std::cout << " found expected\n" ;
|
|
for ( int i = 1 ; i < 10 ; i++ ) {
|
|
double found = static_cast<double>( frequencies[ i ] ) / 1000 ;
|
|
double expected = std::log10( 1 + 1 / static_cast<double>( i )) ;
|
|
std::cout << i << " :" << std::setw( 16 ) << std::right << found * 100 << " %" ;
|
|
std::cout.precision( 3 ) ;
|
|
std::cout << std::setw( 26 ) << std::right << expected * 100 << " %\n" ;
|
|
}
|
|
return 0 ;
|
|
}
|