Generatore di Fibonacci ritardato

Template:F 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}(\mathrm{mod}m),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
• $modm$ 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\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.

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 [(2^k-1)\cdot 2^{m-3}]$

dividendo entrambi i membri per una stessa quantità

$\frac{(2^k-1)\cdot 2^{m-1}}{2^{m-1}}=\frac{4\cdot [(2^k-1)\cdot 2^{m-3}]}{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.

Voci correlate

• Numeri pseudo-casuali
• Generatore lineare congruenziale

Collegamenti esterni

• Template:Collegamenti esterni