Pomoc w przyśpieszeniu algorytmu

Odpowiedz Nowy wątek
2015-10-22 18:21

Rejestracja: 5 lat temu

Ostatnio: 4 lata temu

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();

}

Pozostało 580 znaków

2015-10-22 21:32

Rejestracja: 11 lat temu

Ostatnio: 1 rok temu

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^2logn) mega stała...
No dobra - jest jeszcze FFT, ktoś chętny? :)


edytowany 2x, ostatnio: yurai, 2015-10-22 21:41
@bogdans Nie benchmarkowałem nigdy tego problemu. W szacowaniu z góry przyjąłem że Fn ma z grubsza n cyfr co przy naiwnym liczeniu bezpośrednio ze wzoru daje problem klasy O((długość Fn)<sup>2) -> O(n</sup>2) -> O(10<sup>10) 10</sup>10 operacji razy stała. Jednak jak wynika z podlinkowanego przez ciebie tematu F_100000 ma tylko 20000 cyfr co już redukuje liczbę operacji 25 razy z 10<sup>10 do mniej niż 0.5*10</sup>9 co jest już do zrobienia w czasie kilkudziesięciu ms na nowoczesnym CPU. Zatem masz absolutną rację, dzięki za wytknięcie błędu. - yurai 2015-10-23 12:50

Pozostało 580 znaków

2015-10-22 23:09

Rejestracja: 5 lat temu

Ostatnio: 4 lata temu

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 ..

edytowany 2x, ostatnio: Avirel, 2015-10-23 01:08

Pozostało 580 znaków

Krzywy Lew
2015-10-23 10:32
Krzywy Lew
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.

Zamiast binarnej lepiej użyć podstawy 32 lub 64 i mnożenia Karatsuby. - hauleth 2015-10-23 11:38

Pozostało 580 znaków

2015-10-23 19:52

Rejestracja: 5 lat temu

Ostatnio: 4 lata temu

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

Pozostało 580 znaków

Odpowiedz

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