[Se conosci come funziona la successione di Fibonacci salta qui!]
La storia che vi voglio raccontare oggi è la storia di Leonardo Pisano (1170 – 1240), conosciuto ai più con il nome di Fibonacci, da cui la famosa successione. L’appellativo “Fibonacci” venne dato a Leonardo poichè figlio di Guglielmo dei Bonacci (da cui filius Bonacci), un facoltoso mercante pisano. Leonardo nacque a Pisa nell’anno 1170 ed è tuttora considerato uno dei più importanti matematici della storia, grazie ai contributi che riuscì a dare alla geometria e all’algebra. Si pensa che ad influenzare Fibonacci, al di là dei matematici suoi colleghi dell’epoca, ci fu anche Muhammad ibn Musa al-Khwarizmi (780 – 850), una sorta di factotum dell’epoca perché era matematico, astronomo, astrologo e geografo. Ad al-Khwarizmi dobbiamo in qualche modo la nascita della parola algoritmo, traduzione latina del suo nome, nonché l’introduzione dello zero e della notazione posizionale nel mondo occidentale a partire dal XII secolo.
Non approfondirò qui la storia di questi due personaggi, che seppur risulta molto affascinante, non è nell’intento di queste righe. Nei prossimi paragrafi invece, proveremo a studiare la successione di Fibonacci mescolando assieme due delle “invenzioni” che i personaggi di cui sopra ci hanno omaggiato: da Leonardo Pisano prendiamo la sua successione numerica, mentre da al-Khwarizmi rubiamo l’idea di tradurre una soluzione di un problema in una sequenza finita di passi, gli algoritmi per l’appunto.
Analizzeremo dunque questa successione numerica dal punto di vista informatico, per scoprire come, implementazioni differenti di tale successione, generano gli stessi risultati in tempi incredibilmente diversi.
Prima di addentrarci nello studio più approfondito della questione, andiamo a rispolverare come funziona la successione del matematico pisano.
L’informatica dei giorni nostri conosce molto bene la successione di Fibonacci, se non altro perché si presta bene come esempio nelle volte in cui si va ad illustrare agli studenti la nozione di ricorsione. Diremo che un algoritmo è un algoritmo ricorsivo, se può essere calcolato calcolando sé stesso su argomenti più semplici. Per comprendere immediatamente questa definizione analizziamo proprio il modo in cui viene formulata la successione di Fibonacci:
[c]
fib (1) = 1
fib (2) = 1
fib (n) = (fib(n-1)+fib(n-2))
[/c]
Come leggiamo quanto scritto sopra? E’ semplice.
Se alla funzione “fib” passiamo l’argomento 1, la funzione ci restituisce 1.
Se alla funzione “fib” passiamo l’argomento 2, la funzione, di nuovo, ci restituisce 1.
Quando diciamo “passiamo l’argomento 1 (o 2)” intendiamo che vogliamo conoscere il primo numero di Fibonacci, o il secondo, o il terzo, e così via.
A questo punto, la terza riga ci dice che se alla funzione “fib” passiamo un argomento che non è né 1 né 2, (diremo quindi un qualsiasi numero naturale n > 2), la funzione calcolerà il risultato auto-chiamando sé stessa su valori più piccoli di quello dato come input.
Ad esempio, se vogliamo calcolare il risultato della funzione di Fibonacci sull’input 3, avremo che:
[c]
fib(3) = fib(2) + fib(1) = 1 + 1 = 2
[/c]
Iniziamo ora a fare dei ragionamenti più interessanti.
Intanto notiamo che la crescita della successione di Fibonacci è una crescita esponenziale, come dimostra la curva rappresentante i primi 12 numeri della successione:
Ciò significa che dopo pochi valori di n, raggiungiamo velocemente valori di fib(n) molto elevati.
Tanto per darvi un’idea se
con n = 10 fib(10) = 55,
con n = 15 fib(15) = 610
e con n = 20 fib(20) = 6765
e questo è sintomo che si sta presto a complicare le cose. Piccole variazioni dei valori dell’asse x generano grandi variazioni dei corrispettivi risultati, per cui potrebbe per noi sembrare abbastanza facile calcolare, ad esempio, il 36-esimo numero di Fibonacci perché in fondo riteniamo che 36 non sia un numero così alto. Supponiamo dunque che la computazione di Fibonacci sull’input 36 (fib(36)) sia tutto sommato semplice e veloce.
Purtroppo, parafrasando la frase di Imitation Game, sono gli algoritmi che nessuno immagina che possano fare certe cose, quelli che fanno cose che nessuno può immaginare.
Il risvolto informatico
La parte a mio avviso più interessante della successione di Fibonacci, la scopriamo quando andiamo ad implementare tale successione su di un calcolatore. La prima volta che si prova ad eseguire l’algoritmo di Fibonacci al computer, si è propensi ad utilizzare il cosiddetto algoritmo “naive”, che ricalca la definizione comune della successone di Fibonacci. Segue un esempio.
[c]
int fibonacci(int i)
{
if (i == 0) return 0;
else if (i == 1) return 1;
else return fibonacci(i-1) + fibonacci(i-2);
}
[/c]
Pro e contro di questa soluzione. Beh, di buono c’è l’idea che l’algoritmo che andiamo ad implementare al computer è esattamente uguale alla definizione della successione di Fibonacci. Così come andiamo a studiare tale sequenza, così l’andiamo a codificare e ad eseguire al computer.
Per contro, gli svantaggi sono notevoli.
E’ davvero l’algoritmo “naive” che useremmo intuitivamente?
Se ci pensassimo qualche istante, arriveremmo a concludere che forse la sopracitata soluzione non è esattamente quella più vicina alla soluzione intuitiva. Capiamoci. Immaginiamo che vi venga chiesto di calcolare fib(10), ovvero il decimo numero di Fibonacci. Procedendo con il calcolo, scopriremo che fib(10) = 55 e il gioco è fatto.
Benissimo, immaginiamo ora che ci venga chiesto di calcolare fib(11). L’intuito ci spingerebbe a sbirciare nella soluzione precedente (fib(10)), per andare a sommare gli ultimi due numeri appena calcolati (fib(9) + fib(10)) per ottenere subito fib(11).
Ma questo procedimento lo seguirebbe l’intuito, non l’algoritmo naive sopra descritto.
L’intuito, eventualmente, si limiterebbe dunque a (ri)leggere gli ultimi due numeri precedentemente calcolati e ad eseguirne un’unica nuova computazione (la loro somma). L’algoritmo “naive” invece, se all’istante t0 ha calcolato fib(10) e all’istante t1 deve calcolare fib(11), rifarà, per fib(11), tutti i calcoli che aveva già fatto poco prima per fib(10). Un grosso spreco, non trovate? E’ un vero peccato “non ricordare” le computazioni precedenti, e infatti questa “mancanza di memoria” la paghiamo in termini di complessità temporale. Se provate a lanciare fib(50), dovrete attendere un bel po’ di minuti prima di osservare il risultato a video. Inoltre, piccola nota a margine, se rilanciate subito dopo fib(50) dovrete riaspettare all’incirca gli stessi minuti di prima per rivedere il risultato.
Un sacco di somme ogni volta…
Per essere precisi, l’algoritmo “naive” ha una complessità pari a O(fib n) addizioni.
Così se ad esempio volessimo calcolare il 30-esimo numero di Fibonacci, con l’algoritmo “naive” dovremmo aspettare circa 3 secondi prima di ottenere un risultato. Prendete con le pinze questo tempo, impreciso e dipendente dalla macchina calcolatrice che utilizziamo. Ci basti però a farci rendere conto che tre secondi non sono proprio pochi se pensiamo che all’algoritmo abbiamo chiesto il 30-esimo numero di Fibonacci, e non il 100’000’000-esimo. Sembra insomma, che più vogliamo numeri alti, più Fibonacci arranca.
Possiamo migliorare le cose?
Certo che sì. Come spesso accade nella risoluzione algoritmica dei problemi, vi sono spesso diverse ottimizzazioni da poter fare a partire dall’algoritmo più intuitivo e facile che ci viene in mente. Per quanto riguarda l’algoritmo di Fibonacci le tecniche di ottimizzazione sono diverse: pensate ad esempio ad aggiungere un semplice vettore che memorizzi i primi n numeri di Fibonacci in modo da non doverli più ricalcolare, ma solo rileggere. Altre soluzioni fanno uso di matrici o di altre tecniche implementate a livello di codice (come ad esempio l’utilizzo di matrici, che abbassano la complessità a O(log2n) chiamate della funzione fib).
L’ottimizzazione che vi propongo io sfrutta le caratteristiche del linguaggio funzionale Haskell, un linguaggio nato negli anni ’80 ad opera del logico Haskell Curry (di cui esiste anche un paradosso che prendete in causa Babbo Natale…). L’algoritmo che calcola l’n-esimo numero di Fibonacci è il seguente, e da ora in avanti ci riferiremo a lui con l’appellativo di fastfib:
[c]fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fastfib n = fibs!!n
[/c]
Cosa è cambiato rispetto a prima?
La complessità intrinseca dell’algoritmo prima di tutto. Mentre in precedenza abbiamo visto come l’algoritmo standard ci impiega al più fib(n) operazioni di calcolo, gli algoritmi ottimizzati per Fibonacci raggiungono anche la complessità lineare O(n).
La seconda cosa che gioca a nostro vantaggio è la scelta del linguaggio utilizzato, l’Haskell, che è caratterizzato dall’essere un linguaggio che effettua valutazioni lazy (pigre): la valutazione delle espressioni viene svolta solamente quando queste servono effettivamente.
Immaginiamo di avere a che fare con un’espressione del tipo:
[c]
stringa 1 = (16 * 2, 23)
[/c]
La particolarità di Haskell sta nel fatto che quello che effettivamente memorizzerà in un primo momento, in relazione alla stringa 1, sarà proprio la stringa (16 * 2, 23) così come la leggiamo, e non (32, 23) come ci aspetteremmo.
Haskell si preoccuperà di calcolare 16 * 2 solamente nel caso in cui vogliamo operare esattamente con il primo argomento della coppia. A quel punto, ne eseguirà la moltiplicazione e ci renderà disponibile il risultato. Insomma, fino a che non abbiamo una reale necessità di operare su certi valori (ottenibili a partire da una o più operazioni), Haskell, pigramente, non si preoccuperà di lavorare per noi.
Per finire, un’ultima cosa importante di fastfib è la sua capacità di non ricalcolare le somme già effettuate in precedenza.
Il risultato delle valutazioni che effettua fastfib ci viene reso disponibile ad una velocità pressoché istantanea per numeri fino all’ordine delle centinaia di migliaia, poi comincia un po’ ad arrancare (comprensibile anche per la limitatezza della memoria).
Come giocare con l’algoritmo fastfib?
Scaricato il compilatore/interpreter ghci, le due righe che compongo fastfib le potete compilare da terminale digitando i seguenti comandi
[css]ghci fastfib[/css]
Quello che dovreste ottenere sono le seguenti righe
[c]
MBP-di-Matteo:Desktop Matteo$ ghci fastfib
GHCi, version 7.8.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim … linking … done.
Loading package integer-gmp … linking … done.
Loading package base … linking … done.
[1 of 1] Compiling Main ( fastfib.hs, interpreted )
Ok, modules loaded: Main.
*Main>
[/c]
A questo punto avete due opzioni:
– Volete sapere l’n-esimo numero di Fibonacci?
Subito dopo il *Main> digitate
[c] fastfib n [/c]
dove n sarà uguale al numero di Fibonacci che volete conoscere
– Volete la successione dei primi n numeri di Fibonacci?
Allora subito dopo il *Main> dovete digitare
[c] take n fibs [/c]
dove n sarà uguale al numero di numeri di Fibonacci che volete calcolare
Funziona?
Se l’esecuzione di fastfib è andata a buon fine, provate ora a fare dei confronti sperimentali. Di seguito riporto l’algoritmo “naive” di Fibonacci che potete utilizzare con il *Main> del compilatore ghci. Ci riferiremo a lui chiamandolo slowfib.
[c]
slowfib 0 = 0
slowfib 1 = 1
slowfib n = slowfib (n-1) + slowfib (n-2)
[/c]
Di nuovo andate a compilare slowfib e ad eseguirlo dal Main. Provate, aprendo due finestre del terminale, a lanciare ad esempio slowfib 35 nella prima finestra e fastfib 35 nella seconda. Che ne dite? Si nota la differenza?
Buon divertimento!
Sitografia utile:
– per approfondire la successione di Fibonacci in Haskell;
– per approfondire con ulteriore dettaglio l’algoritmo fastfib;
– per chi volesse approfondire la storia di Leonardo Fibonacci, scoprire i risvolti non solo matematici che ha la sua successione e approfondire come da questi numeri nasce la sezione aurea.