Descrizione del problema

In questo caso di studio illustriamo una realizzazione efficiente della funzione che calcola il $k$-esimo numero di Fibonacci in un tempo proporzionale a $\log_2 k$. Discutiamo la realizzazione ricorsiva per Haskell, ma il principio su cui si basa è applicabile anche in una versione iterativa. Il “trucco” per ottenere una realizzazione efficiente consiste nel riuscire a definire una funzione che calcola $F_k$ per mezzo della $k$-esima potenza di un opportuno elemento $A$. è noto, infatti, che la $k$-esima potenza di $A$ è calcolabile in un tempo proporzionale a $\log_2 k$, osservando che

\[A^k = \begin{cases} \mathbf{1} & \text{se $k = 0$} \\ A^{k/2} \times A^{k/2} & \text{se $k > 0$ ed è pari} \\ A \times A^{\lfloor k/2\rfloor} \times A^{\lfloor k/2\rfloor} & \text{se $k$ è dispari} \end{cases}\]

dove $\mathbf{1}$ rappresenta l’elemento neutro dell’operazione di moltiplicazione $\times$ usata in questo contesto. L’aspetto chiave di questa formulazione di $A^k$ è che nei due casi non banali è sufficiente calcolare $A^{\lfloor k/2\rfloor}$ una volta e riutilizzare tale risultato due volte per determinare $A^k$.

Nel caso specifico della sequenza di Fibonacci, prendiamo come $A$ la seguente matrice $2\times 2$

\[A = \left( \begin{array}{@{}cc@{}} 1 & 1 \\ 1 & 0 \end{array} \right),\]

come operazione $\times$ la moltiplicazione matriciale, e come elemento neutro $\mathbf{1}$ la matrice identità di dimensioni $2\times 2$. Ora dimostriamo, per induzione su $k$, che

\[A^k = \left( \begin{array}{@{}cc@{}} F_{k+1} & F_k \\ F_k & F_{k-1} \end{array} \right)\]

dove assumiamo, per convenzione, che $F_{-1} = 1$. Per $k=0$ abbiamo

\[A^0 = \left( \begin{array}{@{}cc@{}} 1 & 0 \\ 0 & 1 \end{array} \right) = \left( \begin{array}{@{}cc@{}} F_{k+1} & F_k \\ F_k & F_{k-1} \end{array} \right)\]

Per $k>0$ deriviamo

\[A^k = A \times A^{k-1} = \left( \begin{array}{@{}cc@{}} 1 & 1 \\ 1 & 0 \end{array} \right) \times \left( \begin{array}{@{}cc@{}} F_k & F_{k-1} \\ F_{k-1} & F_{k-2} \end{array} \right) = \left( \begin{array}{@{}cc@{}} F_k + F_{k-1} & F_{k-1} + F_{k-2} \\ F_k & F_{k-1} \end{array} \right) = \left( \begin{array}{@{}cc@{}} F_{k+1} & F_k \\ F_k & F_{k-1} \end{array} \right)\]

in cui le uguaglianze seguono, procedendo da sinistra verso destra, dalla definizione di $A^k$, dall’ipotesi induttiva, dalla definizione di moltiplicazione matriciale, e dalla definizione della sequenza di Fibonacci.

Implementazione in Haskell

Per la realizzazione efficiente di fibonacci è necessario lavorare con matrici $2 \times 2$ di numeri di tipo Integer. Tra le varie rappresentazioni possibili di queste matrici, scegliamo di usare una quadrupla (una tupla con 4 elementi). In altre parole, la tupla

	(a, b, c, d)

rappresenta la matrice con righe (a, b) e (c, d). Per comodità, possiamo definire un alias di tipo con un nome conciso e significativo per il tipo di queste tuple:

type Matrice = (Integer, Integer, Integer, Integer)

È evidente che sarebbe possibile anche una rappresentazione più strutturata, facendo uso di tuple all’interno di tuple:

	((a, b), (c, d))

Questa seconda rappresentazione è più vicina all’idea di matrice come struttura bidimensionale, ma non porta altri vantaggi pratici ai fini del problema in oggetto, pertanto utilizzeremo il tipo Matrice definito qui sopra.

Una volta scelta la rappresentazione delle matrici, è necessario realizzare le operazioni di moltiplicazione e potenza. Per la prima avremo

mul :: Matrice -> Matrice -> Matrice
mul (a₁₁, a₁₂, a₂₁, a₂₂) (b₁₁, b₁₂, b₂₁, b₂₂) =
  (a₁₁ * b₁₁ + a₁₂ * b₂₁,
   a₁₁ * b₁₂ + a₁₂ * b₂₂,
   a₂₁ * b₁₁ + a₂₂ * b₂₁,
   a₂₁ * b₁₂ + a₂₂ * b₂₂)

e per la seconda

pow :: Matrice -> Int -> Matrice
pow a k | k == 0         = (1, 0, 0, 1)
        | k `mod` 2 == 0 = b `mul` b
        | otherwise      = a `mul` b `mul` b
  where
    b = a `pow` (k `div` 2)

Notiamo l’uso infisso delle funzioni mul e pow. Questo è possibile racchiudendo il nome di tali funzioni tra backtick, esattamente come avviene per le funzioni di libreria div e mod. Con pow a disposizione, la funzione fibonacci efficiente è realizzata come segue

fibonacci :: Int -> Integer
fibonacci k = risultato
  where
    (_, risultato, _, _) = (1, 1, 1, 0) `pow` k

in cui il pattern a sinistra di = nella definizione locale che segue il where ci consente di dare un nome all’elemento della matrice che siamo interessati a restituire come risultato.

Per avere un’idea dell’efficienza di questa realizzazione di fibonacci, è possibile confrontare il tempo di esecuzione necessario a valutare la seguente espressione per le varie versioni presentate qui e nel precedente caso di studio. Tenere presente che la versione più lenta di fibonacci richiede un tempo di calcolo significativo (superiore ai 10 secondi) già intorno al 35-esimo numero di Fibonacci.

fibonacci 100000