Subtração com transporte

O algoritmo Subtração com transporte é um gerador de números pseudoaleatórios, fazendo parte de um conjunto de algoritmos projetados para produzir uma longa série de números aparentemente aleatórios com base em uma pequena quantidade de dados iniciais. É do tipo Fibonacci defasado introduzido por George Marsaglia e Arif Zaman em 1991.^[1] "Fibonacci defasado" refere-se ao fato de que cada número aleatório é uma função de dois dos números precedentes em alguns deslocamentos fixos especificados, ou "atrasos".

A sequência gerada pelo mecanismo de subtração com transporte pode ser descrita pela recorrência:

${\displaystyle x(i)=(x(i-S)-x(i-R)-cy(i-1))\ {\bmod {\ }}M}$

onde ${\displaystyle cy(i)={\begin{cases}1,&{\text{se }}x(i-S)-x(i-R)-cy(i-1)<0\\0,&{\text{em outros casos}}\end{cases}}}$ .

As constantes S e R são conhecidas como atrasos curtos e longos, respectivamente.^[2] Portanto, as expressões ${\displaystyle x(i-S)}$ e ${\displaystyle x(i-R)}$ correspondem aos termos anteriores S e R da sequência. S e R satisfazem a condição ${\displaystyle 0<S<R}$ . O módulo M tem o valor ${\displaystyle M=2^{W}}$, onde W é o tamanho da palavra, em bits, da sequência de estados e ${\displaystyle W>0}$ .

O mecanismo de subtração com transporte é um dos geradores da família que inclui também mecanismos de adição com transporte e subtração com empréstimo.^[1]

É um dos três mecanismos geradores de números aleatórios incluídos na biblioteca padrão C++11.^[3]

Referências