Pomoc w przyśpieszeniu algorytmu

0

Witam, potrzebuję pomocy z przyśpieszeniem algorytmu, chodzi o wyznaczanie liczby z ciągu fibonacciego z przedziału 0<n<100000.
Zrobiłem to na stringach i później każdą pojedyńczą "litere" zamieniałem na cyfrę i dodawałem. Działa, tylko że nie w takim czasie jaki mi potrzeba. Co można by zmienić? Sam algorytm wyznaczania tej liczby? (macierz na przykład) czy bardziej chodzi o sam kod?
Kod próbowałem zrobić na klasach i pogmatwałem przy tej zmiennej "wynik", ale mam to samo również w funkcjach normalnych.

#include <iostream>

#define Znak(b) (char(b+48))
#define Cyfra(a) (int(a-48))


using namespace std;

class Fib
{
    string wartosc="";
    string wynik="";
public:
    Fib (string w): wartosc(w) {};
    void wyswietl()
    {
        cout<<wartosc<<endl;
    }
    void dlugosc()
    {
        cout<<this->wartosc.length()<<endl;
    }
    Fib operator+(Fib &l)
    {
        int i;
        int Pomocnicza = 0;
        while( (this->wartosc).length() != (l.wartosc).length() )
        {
            if( (this->wartosc).length() > (l.wartosc).length() )
            {
                l.wartosc = "0" + l.wartosc;
            }
            else this->wartosc = "0" + this->wartosc;
        }
        int Pom;


        for(i = ((this->wartosc).length())-1; i >= 0; i-- )
        {
            Pom = Cyfra((this->wartosc)[i]) + Cyfra((l.wartosc)[i]) + Pomocnicza;
            wynik = Znak( Pom % 10 ) + wynik;
            Pomocnicza = (Pom/10);
        }

        if( Pomocnicza != 0 ) wynik = Znak( Pomocnicza ) + wynik;
        return Fib(wynik);
    }
};



int main()
{

    Fib f0("0");
    Fib f1("1");
    Fib fn("0");
    int i,N;
    cin>>N;
    if( N < 2 )
    {
        if( N == 0 ) fn = f0;
        else fn = f1;
    }
    else
    {
        for( i = 2; i <= N; i++ )
        {
            fn = f1+f0;
            f0 = f1;
            f1 = fn;
        }
    }

    fn.wyswietl();

}
 
1

Najszybszym rozwiązaniem będzie potęgowanie macierzy ze wzoru
user image
wraz z własną arytmetyką (którą masz już częściowo zaimplementowaną). Najpierw zaklep sobie powyższy wzorek na zwykłych long long-ach a w ramach kolejnego kroku dopisz mnożenie dużych liczb (coś w stylu Fib operator*(const Fib &l)),

Działa, tylko że nie w takim czasie jaki mi potrzeba

Tak na marginesie to dla n ~ 100000 to nigdy nie zadziała w rozsądnym czasie, taka natura problemu - O(n^2*logn) * mega stała...
No dobra - jest jeszcze FFT, ktoś chętny? :)

0

Zrobiłem te macierze, wynik nie do końca się zgadza ale liczenie jest jeszcze dłuższe (liczby dokładnie się nie zgadzają ale mają tyle cyfr).
Masz może jakiegoś tipa, jak wykonać te potęgowanie macierzy używając własnej arytmetyki(przyśpieszając tym, a nie zwalniając program :P )?

@Edit dobra liczby wychodzą już ok, ale prędkość zmalała ..

0

A jak Ty potęgujesz te macierze? Naiwnie, czy szybkim potęgowaniem? No i reprezentacja długich liczb w systemie dziesiętnym będzie bardzo powolna, zmień na binarną, a najlepiej użyj gotowej biblioteki np. gmp bo bez dobrej znajomości asma lub przynajmniej intrinsics nie napiszesz tego wydajnie.

0

Szybkim potęgowaniem? Zrobiłem niby teraz że liczy macierz n/2 i później potęguje tą macierz, niestety wynik dalej tak samo wolny :P

1 użytkowników online, w tym zalogowanych: 0, gości: 1