Generatore di Fibonacci ritardato

Niente fonti!
Questa voce o sezione sull'argomento algoritmi non cita le fonti necessarie o quelle presenti sono insufficienti.

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 {\displaystyle F_{n}=F_{n-1}+F_{n-2}}

Similmente, il generatore è definito come

F n = F n − j ⋆ F n − k ( mod m ) , 0 < j < k {\displaystyle F_{n}=F_{n-j}\star F_{n-k}{\pmod {m}},\quad 0<j<k\,}

dove

  • F n {\displaystyle F_{n}} è l' n {\displaystyle n} -esimo termine della successione di numeri generati
  • F n − j {\displaystyle F_{n-j}} e F n − k {\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
  • mod m {\displaystyle \mod m} indica il resto della divisione tra ( F n − j ⋆ F n − k ) {\displaystyle (F_{n-j}\star F_{n-k})} e ( m ) {\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 p {\displaystyle p} tale che

p ≤ ( 2 k − 1 ) ⋅ 2 m − 1 {\displaystyle p\leq (2^{k}-1)\cdot 2^{m-1}}

In caso di moltiplicazione invece

p ≤ ( 2 k − 1 ) ⋅ 2 m − 3 {\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

( 2 k − 1 ) ⋅ 2 m − 1 = 4 ⋅ [ ( 2 k − 1 ) ⋅ 2 m − 3 ] {\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à

( 2 k − 1 ) ⋅ 2 m − 1 2 m − 1 = 4 ⋅ [ ( 2 k − 1 ) ⋅ 2 m − 3 ] 2 m − 1 {\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 2 m − 3 {\displaystyle 2^{m-3}} per 2 m − 1 {\displaystyle 2^{m-1}} , ricordando che per le potenze vale che a n a m = a n − m {\displaystyle {\frac {a^{n}}{a^{m}}}=a^{n-m}}

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

semplificando

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

infine

( 2 k − 1 ) = ( 2 k − 1 ) {\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. Modifica su Wikidata
  Portale Crittografia
  Portale Matematica