оптимизирующий код: алгоритм фибоначчи

Question

Я работаю над алгоритмом фибоначчи для действительно больших чисел (100 тыс. Номеров). Мне нужно сделать этот запуск быстрее, хотя, но всего пару секунд, и у меня кончились идеи. Есть ли способ сделать это быстрее? Спасибо за помощь.

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

Answer 1

Независимо от того, насколько хорошо вы выполняете оптимизацию на заданном коде, не изменяя базовый алгоритм, вы можете оптимизировать его только незначительно. Ваш подход с линейной сложностью, и для больших значений он быстро станет медленным. Более быстрое внедрение чисел Фибоначчи, делая матрицу exponentiation by squaring на матрице:

0 1 
1 1 

Этот подход будет с логарифмической сложностью, которая асимптотически лучше. Выполните несколько расширений этой матрицы, и вы заметите, что номер Фибоначчи n + 1 расположен в нижнем правом углу.

Answer 2

Я хотел бы сохранить некоторые предвычисленные точки (тем более, что вы ищете действительно большие числа)

т.е. сказать, что я спас 500th и 501-й номера Фибо. Тогда, если кто-нибудь спросит меня, что такое 600-й фиб? Я бы начал вычислять с 502, а не с 1. Это действительно сэкономит время.

Теперь вопрос, сколько баллов вы бы сохранили, и как выбрать пункты для сохранения?

Ответ на этот вопрос полностью зависит от приложения и возможного распространения.

Answer 3

Предлагаю вам использовать что-то вроде cpp-bigint (http://sourceforge.net/projects/cpp-bigint/) для ваших больших чисел. код будет выглядеть следующим образом тогда

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

Быстрый бенчмарка на моей машине:

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

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