[C++] Obliczanie N-tej liczby Fibonacciego modulo

adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[C++] Obliczanie N-tej liczby Fibonacciego modulo

Post autor: adambak » 7 wrz 2011, o 11:30

Tak jak w temacie.. Mam dane \(\displaystyle{ N<=10^9}\), dla którego mam obliczyć \(\displaystyle{ N}\)-tą liczbę Fibonacciego \(\displaystyle{ mod \ (10^9+7)}\) Oczywiście liniówka z tablicowaniem wyników odpada.. \(\displaystyle{ O(\log n)}\) będzie idealne, więc pomyślałem, że zastosuję wzór Bineta (http://pl.wikipedia.org/wiki/Ci%C4%85g_ ... B3r_Bineta) + algo na szybkie potęgowanie (podczas którego w każdym kroku robię modulo \(\displaystyle{ (10^9+7)}\) ). Wszystko by było super, gdyby nie to, że w takim razie muszę korzystać z double z którym jak zwykle mam jakieś kłopoty.. programy są króciutkie, więc zamieszczam z nadzieją, że ktoś mądrzejszy zauważy błąd..

Pierwsza próba:
http://ideone.com/v00zz
nie wiem jakim cudem przekracza limit czasu, gdzie się zapętla.. podejrzewam że to dwie pętle while obcinające wartości zmiennych fib i a do pożądanej reszty.. nie wiem czemu tak się dzieje, jakaś wskazówka? zamienię więc je na funkcję fmod..

W takim razie druga próba:
http://ideone.com/lad14
niestety, tym razem błędna odpowiedź bo dla:

Kod: Zaznacz cały

1
10000
poprawną odpowiedzią jest:

Kod: Zaznacz cały

271496360 
czy coś robię źle, czy to niedokładność double się nawarstwia z każdym mnożeniem i tym pięknym sposobem nie można zrobić tego zadania dobrze dla tak dużych \(\displaystyle{ N}\)?

Afish
Moderator
Moderator
Posty: 2823
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 354 razy

[C++] Obliczanie N-tej liczby Fibonacciego modulo

Post autor: Afish » 7 wrz 2011, o 12:09

1. Nie math.h tylko cmath.
2. W pierwszym programie najwięcej czasu zjadają pętle obliczające modulo.
3. Zamiast tego

Kod: Zaznacz cały

n>>=1;
stosuj normalne dzielenie. Takie sztuczki robi się dopiero wtedy, gdy kod jest poprawny. Poza tym kompilator i tak zrobi to lepiej.
4. Błędna odpowiedź to na 99% efekt niedokładności doubli. Musisz to wyliczyć na liczbach całkowitych.

xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

[C++] Obliczanie N-tej liczby Fibonacciego modulo

Post autor: xiikzodz » 7 wrz 2011, o 12:10

W ogólności wzór Bineta jest niefortunny, bo dla dużych \(\displaystyle{ n}\) zaokrąglenia mogą przekroczyć \(\displaystyle{ 1}\).

Możesz skorzystać z tożsamości:

\(\displaystyle{ F_n=F_{(n+1)/2}^2+F_{(n-1)/2}^2}\)

dla nieparzystych \(\displaystyle{ n}\)

\(\displaystyle{ F_n=F_{n/2+1}^2-F_{n/2-1}^2}\)

dla parzystych \(\displaystyle{ n}\).

Daje to żądaną złożoność obliczeniową.

Edt: dzieki za uwage, poprawione.
Ostatnio zmieniony 7 wrz 2011, o 14:01 przez xiikzodz, łącznie zmieniany 1 raz.

adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[C++] Obliczanie N-tej liczby Fibonacciego modulo

Post autor: adambak » 7 wrz 2011, o 12:39

Afish, dzięki, od razu nasuwają mi się pytania:
1. czemu cmath a nie math.h? jakoś często zdarza mi się to mieszać, więc gdybyś mógł mnie poprawić, kiedy co stosować.. (cmath właśnie kojarzyło mi się z czystym C)
2. na typach całkowitych.. ale to już nie tym sposobem, prawda? minus tej metody..

niby tych mnożeń nie ma dużo, ale jednak double wymięka, w sumie znów się na nim zawiodłem..


xiikzodz, genialne, dziękuję
a mogłabyś od razu zarzucić linkiem skąd ten wzorek?
EDIT: ok już go mam i czytam skąd co się wzięło..

a no i popraw proszę literówkę, można się domyślić oczywiście co gdzie, ale 2x użyłaś słowo "nieparzystych"

-- 7 wrz 2011, o 14:46 --

w sumie wybaczcie, ale pomęczę do końca..

jest już dużo dużo lepiej (przechodzi przykładowe testy)
http://ideone.com/Zu2HB

jednak nie wiem skąd ten wynik na minusie dla jednego testu.. poza tym martwi czas wykonywania, bo testów ma być ze 100.. czyli mamy sytuację: coś za wolno i nie do końca poprawnie.. pomożecie?

abc666

[C++] Obliczanie N-tej liczby Fibonacciego modulo

Post autor: abc666 » 7 wrz 2011, o 15:24

adambak, jak masz odejmowanie to \(\displaystyle{ b}\) może być większe niż \(\displaystyle{ a}\).

adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[C++] Obliczanie N-tej liczby Fibonacciego modulo

Post autor: adambak » 7 wrz 2011, o 16:34

hmm, coś pomogło, ale dziwne.. skoro \(\displaystyle{ a=F(n/2+1)}\) i \(\displaystyle{ b=F(n/2-1)}\), no to czy \(\displaystyle{ a}\) nie powinno być większym wyrazem ciągu skoro ma większy indeks?

oto poprawiony program: http://ideone.com/a5mEs którym dostaję "błędną odpowiedź", lekko załamujące, że w dodatku wolno liczy :-/

-- 7 wrz 2011, o 17:37 --

ok! cofam! to są wartości modulo więc jak najbardziej może być \(\displaystyle{ a<b}\)..

-- 7 wrz 2011, o 18:09 --

ok, teraz mam już chyba 100% dobrych odpowiedzi, ale dostaję " przekroczono limit czasu ".. czemu? przecież złożoność się zgadza.. dla takich wartości \(\displaystyle{ N}\) to powinien liczyć w mgnieniu oka.. gdzieś musiałem coś schrzanić, ale zupełnie nie widzę gdzie.. dla jasności, to jest mój najbardziej aktualny kod: http://ideone.com/a5mEs

Afish
Moderator
Moderator
Posty: 2823
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 354 razy

[C++] Obliczanie N-tej liczby Fibonacciego modulo

Post autor: Afish » 7 wrz 2011, o 19:54

adambak pisze:Afish, dzięki, od razu nasuwają mi się pytania:
1. czemu cmath a nie math.h? jakoś często zdarza mi się to mieszać, więc gdybyś mógł mnie poprawić, kiedy co stosować.. (cmath właśnie kojarzyło mi się z czystym C)
Math.h jest nagłówkiem dla języka C. W języku C++ nagłówek to cmath i jego należy stosować. Jest to kwestia zgodności ze standardami i takie tam bajki.
adambak pisze:2. na typach całkowitych.. ale to już nie tym sposobem, prawda? minus tej metody..
niby tych mnożeń nie ma dużo, ale jednak double wymięka, w sumie znów się na nim zawiodłem..
Uroki arytmetyki zmiennopozycyjnej. Poczytaj o zachowaniach chaotycznych - tam dopiero dzieją się cuda ;)

