/*
Fibonacci Numbers to the nth term, using the formula:
(1 + sqrt(5))^n - (1 - sqrt(5))^n
F[n] = =================================
2^n * sqrt(5)
*/
#include <vector>
#include <cmath>
#include <iostream>
#include <limits>
#include <iomanip>
static std::vector<double> fibonacci_sequence( unsigned int n )
{
static const double root5 = std::sqrt(5.0) ;
static const double root5_plus_1 = root5 + 1 ;
static const double root5_minus_1 = root5 - 1 ;
std::vector<double> result { 1, 1 } ;
double a = root5_plus_1 * root5_plus_1 ;
double b = root5_minus_1 * root5_minus_1 ;
double denom = root5 * 4 ;
for( unsigned int i = 2 ; i < n ; ++i )
{
a *= root5_plus_1 ;
b *= root5_minus_1 ;
denom *= 2 ;
result.push_back( std::round( (a-b)/denom ) ) ;
}
return result ;
}
static unsigned int number_of_terms( unsigned int max, const char* prompt )
{
std::cout << "please enter " << prompt << ": [2, " << max << "]: " ;
unsigned int n ;
if( std::cin >> n && n >= 2 && n <= max ) return n ;
std::cin.clear() ;
std::cin.ignore( std::numeric_limits<std::streamsize>::max(), '\n' ) ;
return number_of_terms( max, prompt ) ;
}
static int ndigits( unsigned int n )
{
if( n < 10 ) return 1 ;
else return 1 + ndigits( n/10 ) ;
}
int main()
{
constexpr unsigned int MAX_TERMS = 50 ;
const char* const prompt = "number of terms in the fibonacci_sequence" ;
const auto seq = fibonacci_sequence( number_of_terms( MAX_TERMS, prompt ) ) ;
std::cout << std::fixed << std::setprecision(0) << '\n' ;
const int width = ndigits( seq.back() ) + 2 ;
int cols = 0 ;
const int maxcols = 60 - width ;
for( auto v : seq )
{
std::cout << std::setw(width) << v ;
cols += width ;
if( cols > maxcols ) { std::cout << '\n' ; cols = 0 ; }
}
std::cout << '\n' ;
}