5
\$\begingroup\$

My program gets some input values and outputs Fibonacci values.

Generally, I'm adding single numbers from the right to left, and I'm saving it in the sum value and get rest of it and add to string. (The value of "second" will always be larger than "first").

Is there some way to speed up my code?

#include <iostream>
#include <string>
using namespace std;

string addition(string &first, string &second);

int main()
{
      unsigned int value;
      cin>>value;
      string first="1";                 
      string second="1";                
      string helper;                         

      if(value==1)
          cout<<"1"<<endl;
      else if(value==2)
          cout<<"1"<<endl;

      for(int i=2; i<value;i++)       
      {
            helper=addition(first,second);
            first=second;
            second=helper;
      }
      cout<<helper<<endl;
      return 0;
 }

string addition(string &first, string &second)
{
      string finalValue;
      short moveValue=0;
      unsigned int maximum=0, minimum=0;
      short sum;
      char app;

      maximum=second.length();
      minimum=first.length();

      for(int i=maximum-1;i>=0;i--)
      {
             if(minimum)
             {
                  minimum--;
                  sum=first[minimum]-48+second[i]-48+moveValue;    
                  moveValue=sum/10;                             
                  app=sum%10+48;
                  finalValue=app+finalValue;
             }
             else
             {
                  sum=second[i]-48+moveValue;
                  moveValue=sum/10;
                  app=sum%10+48;
                  finalValue=app+finalValue;
             }
      }

      if(moveValue==1)
      {
           app=moveValue+48;
           finalValue=app+finalValue;
      }
      return finalValue;
}
\$\endgroup\$
  • \$\begingroup\$ Why does your addition method work with strings? What exactly is the final output? \$\endgroup\$ – RubberDuck Oct 10 '15 at 10:53
  • 1
    \$\begingroup\$ I can't use normal types because it's too small so I did it using strings. FinalOutpus is the result of first+second. \$\endgroup\$ – Empeg Oct 10 '15 at 11:08
  • \$\begingroup\$ Because what's too small? \$\endgroup\$ – RubberDuck Oct 10 '15 at 11:09
  • 1
    \$\begingroup\$ @rubberduck I bet he means he's getting overflow. Takes some effort now, though; he must be doing a really absurd input. There are lots of libraries that implement bignums, those will get the code away from re-implementing addition. \$\endgroup\$ – sqykly Oct 10 '15 at 15:26
5
\$\begingroup\$

I see a number of things that you could use to improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. Know when to use it and when not to (as when writing include headers).

Avoid introducing unneeded variables

The helper string is not necessary. Instead, you could rework your addition routine so that it calculates first+=second and then swaps first and second. In that way, second would always contain the final value. This would also help with the next suggestion.

Avoid introducing unneeded tests

With a little judicious rewrite, your main function can eliminate the special case testing to see if the terms value is 1 or 2. I'd rewrite it like this:

int main()
{
    unsigned int maxterm;
    std::cin >> maxterm;
    std::string first="1";                 
    std::string second="1";                

    for(unsigned i=2; i < maxterm; ++i) {
        fibnext(first,second);
    }
    std::cout << second << std::endl;
}

Note that I've also renamed a variable from value (which is not very descriptive) to maxterm and the routine from addition (which is descriptive but very general) to fibnext which more accurately suggests that it's calculating the next Fibonacci term.

Simplify your addition

There are a few ways to simplify the addition, but this is perhaps the most straightforward:

std::string &fibnext(std::string &first, std::string &second)
{
    char carry = 0;

    // make strings the same length by 0-padding first
    first.insert(0, second.length() - first.length(), '0');
    for(int i=first.length()-1; i >= 0; --i)
    {
        first[i] += second[i] - '0' + carry;
        if (first[i] > '9') {
            first[i] -= 10;
            carry = 1;
        } else {
            carry = 0;
        }
    }
    if (carry)
        first.insert(0, 1, '1');

    std::swap(first,second);
    return second;
}

Results

The effects of these changes are to reduce the number of times that strings are copied and constructed. In fact, only two std::string objects are created and then expanded as needed. Each time a digit is inserted at the beginning of a string, it (conceptually, anyway) needs to allocate a new space that's large enough, copy the string into that new memory, and then free the old space. However, std::string implementations are often smart enough to allocate larger-than-immediately-needed chunks to help with exactly this type of operation.

I measure it as being almost 30x faster than the original code (0.10 seconds vs 2.88 seconds on my 64-bit Linux box) when calculating the 10,000th Fibonacci number.

\$\endgroup\$
5
\$\begingroup\$

This is not the fastest answer, but I hope it is the one requiring the minimal effort, with only 5 lines of code change for a good speedup (for n=20000, 14 seconds was cut to 2.5 seconds)

First I ran a code profiler, gprof, and foud the following

> Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 68.58      0.28     0.28     9998    28.12    41.18  addition(std::string&, std::string&)
 31.84      0.41     0.13 10451932     0.01     0.01  std::basic_string, std::allocator > std::operator+, std::allocator >(char, std::basic_string, std::allocator > const&)
  0.00      0.41     0.00        1     0.00     0.00  _GLOBAL__sub_I_main
  0.00      0.41     0.00        1     0.00     0.00  __static_initialization_and_destruction_0(int, int)

Your code is spending roughly 30% of it's time doing the 'operator+()' function of std::string, which seems an easy place to identify and change things since you have this in only three lines, namely

    finalValue=app+finalValue;

So by changing to this

    finalValue+=app;

We can cut down a lot of time. This changes from being 'make a new string' to 'add a single char onto an existing string'. (Why? It's related to how strings are stored in RAM in C++). Small problem, this ends up with a reversed number! This can have a "quick and dirty fix" of reverse(finalValue.begin() ,finalValue.end()); along with including the 'algorithm' header, and that makes 5 lines of changes total. (3 unique).

The changes noted above by other answerers will give even more speedup, cool question though. Reminds me of old Michael Abrash books. Good luck.

\$\endgroup\$
  • 2
    \$\begingroup\$ +1 for running a profiler! Measuring is still the best way to figure out why code is slow. \$\endgroup\$ – Edward Oct 10 '15 at 21:48
3
\$\begingroup\$
  1. You should avoid using namespace std; It's a plague and just biding its time to bite you later.
    Why is “using namespace std;” considered bad practice?

  2. Don't repeat yourself.
    If there are no circular dependencies, omit any forward-declarations and instead define before use.

  3. If you do the same thing for two conditions in an if-else-chain, combine them.
    If doing so makes the code more complicated and the repeated code-block is sufficiently complex, you might even use the much-maligned goto.

    Anyway, I'm not convinced you actually really want to output anything there in either case.

  4. Your string is no longer really a string, but secretly a ascii-decimal-coded number.
    So why don't you make it it's own class?

    Use Operator overloading to make it behave like a builtin type.

  5. As you make your numbers it's own type, you can now change it's inner representation:

    • Reverse the representation, so the lowest-order digit is at the start.
    • Consider saving it in a higher-order base which is a power of two, at minimum 28.
    • Unless you want to code it yourself as an exercise, use a third-party library like gmp to do the heavy lifting for you.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.