need critiqueing on some software

[Dy7SLyTq]

so i wrote a basic fibonacci program, and i was wondering if there was any way to make it better. just for the record, it works fine and exactly the way i want it to.

/*
     Fibonacci Numbers to the nth term, using the formula:

            (1 + sqrt(5))^n - (1 - sqrt(5))^n
     F[n] = =================================
                     2^n * sqrt(5)
*/

#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <cmath>
#include <cstdlib>

using std::cout;
using std::cerr;
using std::endl;
using std::cin;
using std::istringstream;
using std::string;
using std::setfill;
using std::setw;
using std::right;

double Fib(double);

int main(int argc, char *argv[])
{
     string GetTop;

     do
     {
          cout<<"Number: ";
          cin>> GetTop;
     }while(atoi(GetTop.c_str()) < 0);

     int Length;

     if(GetTop.length() < string("Term").length())
          Length = string("Term").length();

     else
          Length = GetTop.length();

     istringstream Stream(GetTop);
     int Top;

     Stream >> Top;
     cout<< setw(Length) <<"Term"<<" | Number"<< endl;
     cout<< setfill('=') << setw(Length + string(" | Number").length()) <<"="<< endl;
     cout<< setfill(' ');

     for(int Counter = 0; Counter <= Top; Counter++)
          cout<< right << setw(Length) << Counter + 1 <<" | "<< Fib(Counter) << endl;
}

double Fib(double Current)
{
     double RootFive = sqrt(5.0);
     double FirstTerm = 1.0 + RootFive;
     double FinishedSideOne = pow(FirstTerm, Current);
     double SecondTerm = 1.0 - RootFive;
     double FinishedSideTwo = pow(SecondTerm, Current);
     double Top = FinishedSideOne - FinishedSideTwo;
     double Left = pow(2, Current);
     double Bottom = Left * RootFive;
     double Total = Top / Bottom;

     return Total;
}

[ats15]

Few efficiency/style comments:

1. I would make GetTop an integer (no need to atoi every time), and only then convert to string
2. If you rewrite the formula as FirstTerm=(1.0+RootFive)*0.5 you have one less pow call (not very efficient function)
3. It would be much more efficient to implement your own equivalent of pow with integer exponents (see for example http://www.overclockers.com/forums/showthread.php?t=380512)

[Zhuge]

I'd also suspect that if you are going to be printing every Fibonacci number up to n you may as well do the addition recurrence method since that will require only an addition each step, saving time.

[JLBorges]

If I were to write an equivalent program, it may end up looking something like this:

/*
     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>
#include <sstream>

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( double n ) // EDITED
{
    std::ostringstream stm ;
    stm << std::fixed << std::setprecision(0) << n ;
    return stm.str().size() ;
}

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' ;
}

http://ideone.com/6yqRcZ

[Dy7SLyTq]

@ats15:
a) which is more expensive? caliing atoi or converting between an int to a string to an int? im not arguing im really asking
b) why would i rewrite it like that? it will never be to the power of 0.5 and it will change with every iteration
c) alright ill do that thanks. ill look up some fast power algorithms tonight

@zhuge: whats the addition reccurrence method? i know i could google it, but would i find correct answeres that pertain to this?

@JLBorges: so thats an interesting version, I just have one question. wouldnt it be expensive will all of the objects? and all of the potential function calls?

edit:
i appreciate all of the suggestions and im not throwing them out the window, im just questioning to understand them better. also, what is in the pow function that would make it go so slow?

[JLBorges]

> wouldnt it be expensive will all of the objects?

I suppose you mean that the std::vector<double> is expensive in terms of memory. Because the sequence is stored, it does use the memory required for that. For example, with 128 terms, about 1.2 KB or so on my implementation. Would that be significant?

It would be faster because the computation of each successive term

         a *= root5_plus_1 ;
         b *= root5_minus_1 ;
         denom *= 2 ; 

uses three multiplications instead of three exponentiations. For that, we do not need the entire sequence, and we can scrounge on the aforementioned 1.2 KB by passing just the last term as input to the function. (Yes, there is the issue of floating point error Propagation; I would think that it would not be very significant - multiplication and division are 'safe' operations, while addition and subtraction are 'dangerous'.)


> and all of the potential function calls?

How many? This has far fewer function calls than the original code (which required four function calls for computing each term.


> i appreciate all of the suggestions and im not throwing them out the window

These programs are toys. Throw them out of the window when you become tired of them.

[ats15]

a. Converting int to string is less complicated (no checks needed
b. It is not to the power 0.5 It is pow ((1+sqrt(5))/2, n). I just use *0.5 instead of /2. That way you don't need to calculate 2^n. I should have mentioned that your SecondTerm is also (1.0 - RootFive)/2, and double Total = Top / RootFive;
c. The fast way is already in the code that JLBorges pasted

The recurrence method says F(n+2)=F(n+1)+F(n) http://www.programmingsimplified.com/cpp/source-code/fibonacci-series

[Dy7SLyTq]

i would have to convert it back to an int. about b) thanks that would work really well.'
about the recurrence method: alright cool. thanks

@jl: i did mean that and quite a bit more, but i guess your right in that it wouldnt be that much more expensive. about the function calls, i didnt mean how many you see in source, well actually now that im looking at it there arent as many as i thought there would be