Liczby Fibonacciego (F_n), 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,

F₀ = 0
F₁ = 1
F_n = F_n-1 + F_n-2 dla n > 1

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

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      WOW!!!
lub w częściej spotykanej notacji
F[1476] = 1,3069892237634 x 10³⁰⁸    PODWÓJNE WOW!!!

Dla porównania, warto sobie uzmysłowić, że rząd wielkości liczby atomów w  widzialnym, obserwowalnym Wszechświecie szacuje się na 10⁸⁰.  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.