title: Generatore di Fibonacci ritardato
text: # Generatore di Fibonacci ritardato
  
  Un generatore di Fibonacci ritardato (LFG, dall'inglese Lagged Fibonacci Generator) è un algoritmo per la generazione di numeri pseudo-casuali basato su una generalizzazione della successione di Fibonacci. Dalla definizione della successione di Fibonacci:
  
      $F_{n}=F_{n-1}+F_{n-2}$
  
  Similmente, il generatore è definito come
  
      $F_{n}=F_{n-j}\star F_{n-k}{\pmod {m}},\quad 0<j<k\,$
  
  dove
  
  * $F_{n}$ è l'$n$-esimo termine della successione di numeri generati
  * $F_{n-j}$ e $F_{n-k}$ sono due qualunque termini precedenti della successione
  * $\star$ è una qualsiasi operazione binaria. Può essere addizione, sottrazione, moltiplicazione, divisione, ma anche un operatore logico
  * $\mod m$ indica il resto della divisione tra $(F_{n-j}\star F_{n-k})$ e $(m)$
  
  Se l'operatore usato è l'addizione, il generatore sarà di tipo additivo, se l'operatore è la moltiplicazione si avrà un generatore di Fibonacci ritardato di tipo moltiplicativo.
  
  ## Proprietà
  
  Come tutti i generatori di numeri pseudo-casuali, il generatore di Fibonacci ritardato è una funzione periodica. Il periodo massimo varia a seconda dell'operatore usato. Nel caso di somma o sottrazione, il generatore ha periodo $p$ tale che
  
      $p\leq (2^{k}-1)\cdot 2^{m-1}$
  
  In caso di moltiplicazione invece
  
      $p\leq (2^{k}-1)\cdot 2^{m-3}$
  
  Da notare che il periodo della moltiplicazione è un quarto di quello della somma.
  
  Come dimostrato di seguito, l'operatore addizione genera una sequenza numerica con periodo molto maggiore dell'operatore moltiplicazione.
  
  dimostriamo che
  
      $(2^{k}-1)\cdot 2^{m-1}=4\cdot \left[(2^{k}-1)\cdot 2^{m-3}\right]\,$
  
  dividendo entrambi i membri per una stessa quantità
  
      ${\frac {(2^{k}-1)\cdot 2^{m-1}}{2^{m-1}}}={\frac {4\cdot \left[(2^{k}-1)\cdot 2^{m-3}\right]}{2^{m-1}}}\,$
  
  Nel primo membro si semplifica, nel secondo si divide $2^{m-3}$ per $2^{m-1}$, ricordando che per le potenze vale che ${\frac {a^{n}}{a^{m}}}=a^{n-m}$
  
      $(2^{k}-1)=4\cdot (2^{k}-1)\cdot 2^{m-3-m+1}\,$
  
  semplificando
  
      $(2^{k}-1)=4\cdot (2^{k}-1)\cdot 2^{-2}$
  
  infine
  
      $(2^{k}-1)=(2^{k}-1)$
  
  Q.E.D.
  
  