Jak wyliczać duże (naprawdę duże) liczby Fibonacciego?

https://xpil.eu/af6

Dziś ostatni z serii trzech wpisów o liczbach Fibonacciego.

Tak, zdaję sobie sprawę, że Czytelnik zamiast tego może pożądać innych tematów, bardziej ważkich. Jeżeli chodzi o ważkie, zapraszam na forum entomologów...

Pokażę dziś jak w szybki sposób wyliczyć N-tą liczbę Fibonacciego. Otóż zamiast pracowicie wyliczać je po kolei, co wymaga N-kroków (i dużej ilości dodawania), wystarczy zastosować sprytny algorytm rekurencyjny oparty na potęgowaniu, mnożeniu i dodawaniu, który będzie wymagał nie więcej, niż (pi x oko) log2n kroków.

ty mię tu, urwał, logarytmami nie szantażuj, tylko mów po ludzku gdzie garniec ze złotem jest

Mówiąc po ludzku wyliczenie tysięcznej liczby Fibonacciego nie zajmie nam więcej niż dziesięć kroków, milionowej - około dwudziestu, a miliardowej - około trzydziestu kroków.

Ma się rozumieć należy się liczyć z faktem, że długość liczb w ciągu Fibonacciego rośnie błyskawicznie, więc chociaż zaoszczędzimy na ilości kroków, nie zaoszczędzimy na ilości miejsca potrzebnego na przechowanie wyników. Musimy też mieć dobrze opanowane mnożenie i potęgowanie dużych (naprawdę dużych!) liczb. Na szczęście niektóre języki programowania (na przykład Python) radzą sobie z tym całkiem sprawnie.

OK, przejdźmy do rzeczy.

Jeżeli chcemy wyliczyć N-tą liczbę Fibonacciego, musimy zrobić tak:

Dla N parzystego:
- Bierzemy liczbę Fibonacciego na pozycji N/2, zapamiętujemy ją pod literką A.
- Bierzemy liczbę Fibonacciego na pozycji (N/2)+1, mnożymy ją przez dwa. Wynik zapamiętujemy pod literką B.
- Odejmujemy A od B, wynik odejmowania mnożymy przez A.
- Otrzymany wynik jest N-tą liczbą Fibonacciego.

Dla N nieparzystego:
- Bierzemy liczbę Fibonacciego na pozycji N/2 zaokrąglonej w dół do całości i podnosimy ją do kwadratu. Zapamiętujemy wynik jako A.
- Bierzemy liczbę Fibonacciego na pozycji N/2 zaokrąglonej w górę do całości, podnosimy ją do kwadratu. Zapamiętujemy wynik jako B.
- Dodajemy A do B. Wynik dodawania jest N-tą liczbą Fibonacciego.

No teraz najważniejsze. Uważny (oraz - ważne - niezaśnięty!) Czytelnik zauważy zapewne, że powyższy przepis każe wyliczać liczby Fibonacciego za pomocą innych liczb Fibonacciego. Ale skąd wziąć te inne liczby?

Tu w sukurs przychodzi rekurencja. Jeżeli przyjrzymy się uważnie, zauważymy, że każdorazowo wynik algorytmu dla F(N) zależy od dwóch liczb z okolic F(N/2). Żeby wyliczyć F(1000) potrzebujemy F(500) oraz F(501). Zeby wyliczyć F(500) potrzebujemy F(250) i F(251). I tak dalej. Każdy kolejny krok przemieszcza nas "w dół" sekwencji Fibonacciego o połowę. Prędzej czy później dotrzemy więc w "znane" tereny - przecież pierwszych sto czy dwieście liczb Fibonacciego możemy sobie wstępnie wyliczyć metodą tradycyjną i gdzieś zapamiętać na stałe.

Wykonanie takiego obliczenia na piechotę może być nieco żmudne (chociaż, gwarantuję, i tak o niebo szybsze niż wyliczanie tego w sposób tradycyjny, sumując). Jednak jeżeli zaprzęgniemy do tego algorytm komputerowy, jedynym ograniczeniem będzie w tym momencie ilość pamięci potrzebnej na przechowanie wyników pośrednich.

Może nawet kiedyś popełnię jakąś Pchełkę w tym temacie.

P.S. Jeżeli ktoś chciałby spróbować się z powyższym algorytmem we własnym zakresie podpowiem, że liczby Fibonacciego są ponumerowane od zera, a dwa pierwsze elementy to 0, 1. Czyli: F(0) = 0, F(1) = 1.

https://xpil.eu/af6

2 komentarze

  1. Temat świetnie opisany. Z tego co mi wyszło w kodzie mogę dodać, że zamiast rekurencji można zastosować pętlę while. Można też się obyć bez “globala” dla pierwszych iluś tam wyników. No i bez BigIntegerów się nie obędzie;p

    1. W Pythonie z tego co pamiętam nie rozróżnia się smallint od int czy bigint. Ale mogę się mylić, programista ze mnie raczej niedzielny 🙂

Skomentuj xpil Anuluj pisanie odpowiedzi

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]

Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.