Generatore di Fibonacci ritardato

Da Wikipedia, l'enciclopedia libera.

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
  • \pmod 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à[modifica | modifica wikitesto]

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 \le (2^k-1) \cdot 2^{m-1}

In caso di moltiplicazione invece

p \le (2^k-1) \cdot 2^{m-3}

Da notare che il periodo della moltiplicazione è un quarto di quello della somma.

dimostrazione

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.

Come dimostrato, l'operatore addizione genera una sequenza numerica con periodo molto maggiore dell'operatore moltiplicazione.

Voci correlate[modifica | modifica wikitesto]