Adição com transporte

Adição com transporte (AWC, sigla em inglês) é um algoritmo de geração 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. É um dos tipos de geradores de Fibonacci defasado, introduzido por George Marsaglia e Arif Zaman em 1991. "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".

Algoritmo

Considerando a sequência de Fibonacci clássica

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....

com cada um dos elementos sendo a soma dos dois elementos prévios. Se aplicarmos o operador mod a todos os elementos desta sequência, teremos um exemplo de sequência de Fibonacci defasada com atraso $r=2$, $s=1$ e uma operação binária $v\diamond w=(v+w)mod10$, temos

0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, ....

Para uma definição mais formal e estabelecermos o período dessa sequência, precisamos gerar um conjunto finito X de vetores $x=(x_1,x_2)$, tendo como componentes os resíduos de 10 e função iterativa $f$ definida por $f(x_1,x_2)=(x_2,x_1+x_{2}modm)$. Como $f$ tem uma inversa, para qualquer vetor inicial $x\in X$ a sequência $x,f(x),f^2(x),f^3(x),\dots$ é estritamente periódica.

O gerador pseudo-aleatório usando adição com transporte se baseia na sequência periódica acima. Temos como valores iniciais x_0 e x_1 iguais a 0 e 1, respectivamente, mais um bit de transporte inicial de 0. Cada novo dígito da sequência é igual à soma dos dois dígitos anteriores (como na Fibonacci) mais o bit de transporte. Ao resultado é aplicado $mod10$ e o bit de transporte do novo dígito da sequência pode ser 1 ou 0, dependendo se o resultado é maior ou menor que 10. Usando sobrescritos para indicar o bit de transporte, os digito da sequência gerada são

$0,1^0,1^0,2^0,3^0,5^0,8^0,3^1,2^1,6^0,8^0,4^1,3^1,8^0,1^1,0^1,2^0,\dots$

Diferente da sequência-base mostrada acima, $x,f(x),f^2(x),f^3(x),\dots$, nossos $x$ provém do conjunto de vetores $X$ de ordem $1\times 3$, com $x=(x_1,x_2,c)$. A função de iteração $f$ é, portanto

$f(x_1,x_2,c)=\{\begin{array}{cc}(x_2,x_1+x_2+c,0),& \text{se }{x}_1+x_2+c<10\\ (x_2,x_1+x_2+c-10,1),& \text{se }{x}_1+x_2+c\ge 10\end{array}$

Nos casos em que os vetores iniciais $x=(x_1,x_2,0)$, com $x_1<x_2$ ou $x=(x_1,x_2,1)$, com $x_1>x_2$, a sequência é periódica com um período igual a 108. O mesmo período também ocorre no caso no caso de vetores iniciais diferentes dos tipos anteriores, e diferentes de $(0,0,0)$ ou $(9,9,9)$, só que o vetor que deu origem à sequência pode não aparecer novamente dentro dela.

Como se baseia nas sequências de Fibonacci defasadas, toda uma nova classe de geradores pode ser criada a partir da escolha de valores específicos dos atrasos $r$ e $s$; assim como do vetor gerador $x=(x_1,x_2,\dots ,x_r,c)$ com resíduos gerados em relação a $b$, obtendo-se assim, uma sequência $x,f(x),f^2(x),f^3(x),\dots$ com

$f(x_1,x_2,c)=\{\begin{array}{cc}(x_2,\dots ,x_r,x_{r+1-s}+x_1+c,0),& \text{se }{x}_{r+1-s}+x_1+c<b\\ (x_2,\dots ,x_r,x_{r+1-s}+x_1+c-b,1),& \text{se }{x}_{r+1-s}+x_1+c\ge b\end{array}$

O período da sequência gerada será, então, de $b^r+b^s-2$. Ou seja, devido a sua característica exponencial, estes geradores podem apresentar períodos bastante longos. Por exemplo, ao se escolher $b$ tem ordem de $2^{32}$ e $r$ em torno de 20, o período da sequência é de $2^{640}$, com um custo computacional baixo, já que usará somente $r$ locações de memória e a operação será realizada aproveitando-se a aritmética que já vem embutida na CPU.

Versão complementar

O gerador AWC tem uma versão chamada AWC complementar (AWC-c, sigla em inglês). As regras para formação do elemento $x_n$ e o transporte $c$ são

$\begin{array}{ccc}{x}_n& =& (2b-1-x_{n-r}-x_{n-s}-c_n)modb\\ & =& (-x_{n-r}-x_{n-s}-c_n-1)modb,\\ c_{n+1}& =& I(x_{n-r}+x_{n-s}+c_n\ge b)\end{array}$

com $I$ sendo a função indicadora, cujo valor é 1 se seu argumento é verdadeiro, e 0 se falso.

No AWC-c, $x_n$e $c$ são criados como no AWC, mas toma-se o dígito complementar $b-1-x_n$ em vez de $x_n$. Com essa alteração, o período das sequências geradas por meio do AWC-c será de $b^r+b^s$.