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:

Similmente, il generatore è definito come

Dove:

  • è l' termine della successione di numeri generati
  • e sono due qualunque termini precedenti della successione
  • è una qualsiasi Operazione binaria. Può essere addizione, sottrazione, moltiplicazione, divisione, ma anche un operatore logico
  • indica il resto della divisione tra e

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 tale che

In caso di moltiplicazione invece

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

dividendo entrambi i membri per una stessa quantità

Nel primo membro si semplifica, nel secondo si divide per , ricordando che per le potenze vale che

semplificando

infine

Q.E.D.

Voci correlate[modifica | modifica wikitesto]