Awatar użytkownika
Zordon
Gość Specjalny
Gość Specjalny
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 909 razy

[C++] Obliczanie N-tej liczby Fibonacciego modulo

Post autor: Zordon » 7 wrz 2011, o 20:38

xiikzodz pisze:W ogólności wzór Bineta jest niefortunny, bo dla dużych \(\displaystyle{ n}\) zaokrąglenia mogą przekroczyć \(\displaystyle{ 1}\).

Możesz skorzystać z tożsamości:

\(\displaystyle{ F_n=F_{(n+1)/2}^2+F_{(n-1)/2}^2}\)

dla nieparzystych \(\displaystyle{ n}\)

\(\displaystyle{ F_n=F_{n/2+1}^2-F_{n/2-1}^2}\)

dla parzystych \(\displaystyle{ n}\).

Daje to żądaną złożoność obliczeniową.

Edt: dzieki za uwage, poprawione.
no właśnie to nie jest wcale takie oczywiste, że to da odpowiednią złożoność, bo implementując to tak po prostu narażamy się na wielokrotne obliczanie tych samych wartości. Z ciekawości chciałbym zobaczyć ile razy wywoła się \(\displaystyle{ F(1)}\) jak odpalę \(\displaystyle{ F(100000000)}\).
Edit: teraz widze, ze to w ogóle ani troche nie daje złożoności \(\displaystyle{ O(\lg n)}\)
Równanie rekurencyjne na koszt algorytmu ma postac: \(\displaystyle{ T(n)=2*T(n/2)+O(1)}\), co daje tylko \(\displaystyle{ O(n)}\). Ale i tak napiszę poniżej jak to naprawić, żeby przeszlo z czasem \(\displaystyle{ 0.00}\)

