Courtesy of WikipediaLiczby Fibonacciego (Fn), układają się w niemalejący ciąg liczb naturalnych zwany ciągiem Fibonacciego charakteryzujący się tym, że zaczyna się od 0 i 1, a każda następna liczba ciągu jest sumą dwóch poprzednich. Tak więc,

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 dla n > 1

Porównajmy zatem algorytmy, które mogą być zastosowane do generowania ciągu Fibonacciego!

Courtesy of PNGTree.com






Co ciekawe, największa liczba Fibonacciego, którą może wygenerować interpreter Perla 5 na współczesnym, standardowym komputerze z 64-bitowym procesorem, to 

F[1476] = 1,3069892237634e+308     surprised WOW!!!
lub w częściej spotykanej notacji
F[1476] = 1,3069892237634 x 10308   surprised PODWÓJNE WOW!!!

W istocie, 1,796 x 10308 jest największą liczbą, jaką może obsłużyć komputer w architekturze 64-bitowej !!!




Dla porównania, warto sobie uzmysłowić, że rząd wielkości liczby atomów w  widzialnym, obserwowalnym Wszechświecie szacuje się na 1080surprised POTRÓJNE WOW!!!

Przeprowadziłem testy wydajności algorytmów generujących ciąg Fibonacciego na maszynie wirtualnej (Windows 10 x64, Intel Core i7-6700 CPU dual-core, 8 GB RAM z interpreterem Perla 5). Zarówno algorytm iteracyjny jak i arytmetyczny okazał się znacznie szybszy i wydajniejszy w porównaniu z algorytmem rekurencyjnym. Co ciekawe, algorytm iteracyjny był ok. 1,5 raza szybszy niż arytmetyczny wg pomiaru czasu zużytego przez każdy z procesów w wielokrotnie powtarzanych cyklach.