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:

${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$

Similmente, il generatore è definito come

${\displaystyle F_{n}=F_{n-j}\star F_{n-k}{\pmod {m}},\quad 0<j<k\,}$

dove

• ${\displaystyle F_{n}}$ è l'${\displaystyle n}$-esimo termine della successione di numeri generati
• ${\displaystyle F_{n-j}}$ e ${\displaystyle F_{n-k}}$ sono due qualunque termini precedenti della successione
• ${\displaystyle \star }$ è una qualsiasi operazione binaria. Può essere addizione, sottrazione, moltiplicazione, divisione, ma anche un operatore logico
• ${\displaystyle \mod m}$ indica il resto della divisione tra ${\displaystyle (F_{n-j}\star F_{n-k})}$ e ${\displaystyle (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 ${\displaystyle p}$ tale che

${\displaystyle p\leq (2^{k}-1)\cdot 2^{m-1}}$

In caso di moltiplicazione invece

${\displaystyle 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

${\displaystyle (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à

${\displaystyle {\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 ${\displaystyle 2^{m-3}}$ per ${\displaystyle 2^{m-1}}$, ricordando che per le potenze vale che ${\displaystyle {\frac {a^{n}}{a^{m}}}=a^{n-m}}$

${\displaystyle (2^{k}-1)=4\cdot (2^{k}-1)\cdot 2^{m-3-m+1}\,}$

semplificando

${\displaystyle (2^{k}-1)=4\cdot (2^{k}-1)\cdot 2^{-2}}$

infine

${\displaystyle (2^{k}-1)=(2^{k}-1)}$

Q.E.D.

Voci correlate

• Numeri pseudo-casuali
• Generatore lineare congruenziale

Collegamenti esterni

• (EN) Fibonacci generator, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.