optimizing code: fibonacci algorithm

Question

I'm working on a fibonacci algorithm for really big numbers (100k th number). I need to make this run faster though, but just a couple of seconds and I ran out of ideas. Is there any way to make it faster? Thanks for help.

#include <iostream>

using namespace std;
int main() {


    string elem_major = "1";
    string elem_minor = "0";
    short elem_maj_int;
    short elem_min_int;
    short sum;
    int length = 1;
    int ten = 0;

    int n;
    cin >> n;


    for (int i = 1; i < n; i++)
    {

        for (int j = 0; j < length; j++)
        {
            elem_maj_int = short(elem_major[j] - 48);
            elem_min_int = short(elem_minor[j] - 48);
            sum = elem_maj_int + elem_min_int + ten;
            ten = 0;
            if (sum > 9)
            {
                sum -= 10;
                ten = 1;
                if (elem_major[j + 1] == NULL)
                {
                    elem_major += "0";
                    elem_minor += "0";
                    length++;
                }
            }
            elem_major[j] = char(sum + 48);
            elem_minor[j] = char(elem_maj_int + 48);
        }
    }

    for (int i = length-1; i >= 0; i--)
    {
        cout << elem_major[i];
    }

    return 0;
}

This question belongs to Code Review

Thomas Ayoub
– Thomas Ayoub

2015-10-16 13:21:49 +00:00
Commented Oct 16, 2015 at 13:21 — Thomas Ayoub
– Thomas Ayoub, Commented Oct 16, 2015 at 13:21
Use power of matrix.

MikeCAT
– MikeCAT

2015-10-16 13:25:32 +00:00
Commented Oct 16, 2015 at 13:25 — MikeCAT
– MikeCAT, Commented Oct 16, 2015 at 13:25
@sam2090 this is the DP approach

Ivaylo Strandjev
– Ivaylo Strandjev

2015-10-16 13:35:38 +00:00
Commented Oct 16, 2015 at 13:35 — Ivaylo Strandjev
– Ivaylo Strandjev, Commented Oct 16, 2015 at 13:35

Ivaylo Strandjev · Accepted Answer · 2015-10-16 13:32:11Z

6

No matter how good optimizations you perform on a given code, without changing the underlying algorithm you can only optimize it marginally. Your approach is with linear complexity and for big values it will quickly become slow. A faster implementation of Fibonacci numbers is by doing matrix exponentiation by squaring on the matrix:

0 1
1 1

This approach will be with logarithmic complexity which is asymptotically better. Perform a few exponentiations of this matrix and you'll notice that the n + 1st Fibonacci number is at its lower right corner.

edited Oct 16, 2015 at 13:32

answered Oct 16, 2015 at 13:25

Ivaylo Strandjev

71.4k18 gold badges130 silver badges183 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

sam Over a year ago

+1 didn't read through OP's code. Usually fibonacci are recursive so I thought this might be as well :). Maybe this might be useful

Yu-Han Lyu Over a year ago

There are some methods that are asymptotically the same as q-matrix method but are faster in practice, for example [dx.doi.org/10.1016/S0020-0190(80)90076-9]. It may be helpful to read papers citing this paper to find other advanced algorithms. Here is my implementation of this algorithm [github.com/yuhanlyu/Snippets/blob/master/experiments/fibonacci/….

pokey909 · Accepted Answer · 2015-10-16 13:53:06Z

1

I suggest you use something like cpp-bigint (http://sourceforge.net/projects/cpp-bigint/) for your big numbers. The code would look like this then

#include <iostream>
#include "bigint.h"

using namespace std;
int main() {
    BigInt::Rossi num1(0);
    BigInt::Rossi num2(1);
    BigInt::Rossi num_next(1);

    int n = 100000;

    for (int i = 0; i < n - 1; ++i)
    {
        num_next = num1 + num2;
        num1 = std::move(num2);
        num2 = std::move(num_next);
    }
    cout << num_next.toStrDec() << endl;
    return 0;
}

Quick benchmark on my machine:

time ./yourFib
real    0m8.310s
user    0m8.301s
sys 0m0.005s

time ./cppBigIntFib
real    0m2.004s
user    0m1.993s
sys 0m0.006s

answered Oct 16, 2015 at 13:53

pokey909

1,8371 gold badge17 silver badges22 bronze badges

Comments

knightrider · Accepted Answer · 2015-10-16 13:25:37Z

0

I would save some precomputed points (especially since you are looking for really big numbers)

ie say I saved 500th and 501st fib number. Then if some one asks me what is 600th fib? I would start computing from 502 rather than from 1. This would really save time.

Now the question how many points you would save and how would select the points to save?

The answer to this question totally depends on the application and probable distribution.

answered Oct 16, 2015 at 13:25

knightrider

2,1531 gold badge18 silver badges29 bronze badges

Collectives™ on Stack Overflow

optimizing code: fibonacci algorithm

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related