Subtração com empréstimo

Subtração com empréstimo (SWB, 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, ....

Diferente do que ocorre na geração usando a adição com transporte (AWC) , cada novo elemento na sequência deste gerador é produzido subtraindo-se o dígito com atraso 1 e o bit de empréstimo (inicialmente igual a 0 para o dígito de atraso 1, que é o 1 em negrito na seq. de Fibonacci acima) do dígito com atraso 2 (o 0 em negrito, nessa mesma sequência). Se a diferença resultar em um número positivo, o bit de empréstimo é igualado a zero; se não, soma-se 10 à diferença obtida e o bit de empréstimo recebe o valor 1. Logo, usando 0 e 1 como valores iniciais, com bit de empréstimo igual a 0, geramos a sequência

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

Para uma definição mais formal, precisamos gerar um conjunto finito X de vetores $x=(x_1,x_2,c)$, tendo como componentes $x_1$e $x_2$,resíduos de 10 e $c\in \{0,1\}$. A função $f$ de geração da sequência é então definida como

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

Que pode ser resumido de maneira mais informal como sendo $x_n=x_{n-2}-x_{n-1}-c$, sendo o empréstimo atualizado com $c_{n+1}=I(x_{n-2}-x_{n-1}-c_n)$, com $I$ sendo a função indicadora..

Já que a ordem da subtração importa no caso deste gerador, toda uma nova gama de geradores SWB pode ser criada por meio da transposição dos elementos atrasados na forma $x_n=x_{n-1}-x_{n-2}-c$, com o bit de empréstimo definido de acordo $c_{n+1}=I(x_{n-1}-x_{n-2}-c_n)$. O gerador como é definido inicialmente é chamado de SWB-II, enquanto que a forma modificada é classificada como SWB-I.

Como formulação geral e de modo a serem estabelecidos os períodos respectivos desta classe de geradores, definimos um conjunto finito X de vetores $x=(x_1,x_2,\dots ,x_r,c)$, com os valores de $x$ resíduos em relação à uma base qualquer $b$, e valores de atraso $r$ e $s$, sendo $r>s$ tendo a função iterativa $f$ definida para SWB-I

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

e a função iterativa do gerador SWB-II

$f(x_1,\dots ,x_r,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\ge 0\\ (x_2,\dots ,x_r,x_{r+1-s}-x_1-c+b,1),& \text{se }{x}_{r+1-s}-x_1-c<0\end{array}$

Com os valores das variáveis atribuídos, pode-se garantir que será gerada uma sequência periódica, tendo no caso do SWB-I o valor de $b^r-b^s-2$; enquanto que para o SWB-II será $b^r-b^s$.