Sei que é redescobrir a roda, mas quero saber como posso implementar do meu jeito um bom gerador congruente linear para sortear números inteiros de 0
a 2^B-1
. Como escolher constantes, quantos bits para a sequência, como fazer essa sequência ser bem embaralhada mesmo, etc.
-
Se alguém postar uma resposta melhor, mais simples e efetiva, eu aceito como solução.– RHER WOLF9/04/2021 às 18:55
-
1Isto teria duas utilidades , 1 exercício acadêmico , ok , 2 alguma utlização fora da curva por segurança ou sigilo e aqui não seria o local para discutir , fora isto é melhor optar por soluções estáveis e testadas das linguagens– Motta6/07/2022 às 15:47
-
De vez em quando, adiciono novas observações, como as ideias recentes de critérios.– RHER WOLF12/07/2022 às 5:33
-
Mas esta sua pergunta deveria ser a razão de ser o SO , melhorar os "código"– Motta12/07/2022 às 15:08
1 Resposta
Geradores congruentes lineares para sorteio
Primeiramente, saiba que os GCLs (geradores congruentes/congruenciais lineares) são geradores de sequências recursivas de elementos inteiros em que aplica-se a cada elemento para descobrir o próximo da sequência duas operações lineares, uma multiplicação e outra de adição, e depois restringem o resultado a um intervalo calculando resto de divisão. Isto é usado para gerar números pseudo-aleatórios por meio da formação de sequências bem embaralhadas. Como?
Dado um m ∈ ℕ*
, um f ∈ {1,2,...,m-1}
e um t ∈ {0,1,2,...,m-1}
, temos uma recursão s[n] = ( s[n-1] * f + t ) % m
. Adotando um valor inicial (chamado semente) s[0] ∈ {0,1,...,m-1}
, podemos a partir dele calcular s[1] = ( s[0] * f + t ) % m
, dele calcular s[2] = ( s[1] * f + t ) % m
e daí em diante. Cada vez que se obtém um novo elemento da sequência, pode-se modificá-lo de modo que vire um inteiro mais adequado como resultado pseudo-aleatório. É comum ignorar os bits menos significativos porque costumam ter um padrão nítido de comportamento e a escolha correta de m
, f
e t
é fundamental para formar uma sequência que realmente pareça aleatória.
Perceba que a fórmula recursiva garante um único sucessor para cada elemento de qualquer sequência. Além disso, independentemente da semente os sucessores dela são limitados a um máximo de m
possíveis valores e a recursão é infinita, portanto ao menos no m+1º
sucessor encontramos um elemento já alcançado anteriormente, tal que terá o mesmo sucessor daquela vez, mesmo sucessor do sucessor... o que dá caráter cíclico à sequência. Por outro lado, nem toda sequência tem para cada valor de elemento um único possível antecessor, a não ser que a semente (que é elemento sem antecessor) tenha valor igual a um sucessor da sequência, pois aí nesta sequência somente um elemento tem sucessor de valor igual ao da semente. Os GCLs possuem mais uma série de propriedades.
Exemplo de GCL
A biblioteca de C do visual studio já usou a recursão s[n] = ( s[n-1]*214013+2531011 )%4294967296
retornando os bits de índice 16 a 30. Uma maneira de implementar isso é usar uma variável de estado global inteira de 32 bits int state ;
para armazenar o elemento atual da sequência, implementar uma definição de seed void srand( int seed ){ state = seed ; }
e o sorteio que atualiza o estado para o próximo elemento e pega os bits corretos.
int rand(){
//state = state * 214013 + 2531011 ;
state = state * 0x343FD + 0x269EC3 ;
return ( state & 0x7FFFFFFF )>>16 ;
}
Não foi necessário calcular o resto da divisão porque o tipo inteiro de 32 bits já automaticamente limita a 4294967296 números na sequência e, apesar do sinal tornar o intervalo de incorreto (não de 0 a 4294967295 mas sim -2147483648 a 2147483647), o operador &
anula o bit de índice 31 (restando de 0 a 30), o que tira o sinal e possibilita com o deslocamento terminar de pegar os bits de índice 16 a 30 como se fossem de 0 a 14. Com isso, o sorteio resulta em números de 0 a 32767.
E a semente?
Lógico que, não apenas neste mas em qualquer GCL, se sempre usar a mesma semente a sequência será sempre a mesma, não simula um comportamento aleatório. Por isso é recomendado usá-los de modo que se garanta distintas sementes com um mecanismo oculto, como o uso de uma função relógio, pois a cada intervalo de tempo da granularidade da função o resultado do relógio é diferente e cada vez que o resultado dele muda (logo a semente muda) a sequência também muda.
Também pode-se usar como semente um inteiro que represente uma espécie de "código genético" de algo, pois sempre que usar esse mesmo código a sequência pseudoaleatória será a mesma, já outro código resulta em outra sequência. Com isso, um procedimento que constrói características de algo usando uma sequência pseudo-aleatória poderá formar sempre os mesmos dados dessa coisa a partir do código dela e com outro código, dados de outra. Pode-se aplicar em jogos com geração de características de um indivíduo, um mundo virtual (como em Terraria), o calendário de condições climáticas (como no Stardew Valley) e outros.
Pode ainda sortear com um mecanismo de GCL uma semente de outro, que usa uma recursão diferente. Assim, um só estado do primeiro GCL não simplesmente gera um inteiro mas uma sequência (e distinta da que ele gerará daí em diante). Afinal gerar longas sequências gasta muitos estados, pode adiantar o uso de todos e isso leva a repetição da sequência. Além disso, usar o mesmo GCL com a mesma semente gera a mesma sequência, portanto realmente é recomendado criar um segundo mecanismo diferente do primeiro para sortear sequências usando um estado do primeiro.
Fontes
https://en.wikipedia.org/wiki/Linear_congruential_generator https://pt.wikipedia.org/wiki/Geradores_congruentes_lineares
Definindo o seu
GCLs têm uma variável de estado s
que abriga um número inteiro, normalmente com número de bits b
maior que B
, a começar pela semente. Cada vez que essa variável é atualizada aplica-se uma fórmula como s=s*f+t
onde f
é um fator inteiro e t
é um termo inteiro, ambos constantes ao longo da sequência, definidos a sua escolha e tal decisão fortemente impacta a qualidade dos resultados. No extremo de usar f=0
, observa-se que o próximo estado sempre é t
, sempre o mesmo valor, o que sequer é comportamento aleatório. Mesmo fazendo outras escolhas, é possível que os ciclos sejam curtos, logo as sequências sejam muito repetitivas, ou que as gerações pareçam bem previsíveis.
Sendo assim, primeiramente é recomendado b
alto para s
suportar mais valores e que o par de constantes atenda a f%4 == 1
e t%2 == 1
para que qualquer número aceito pelo tipo inteiro de s
seja alcançável em qualquer sequência (portanto o ciclo tem 2^b
estados). Até então os GCLs de maior qualidade de sorteios medidos seguem estes padrões e ciclos longos de estados tornam a sequência menos repetitiva, portanto menos previsível. Outra alternativa é f%8 ∈ {3,5}
e t == 0
para tirar a necessidade da adição, mas os possíveis ciclos deste alcançam no máximo 1/4 dos valores suportados pelo tipo inteiro usado e essa sequência (logo esse tamanho de sequência) ainda depende da semente, funcionando melhor com semente ímpar porque metade dos estados ímpares formam uma sequência cíclica e a outra metade, outra, já os pares formam sequências menores. Mais uma alternativa é f%4 == 1
e t%4 == 2
, que separa dois ciclos, um com somente todos os pares e outro com os ímpares, claro que definido pela semente.
Segundo, perceba que os primeiros bits costumam seguir um padrão muito previsível, portanto outra razão de se recomendar variável de estado com mais bits que os que se deseja sortear é exatamente para deslocá-los, pegando os de maior relevância que são menos previsíveis. Se a sequência pseudo-aleatória é de uma variável de b
bits, então para sortear B
bits deve-se deslocar b-B
bits para a direita. Lembre-se de dar atenção ao sinal do inteiro ao deslocar.
Terceiro, não se tem uma convenção de como medir o realismo dos sorteios, mas é fato que GCLs simulam modelos uniformes discretos e esse tipo de distribuição possui características como valor médio, desvio médio, desvio máximo, desvio padrão... portanto deve-se atender ao máximo essas propriedades, requerendo assim um critério. A partir daí, você pode escolher as constantes b
, f
e t
, verificar se gera uma sequência suficientemente boa e decidir se as usa ou procura outras.
Repare ainda que sementes que são estados em um mesmo ciclo têm a qualidade da sua própria sequência igual às das outras (afinal ocorrem as mesmas sucessões, só iniciando em pontos distintos), logo a qualidade de todas é avaliada com uma só. Se o número de estados do ciclo não é absurdamente grande, é possível testar a qualidade da sequência inteira em tempo praticável.
Um exemplo de padrão de qualidade
Uma maneira de medir a qualidade é experimentalmente calcular valores consecutivos da sequência e comparar aspectos deles a valores esperados. Um desses aspectos pode ser simplesmente a diferença absoluta do valor aleatório atual para o antecessor, atual para antecessor do antecessor, etc.
Outro é a diferença finita absoluta com valores da sequência, discretos, retratando assim derivadas de funções contínuas. Em outras palavras, observar valores que retratem as mudanças dos valores aleatórios de um sorteio para outro. Pode-se interpolar para formar curvas contínuas, calcular derivadas nelas e comparar com os valores esperados para estimar o quanto a sequência desvia deles.
Por exemplo, pode-se calcular s[0]=0, s[1]=s[0]*f+t, s[2]=s[1]*f+t
e a partir daí cada vez que se calcula um novo s[n]=s[n-1]*f+t
tem-se uma sequência s[n-3], s[n-2], s[n-1], s[n]
, que permite até terceira ordem de derivadas estimadas usando diferenças finitas. Em caso de b
bits pequeno (como 16), pode-se calcular toda a sequência em tempo razoável com executáveis que não tenham grandes problemas de desempenho, como compilando código em C talvez sem nem precisar de otimização.
Exemplo de aplicação de terceira ordem de derivadas
Sendo a sequência em s
de valores únicos de 0
a 2^b-1
distribuídos pseudo-aleatoriamente, pode-se obter outra sequência aplicando um fator e um termo mantendo as propriedades uniformes. Aplicar v[n]=s[n]/2^b+1/2^(b+1)
resulta em sequência em v
de valores discretos únicos uniformemente distribuídos entre 0
e 1
. A sequência v
tem média 0.5
(portanto um v[n]
tem desvio |v[n]-0.5|
) e desvio absoluto médio 0.25
. Porém as derivadas aproximadas têm média 0
, logo seu desvio absoluto é seu valor absoluto, e seus desvios absolutos médios são variados em função de b
, f
e t
.
No índice n
, da derivada de primeira ordem aproximada por Δv[n]=(11*v[n]-18*v[n-1]+9*v[n-2]-2*v[n-3])/6
se espera o desvio absoluto médio 291539/320760 ≈ 0.909
, segunda Δ²v[n]=2*v[n]-5*v[n-1]+4*v[n-2]-v[n-3]
se espera 1919/1200 ≈ 1.599
e terceira Δ³v[n]=v[n]-3*v[n-1]+3*v[n-2]-v[n-3]
se espera 142/135 ≈ 1.052
. Se, por exemplo, você calcular numa sequência inteira desvios médios de derivadas 0.9, 1.6, 1.06
, encontrará diferenças absolutas relativas 0.0098, 0.0005, 0.0077
e, sendo a primeira maior, pode-se admitir o erro de 0.98%
ou precisão 100%-0.98% = 99.02%
ou ainda precisão por erro 99.02%/0.98% = 101.04
. Pode até pensar em outra métrica de qualidade.
Para aplicar esse critério de qualidade e obter uma dessas medidas, pode-se utilizar a fórmula 6*Δv[n]=11*v[n]-18*v[n-1]+9*v[n-2]-2*v[n-3]
para estimar 6x a derivada na primeira ordem (espera-se desvio de 6*291539/320760 ≈ 5.453
), Δ²v[n]=2*v[n]-5*v[n-1]+4*v[n-2]-v[n-3]
para estimar 1x deriva a segunda (≈1.599
) e Δ³v[n]=v[n]-3*v[n-1]+3*v[n-2]-v[n-3]
para estimar 1x deriva a terceira (≈1.052
). Com essas fórmulas, usando b=4, f=9, t=3 ou t=5
tem-se o GCL de qualidade 89.98% em toda a sequência, já b=4, f=1, t=1 ou t=15
tem 23.45%.
Variantes de derivadas
Ao invés de derivadas em n
, podem ser em n-3/2
, já que fica bem no meio do caminho de n-3
a n
. Neste caso, o critério de qualidade é diferente do anterior e as fórmulas são 24*Δv[n-3/2]=v[n-3]-v[n]+27*(v[n-1]-v[n-2])
(espera-se desvio 98482/10935 ≈ 9.006
), 2*Δ²v[n-3/2]=v[n]+v[n-3]-v[n-2]-v[n-1]
(espera-se desvio 7/15 ≈ 0.467
) e Δ³v[n-3/2]=v[n]+3*(v[n-2]-v[n-1])-v[n-3]
(espera-se desvio 142/135 ≈ 1.052
).
Mais uma opção é usar simplesmente Δv[n]=v[n]-v[n-1]
(espera-se desvio 1/3 ≈ 0.333
), Δ²v[n]=Δv[n]-Δv[n-1]=v[n]-2*v[n-1]+v[n-2]
(espera-se desvio 7/12 ≈ 0.583
) e Δ³v[n]=Δ²v[n]-Δ²v[n-1]=v[n]-3*(v[n-1]-v[n-2])-v[n-3]
(espera-se desvio 142/135 ≈ 1.052
), que são as aproximações mais básicas em n
. Se puder encontrar os desvios absolutos esperados, pode até aplicar ordens maiores com os padrões Δᵒv[n]=Δᵒ⁻¹v[n]-Δᵒ⁻¹v[n-1]
, por exemplo para o=4
espera-se desvio absoluto médio 17009/8640 ≈ 1.969
.
o=0 ⟹ 1/2
(for what?)o=1 ⟹ 1/3 ≈ 0.33333333333333333333
o=2 ⟹ 7/12 ≈ 0.58333333333333333333
o=3 ⟹ 142/135 ≈ 1.05185185185185185185
o=4 ⟹ 17009/8640 ≈ 1.96863425925925925926
o=5 ⟹ 2931233/787500 ≈ 3.72220063492063492063
o=6 ⟹ 1163075987/163296000 ≈ 7.12250139011365863218
o=7 ⟹ 4113717877657/300181423500 ≈ 13.70410543628126941706
o=8 ⟹ 132492375763962751/4996238671872000 ≈ 26.51842405165169204683
o=9 ⟹ 604254505886168721257/11735062568116715520 ≈ 51.49137487582579019981
Não pude calcular mais um durante o tempo que reservei. Além disso, visando pequenas facilitações na implementação tentei calcular os desvios esperados para um modelo distinto de fórmulas trocando Δᵒv[n]=Δᵒ⁻¹v[n]-Δᵒ⁻¹v[n-1]
por Δᵒv[n]=|Δᵒ⁻¹v[n]-Δᵒ⁻¹v[n-1]|
, o que não foi tão longe.
Isso resulta em Δ°v[n]=v[n]
(é a mesma partida, deu no mesmo, desvio absoluto médio esperado é 1/2
, for what?), Δv[n]=|Δ°v[n]-Δ°v[n-1]|=|v[n]-v[n-1]|
(é a mesma fórmula de ordem um, deu no mesmo, 1/3
), Δ²v[n]=|Δ¹v[n]-Δ¹v[n-1]|=||v[n]-v[n-1]|-|v[n-1]-v[n-2]||
(desta vez diferente, esperado 1/4
, parece seguir um padrão numérico óbvio) e Δ³v[n]=|Δ²v[n]-Δ²v[n-1]|=|||v[n]-v[n-1]|-|v[n-1]-v[n-2]||-||v[n-1]-v[n-2]|-|v[n-2]-v[n-3]|||
, porém como o de ordem dez no modelo anterior de fórmulas este último também não teve seu desvio esperado calculado a tempo (apesar da integração numérica com regra dos retângulos parecer convergir para 53/270 ≈ 0.1962962963
cada vez que aumenta os retângulos, o que quebraria o aparente padrão). Suponho que fórmulas como essa em ordens maiores e com outras complicações também não serão.
Um critério mais simples que derivadas de altas ordens
Uma última opção pensada foi o uso de diferenças unicamente entre v[n]
e cada uma de algumas anteriores, como Δv1[n]=v[n]-v[n-1]
, Δv2[n]=v[n]-v[n-2]
e Δv3[n]=v[n]-v[n-3]
. Com isso, pode ir adiante em mais valores anteriores para ter Δv4[n], Δv5[n], ...
, têm desvios absolutos médios esperados (que podem ser usados na medida escolhida de qualidade da mesma forma que os desvios de derivadas) e em todos os casos são 1/3
.
Tudo isso facilita e consome menos processamento, mas não há certeza da efetividade deste. A ideia inicial era observar as tendências de curvas de valores aleatórios mapeados pela ordem de sorteio, tudo usando as derivadas das curvas, o que se for determinante no realismo do critério não chegará aos pés das diferenças finitas mais aprofundadas.
Por outro lado, pode-se entender que todos aproximam derivadas, estes de primeira ordem usando pontos distintos da curva, com isso comparando valores aleatórios sucessivos da sequência e desde o início era preciso escolher algum critério para medir a proximidade de aspectos específicos do GCL com o gerador ideal. Enquanto não há um critério oficial de realismo, nós temos que escolher.
Experimentos
Este código em C tem a função qc
implementada para calcular a qualidade do sorteio, recebendo f%4 == 1
e t%2 == 1
e usando variáveis globais m
definidas cada vez que se define um b=3,4,5,6,7,8
num loop, assim calculando as qualidades e imprimindo as melhores configurações de f
e t
: https://ideone.com/gHg3T1. Perceba que para cada b
percorre f = 1, 5, 9, ..., 2^b-3
, internamente t = 1, 3, 5, ..., 2^b-1
e mais internamente (na função) sorteia toda a sequência possível, o que pesa muito se utilizar dezenas de bits.
Porém este código em C foi atualizado para código em VC++ que aceita qualquer f
e t
. Utilizando
# include <time.h>
# include <stdio.h>
typedef __int8 Char8 ;
typedef double Float64 ;
typedef __int64 SInt64 ;
typedef __int32 SInt32 ;
typedef unsigned __int8 UInt8 ;
typedef unsigned __int32 UInt32 ;
typedef unsigned __int64 UInt64 ;
e implementando a função
Float64 RandomQuality_Percent( UInt32 Factor , UInt32 Term , SInt64 Bits , UInt32 *MinState , UInt32 *MaxState , Float64 *StatesCount ){
const UInt32 CBits=UInt8( Bits>0 ?( Bits<32 ? Bits : 32 ): 0 ) , AndArg=UInt32( (1LL<<CBits)-1 ) ;
const Float64 StvFactor=1.0/(1LL<<CBits) , StvTerm=( Term==0 ? 0.0 : 0.5*StvFactor ) , MaxStatesCount=AndArg+1.0 ;
UInt32 State=( *MinState = *MaxState = (Factor+Term)&AndArg ) , FinalState=(State*Factor+Term)&AndArg ;
Float64 Value0 , Value1=StvFactor+StvTerm , Value2=State*StvFactor+StvTerm , Temporary ;
Float64 Mrd0=(*StatesCount=0) , Mrd1=0 , Mrd2=0 , Value3=(State=FinalState)*StvFactor+StvTerm ;
do {
(*StatesCount)++ ;
Value0 = Value1 ;
Value1 = Value2 ;
Value2 = Value3 ;
Value3 = ( State=(State*Factor+Term)&AndArg )*StvFactor+StvTerm ;
if( State < *MinState ) *MinState = State ;
if( State > *MaxState ) *MaxState = State ;
Temporary = 1100/5.453404414515526 * Value3 ;
Temporary -= 1800/5.453404414515526 * Value2 ;
Temporary += 900/5.453404414515526 * Value1 ;
Temporary -= 200/5.453404414515526 * Value0 ;
( Temporary<0 ? Mrd0-=Temporary : Mrd0+=Temporary ) ;
Temporary = 200/1.5991666666666667 * Value3 ;
Temporary -= 500/1.5991666666666667 * Value2 ;
Temporary += 400/1.5991666666666667 * Value1 ;
Temporary -= 100/1.5991666666666667 * Value0 ;
( Temporary<0 ? Mrd1-=Temporary : Mrd1+=Temporary ) ;
Temporary = 100/1.0518518518518519 * Value3 ;
Temporary -= 300/1.0518518518518519 * Value2 ;
Temporary += 300/1.0518518518518519 * Value1 ;
Temporary -= 100/1.0518518518518519 * Value0 ;
( Temporary<0 ? Mrd2-=Temporary : Mrd2+=Temporary ) ;
} while(( State != FinalState )&&( MaxStatesCount != *StatesCount )) ;
if( (Mrd0/=*StatesCount) > 100 ) Mrd0 = 200 - Mrd0 ;
if( (Mrd1/=*StatesCount) > 100 ) Mrd1 = 200 - Mrd1 ;
Temporary = ( Mrd0<Mrd1 ? Mrd0 : Mrd1 ) ;
if( (Mrd2/=*StatesCount) > 100 ) Mrd2 = 200 - Mrd2 ;
return ( Temporary<Mrd2 ? Temporary : Mrd2 ) ;
}
para calcular a qualidade usando semente 1
e ainda armazenar valores mínimos, máximos da sequência e contagem de elementos dela, pode-se assim conseguir mais dados e para mais configurações. Esta função main
busca os melhores em b=3,4,5,...,12,13
.
SInt32 main( UInt32 argsLength , Char8** args ){
Float64 TimeFactor=0 ;
for( UInt8 Bits=2 ; Bits<=13 ; Bits++ ){
UInt32 StartTime=time(0) ;
printf( " >>> BITS=%u Time=?????.??s" , UInt32(Bits) ) ;
UInt32 MaxValuePer4=1<<( Bits-2 ) , MaxValuePer2=MaxValuePer4<<1 ;
UInt64 MaxValuePlusOne = 2LL * MaxValuePer2 ;
Float64 Count=Float64(MaxValuePlusOne)*MaxValuePlusOne , BestQuality=0 , BestStatesCount[999] ;
UInt32 BestLength=0 , BestFactor[999] , BestTerm[999] , BestMinState[999] , BestMaxState[999] ;
for( UInt32 BlockFactor=0 ; BlockFactor<MaxValuePer4 ; BlockFactor++ ){
for( UInt32 BlockTerm=0 ; BlockTerm<MaxValuePer2 ; BlockTerm++ ){
for( UInt32 PieceFactor=0 ; PieceFactor<4 ; PieceFactor++ ){
UInt32 Factor = 4 * BlockFactor + PieceFactor ;
for( UInt32 PieceTerm=0 ; PieceTerm<2 ; PieceTerm++ ){
UInt32 Term = 2 * BlockTerm + PieceTerm ;
printf( "\b\b\b\b\b\b\b\b\b%8.2lfs" , TimeFactor * Count-- ) ;
Float64 Quality = 1e-9*UInt64( 0.5+1e9*RandomQuality_Percent( Factor , Term , Bits , BestMinState+BestLength , BestMaxState+BestLength , BestStatesCount+BestLength ) ) ;
if(( Quality >= BestQuality )&&( Quality < 100 )&&( BestStatesCount[BestLength] >= 4 )){
if( Quality > BestQuality ){
BestQuality = Quality ;
BestLength = 0 ;
}
BestFactor[ BestLength ] = Factor ;
BestTerm[ BestLength++ ] = Term ;
}
}
}
}
}
TimeFactor = Float64( time(0)-StartTime )/(( MaxValuePlusOne )*Float64( MaxValuePlusOne )) ;
printf( "\b\b\b\b\b\b\b\b\b\b\b\b\b\bQuality=%.9lf%%\n" , BestQuality ) ;
for( UInt32 index=0 ; index<BestLength ; index++ ){
printf( " --> FACTOR(%.4lf)=%u " , BestFactor[index]/Float64(MaxValuePlusOne) , BestFactor[index] ) ;
printf( "TERM(%.4lf)=%u " , BestTerm[index]/Float64(MaxValuePlusOne) , BestTerm[index] ) ;
printf( "MinState=%u MaxState=%u StatesCount=%.0lf\n" , BestMinState[index] , BestMaxState[index] , BestStatesCount[index] ) ;
}
}
}
Perceba que há mais loops que o necessário, pois há a composição de termo e fator com dois componentes, o bloco e o pedaço. É para estabilizar a contagem de tempo, pois há valores vizinhos que demoram tempos distintos. Além disso, a execução demora. Seria uma boa paralelizar os ciclos mais internos.
O resultado impresso no console foi o seguinte.
>>> BITS=2 Quality=91.685846491%
--> FACTOR(0.2500)=1 TERM(0.2500)=1 MinState=0 MaxState=3 StatesCount=4
--> FACTOR(0.2500)=1 TERM(0.7500)=3 MinState=0 MaxState=3 StatesCount=4
>>> BITS=3 Quality=91.685846491%
--> FACTOR(0.1250)=1 TERM(0.2500)=2 MinState=0 MaxState=7 StatesCount=8
--> FACTOR(0.1250)=1 TERM(0.7500)=6 MinState=1 MaxState=7 StatesCount=4
--> FACTOR(0.6250)=5 TERM(0.2500)=2 MinState=1 MaxState=7 StatesCount=4
--> FACTOR(0.6250)=5 TERM(0.7500)=6 MinState=1 MaxState=7 StatesCount=4
>>> BITS=4 Quality=91.685846491%
--> FACTOR(0.0625)=1 TERM(0.2500)=4 MinState=0 MaxState=15 StatesCount=16
--> FACTOR(0.0625)=1 TERM(0.7500)=12 MinState=1 MaxState=13 StatesCount=4
--> FACTOR(0.3125)=5 TERM(0.0000)=0 MinState=1 MaxState=13 StatesCount=4
--> FACTOR(0.3125)=5 TERM(0.5000)=8 MinState=1 MaxState=13 StatesCount=4
--> FACTOR(0.5625)=9 TERM(0.2500)=4 MinState=1 MaxState=13 StatesCount=4
--> FACTOR(0.5625)=9 TERM(0.7500)=12 MinState=1 MaxState=13 StatesCount=4
--> FACTOR(0.8125)=13 TERM(0.0000)=0 MinState=1 MaxState=13 StatesCount=4
--> FACTOR(0.8125)=13 TERM(0.5000)=8 MinState=1 MaxState=13 StatesCount=4
>>> BITS=5 Quality=98.987676056%
--> FACTOR(0.9062)=29 TERM(0.1562)=5 MinState=0 MaxState=31 StatesCount=32
--> FACTOR(0.9062)=29 TERM(0.7188)=23 MinState=0 MaxState=31 StatesCount=32
>>> BITS=6 Quality=99.145568860%
--> FACTOR(0.5781)=37 TERM(0.0469)=3 MinState=0 MaxState=63 StatesCount=64
--> FACTOR(0.5781)=37 TERM(0.5156)=33 MinState=0 MaxState=63 StatesCount=64
>>> BITS=7 Quality=99.850182387%
--> FACTOR(0.1641)=21 TERM(0.3828)=49 MinState=0 MaxState=127 StatesCount=128
--> FACTOR(0.1641)=21 TERM(0.7734)=99 MinState=0 MaxState=127 StatesCount=128
--> FACTOR(0.7891)=101 TERM(0.3828)=49 MinState=0 MaxState=127 StatesCount=128
--> FACTOR(0.7891)=101 TERM(0.3984)=51 MinState=0 MaxState=127 StatesCount=128
>>> BITS=8 Quality=99.958983357%
--> FACTOR(0.5820)=149 TERM(0.2461)=63 MinState=0 MaxState=255 StatesCount=256
--> FACTOR(0.5820)=149 TERM(0.3320)=85 MinState=0 MaxState=255 StatesCount=256
>>> BITS=9 Quality=99.985729809%
--> FACTOR(0.9629)=493 TERM(0.4043)=207 MinState=0 MaxState=511 StatesCount=512
--> FACTOR(0.9629)=493 TERM(0.5566)=285 MinState=0 MaxState=511 StatesCount=512
>>> BITS=10 Quality=99.996862277%
--> FACTOR(0.3018)=309 TERM(0.3291)=337 MinState=0 MaxState=1023 StatesCount=1024
--> FACTOR(0.3018)=309 TERM(0.9717)=995 MinState=0 MaxState=1023 StatesCount=1024
>>> BITS=11 Quality=99.997289187%
--> FACTOR(0.4126)=845 TERM(0.4468)=915 MinState=0 MaxState=2047 StatesCount=2048
--> FACTOR(0.4126)=845 TERM(0.9653)=1977 MinState=0 MaxState=2047 StatesCount=2048
>>> BITS=12 Quality=99.999219599%
--> FACTOR(0.5071)=2077 TERM(0.6321)=2589 MinState=0 MaxState=4095 StatesCount=4096
--> FACTOR(0.5071)=2077 TERM(0.8748)=3583 MinState=0 MaxState=4095 StatesCount=4096
>>> BITS=13 Quality=99.999718263%
--> FACTOR(0.8717)=7141 TERM(0.2313)=1895 MinState=0 MaxState=8191 StatesCount=8192
--> FACTOR(0.8717)=7141 TERM(0.6403)=5245 MinState=0 MaxState=8191 StatesCount=8192
Com um programa similar, pude por algumas horas rastrear valores de f
que formem configurações b=32, t=±1, f%4==1
de sequências tais que a qualidade em cada uma completa pude calcular em cerca de um minuto.
Com 64 bits, não se calcula a qualidade na sequência inteira nem em séculos. Não se definiu outro critério razoável para medir. Logo não houve essa tentativa. Além disso, mesmo limitado a 32 bits não se encontrou um padrão para valores de t
que favorecesse encontros de sequências de maior qualidade. Devido a isso, aceitou-se incremento (t=1
) e decremento (t=-1
ou t=4294967295
).
Examinando cada f=5°,5¹,5²,5³,...,(5^759)%4294967296
com t ∈ {1,-1}
, até então a melhor fórmula encontrada foi s[n+1] = (2335288753*s[n]-1)%4294967296 = 0x8B31ADB1*s[n]+0xFFFFFFFF
com o 53º valor de f
, t=-1
e qualidade (precisão) 99.9999999751%.
Lista de integrais de diferenças finitas
Para dar acesso a mais fórmulas, automatizei cálculo das diferenças finitas mais comuns para até seis números aleatórios chamados State0
, State1
, State2
, State3
, State4
e State5
. Quem conhece o Maple (programa de cálculo simbólico) pode entender que eu interpolei para extrair polinômios e calcular derivadas de múltiplas ordens, assim utilizando as fórmulas resultantes. Desconsiderei as que não utilizam State0
e filtrei fórmulas integrais de resultados repetidos.
Repare que não só inverter o sinal dentro dos cálculos de valor absoluto mas também trocar as ordens das variáveis aleatórias conserva o resultado das integrais, ou seja, tanto faz se sorteia primeiro State0
ou State1
ou State2
ou outro, bem como também trocar as aparições nas fórmulas, como State0<->State1
ou State1<->State2
ou State0<->State2
ou coisa parecida, inclusive várias delas.
-
1Eu só posso falar por mim. Achei pergunta e a resposta interessantes, mas se a pessoa não sabe nada sobre geradores congruentes lineares e estiver querendo conhecer o algoritmo não vai conseguir extrair nada. Só minha opinião, posso estar equivocado, mas poderia introduzir o assunto antes de ir direto ao ponto. 10/04/2021 às 0:53
-
1Notei erro no código que muda algumas conclusões sobre t==0. Corrigi tudo e adicionei mais detalhes e estrutura textual, vou só esperar para ver se termina de executar o programa que fiz para apresentar o resultado. 11/04/2021 às 14:54
-