Zazwyczaj w takich przypadkach stosuje się programowanie dynamiczne, czyli "liczymy od dołu". Ale tutaj niestety nie możemy sobie na to pozwolić, bo takich dużych tablic nie uda się pomieścić. Drugi sposób to "spamiętywanie", czyli za każdym razem gdy obliczę \(\displaystyle{ F(n)}\) to zapamiętuję sobie wynik tych obliczeń, dzięki czemu nigdy nie wykonam tej samej pracy dwa razy. Tutaj kłopot jest znowu ten sam, bo jak zapamiętać \(\displaystyle{ F(n)}\) dla wielkich \(\displaystyle{ n}\) (tablica odpada). Rozwiązanie, które można zastosować to skorzystać z mapy (struktura map z STLa), wygląda to jak tablica, ale można używać dowolnie dużych kluczy (od środka to drzewo czerwono-czarne).
Nie wiem czy już udało Ci się odnaleźć błąd w tamtym rozwiązaniu, ale ono jest generalnie dobre, sam z ciekawości je wczoraj zaimplementowałem (jeśli chcesz zobaczyć kod to pisz). Ale akurat nie uważam go za najlepsze, mimo że bardzo sprytne. Jest sposób bardzo ogólny i dużo sprytniejszy .

xiikzodz zna ten sposób, ale być może sama nie jest tego świadoma. "Niestety" sposób ten wymaga znajomości operacji mnożenia macierzy. Zauważmy taką oto zależność:
jeśli \(\displaystyle{ f_n}\) to n-ta liczba Fibonacciego, to zachodzi:
\(\displaystyle{ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} f_{n+1} \\ f_n \end{bmatrix}=\begin{bmatrix} f_{n+1}+f_n \\ f_{n+1} \end{bmatrix}= \begin{bmatrix} f_{n+2} \\ f_{n+1} \end{bmatrix}}\)

To nie wygląda jeszcze na nic fajnego. Ale dzieki temu przez indukcje mozna pokazac:
\(\displaystyle{ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n\cdot \begin{bmatrix} f_{1} \\ f_0 \end{bmatrix}=\begin{bmatrix} f_{n+1}\\ f_{n} \end{bmatrix}}\)

Zatem sprowadziliśmy liczenie liczb fib. do potęgowania (macierzy). Co to znaczy? To znaczy, że możemy je obliczać w \(\displaystyle{ O(\lg n)}\). Bo tyle nas kosztuje potęgowanie. Algorytm szybkiego potęgowania wygląda tutaj dokładnie tak samo jak dla liczb. Ogólnie potęgowanie w każdej półgrupie można wykonywać w takim czasie, wystarczy nam tylko łączność mnożenia.

Xitami

[C++] Obliczanie N-tej liczby Fibonacciego modulo

Post autor: Xitami » 7 wrz 2011, o 21:22

tu i ówdzie utkać modulo...

Kod: Zaznacz cały

long long fibonacci(long n){
        long long i,h,j,k,t;
        i=h=1;
        j=k=0;
        while(n>0){
                if(n%2 == 1){
                        t= j*h;
                        j=  i*h + j*k +t;
                        i= i*k + t; }
                t=h*h;
                h=2*k*h + t;
                k=k*k + t;
                n=n/2;}
        return j;} 
-- 7 września 2011, 21:27 --

a kiedyś napisało mi się coś takiego

Kod: Zaznacz cały

typedef unsigned long long int ULL;
#define M(a,b,c,d,N) ((ULL)a*b + (ULL)c*d)%N
#define TMUL(a,b,c,d,e,f,g,h,N) \
        {unsigned int A=M(e,a,g,b,N), B=M(f,a,h,b,N), \
        C=M(e,c,g,d,N);d=M(f,c,h,d,N); a=A; b=B; c=C;}
 
unsigned int fibonacci(ULL n, unsigned int mod){  // n<2^64, mod < 3'037'000'499
        if (n<2) return n;
        n--;
        unsigned int xa=1,xb=1,xc=1,xd=0,ra=1,rb=0,rc=0,rd=1;   
        while(n){
                if(n&1)
                        TMUL(ra,rb,rc,rd,xa,xb,xc,xd,mod)
                n/=2;
                if(n==0) break;
                TMUL(xa,xb,xc,xd,xa,xb,xc,xd,mod)  
        }
        return ra;
}
Ostatnio zmieniony 7 wrz 2011, o 21:48 przez Xitami, łącznie zmieniany 1 raz.

adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[C++] Obliczanie N-tej liczby Fibonacciego modulo

Post autor: adambak » 7 wrz 2011, o 21:43

kurcze, z macierzami to u mnie cieniutko w LO takich dodatkowych rzeczy uczyłem się sam, a z nimi szło mi wyjątkowo opornie.. nie to że zupełnie odrzucam to rozwiązanie, bo chciałbym się jego nauczyć, ale póki co nie mam do niego wiedzy..

właśnie pomysł z zapamiętywaniem (o mapach pamiętam) odrzuciłem, bo pomyślałem, że jest mało przyszłościowy, możliwość przekroczenia pamięci itp.. oczywiście można tą dynamikę zrobić bez tablicy, na trzech zmiennych, ale wtedy dla każdego testu liniówka to masakra, widać że będzie TLE..

żałuję bardzo, że nie wypalił pomysł z wzorem od xiikzodz, ale tutaj:
Nie wiem czy już udało Ci się odnaleźć błąd w tamtym rozwiązaniu, ale ono jest generalnie dobre, sam z ciekawości je wczoraj zaimplementowałem (jeśli chcesz zobaczyć kod to pisz).
piszesz właśnie o nim, czy o Binecie? bo wybacz, ale już się pogubiłem tyle już sposobów a na razie żaden nie wypalił do końca.. bardzo byłbym Ci wdzięczny za pokazanie tego kodu (chyba na PW najlepiej), bo bym od razu zobaczył jak pisze mistrz (chociaż już widziałem, ale tylko trzy Twoje kody, bo trzy zadania na SPOJu są moje )-- 7 wrz 2011, o 22:45 --Xitami, a ten pierwszy kod to bazuje na jakim wzorze, skąd się wziął?

Afish
Moderator
Moderator
Posty: 2823
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 354 razy

[C++] Obliczanie N-tej liczby Fibonacciego modulo

Post autor: Afish » 7 wrz 2011, o 21:46

Jeżeli dobrze pamiętam, to wzorcówką dla tego zadania jest właśnie szybie potęgowanie macierzy, więc chyba warto zrozumieć tę metodę. A jeżeli chcesz więcej, to w tym wykładzie http://was.zaa.mimuw.edu.pl/?q=node/35 jest ładnie opowiedziane obliczanie ciągów zdefiniowanych rekurencyjnie właśnie przy użyciu macierzy.

adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[C++] Obliczanie N-tej liczby Fibonacciego modulo

Post autor: adambak » 7 wrz 2011, o 21:50

warto zrozumieć metodę, ale najpierw bym musiał solidnie przerobić same macierze.. w Cormenie niby zaczynają od definicji ale trochę za szybko, potrzebuję jakichś podstaw..

dziękuję za link

Awatar użytkownika
Zordon
Gość Specjalny
Gość Specjalny
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 909 razy

[C++] Obliczanie N-tej liczby Fibonacciego modulo

Post autor: Zordon » 7 wrz 2011, o 21:56

adambak pisze: piszesz właśnie o nim, czy o Binecie? bo wybacz, ale już się pogubiłem tyle już sposobów a na razie żaden nie wypalił do końca.. bardzo byłbym Ci wdzięczny za pokazanie tego kodu (chyba na PW najlepiej), bo bym od razu zobaczył jak pisze mistrz (chociaż już widziałem, ale tylko trzy Twoje kody, bo trzy zadania na SPOJu są moje )
Binetem to nie ma szans niestety ;d Ten wzor sluzy do innych rzeczy. A które zadania są Twoje, bo jakoś nigdy nie zwracam uwagi na autorów ;p?

adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[C++] Obliczanie N-tej liczby Fibonacciego modulo

Post autor: adambak » 7 wrz 2011, o 22:02

BICAKE, PRACA, INVER i SPONSOR

aa.. to daje cztery zadania
Ostatnio zmieniony 7 wrz 2011, o 22:17 przez adambak, łącznie zmieniany 1 raz.

Xitami

[C++] Obliczanie N-tej liczby Fibonacciego modulo

Post autor: Xitami » 7 wrz 2011, o 22:13

pierwszy kod miałem w notatkach, wzór? a bo ja wiem
kod drugi to właśnie potęgowanie macierzy

\(\displaystyle{ \left[\begin{array}{cc}a&b\\c&d\end{array}\right]\cdot \left[\begin{array}{cc}e&f\\g&h\end{array}\right]= \left[\begin{array}{cc}ea+gb&fa+hb\\gd+ec&hd+fc\end{array}\right]}\)

ODPOWIEDZ