Você pode usar o Pi como um gerador de números aleatórios bruto?

30

Recentemente, vi essa pergunta em math.SE. Isso me fez pensar. Pi poderia ser usado como um gerador de números aleatórios bruto? Quero dizer que os resultados são bem conhecidos (há quanto tempo o pi foi calculado até agora?), Mas o Pi parece ser bastante aleatório quando utilizado 1 dígito de cada vez.

Isso faz algum sentido?

Earlz
fonte
Onde esses números aleatórios serão usados?
NullUserException 19/10/12
2
Teoricamente, poderia ser, mas provavelmente seria menos ideal do que os métodos atuais. Apenas instinto nisso, mas parece que o pool aleatório é maior dessa maneira, com menos sobrecarga.
Rig
@NullUserException Não tenho certeza ... Eu queria saber se eles poderiam ser usados. Eu suponho que este definitivamente não seria para criptografia embora'
Earlz
3
@FrustratedWithFormsDesigner - parte do pacote ent. Ele usa os números aleatórios para calcular a área de um círculo inscrito em um quadrado e, a partir disso, é possível calcular pi. Usando os bits de pi como números aleatórios, há uma certa elegância em usar esses dados para calcular pi.
11
O @FrustratedWithFormsDesigner ent é um conjunto de códigos para analisar a pseudo-aleatoriedade do grupo de bytes. Um teste dentro dele é um Monte Carlo para calcular pi e comparar o cálculo aleatório com o valor real para ver quão aleatório é.

Respostas:

50

Escavando de http://www.befria.nu/elias/pi/binpi.html para obter o valor binário de pi (para que fosse mais fácil converter em bytes em vez de tentar usar dígitos decimais) e depois executá-lo através de ent Eu recebo o seguinte para uma análise da distribuição aleatória dos bytes:

Entropia = 7.954093 bits por byte.

A compactação ideal reduziria o tamanho desse arquivo de 4096 bytes em 0%.

A distribuição do quadrado de Chi para 4096 amostras é de 253,00 e excederia aleatoriamente esse valor em 52,36% das vezes.

O valor médio aritmético dos bytes de dados é 126,6736 (127,5 = aleatório).

O valor de Monte Carlo para Pi é 3,120234604 (erro 0,68 por cento).

O coeficiente de correlação serial é 0,028195 (totalmente não correlacionado = 0,0).

Então, sim, usar pi para dados aleatórios forneceria dados bastante aleatórios ... percebendo que são dados aleatórios bem conhecidos.


De um comentário acima ...

Dependendo do que você está fazendo, mas acho que você pode usar os decimais da raiz quadrada de qualquer número primo como um gerador de números aleatórios. Eles devem ter pelo menos dígitos distribuídos uniformemente. - Paxinum

Então, calculei a raiz quadrada de 2 em binário para remover o mesmo conjunto de problemas. Usando a iteração de Wolfram, escrevi um script perl simples

#!/usr/bin/perl
use strict;
use Math::BigInt;

my $u = Math::BigInt->new("2");
my $v = Math::BigInt->new("0");
my $i = 0;

while(1) {
    my $unew;
    my $vnew;

    if($u->bcmp($v) != 1) { # $u <= $v
        $unew = $u->bmul(4);
        $vnew = $v->bmul(2);
    } else {
        $unew = ($u->bsub($v)->bsub(1))->bmul(4);
        $vnew = ($v->badd(2))->bmul(2);
    }   

    $v = $vnew;
    $u = $unew;

    #print $i,"  ",$v,"\n";
    if($i++ > 10000) { last; }
}

open (BITS,"> bits.txt");
print BITS $v->as_bin();
close(BITS);

Ao executar isso nos 10 primeiros A095804 correspondentes , fiquei confiante de que tinha a sequência. O valor v n como quando escrito em binário com o ponto binário colocado após o primeiro dígito fornece uma aproximação da raiz quadrada de 2.

O uso de ent nesses dados binários produz:

Entropy = 7.840501 bits per byte.

Optimum compression would reduce the size
of this 1251 byte file by 1 percent.

Chi square distribution for 1251 samples is 277.84, and randomly
would exceed this value 15.58 percent of the times.

Arithmetic mean value of data bytes is 130.0616 (127.5 = random).
Monte Carlo value for Pi is 3.153846154 (error 0.39 percent).
Serial correlation coefficient is -0.045767 (totally uncorrelated = 0.0).

fonte
Exatamente o tipo de resposta que eu estava procurando. Eu não tenho nenhuma idéia de como calcular todos este tipo de coisas
Earlz
Mesmo que a distribuição numérica seja bastante aleatória, você não precisa encontrar uma maneira de selecionar aleatoriamente uma parte dela?
Blumer
11
@Blumer no. A aleatoriedade é medida em uma sequência de números. Diz-se que a sequência dos dígitos pi é aleatória. Veja en.wikipedia.org/wiki/Statistical_randomness
Simon Bergot
11
Absolutamente certo. E como são dados aleatórios bem conhecidos, você nunca ousa usá-los para fins criptográficos.
Falcon
3
+1 para "dados aleatórios conhecidos". Se você precisar de dados aleatórios que alguém não consegue adivinhar, pi não é para você, se apenas precisar de um monte de números aleatórios por algum motivo, funciona bem.
jmoreno
5

Bem, entre outras propriedades de um gerador de números aleatórios, você provavelmente deseja que seja um número normal . E várias respostas na pergunta math.SE que inspirou sua pergunta apontam que atualmente se acredita que pi seja normal, mas isso não foi comprovado.

psr
fonte
2

Esse gerador seria um gerador de pseudo-número, ou seja, dada a mesma semente, o resultado seria sempre o mesmo. Dito isto, na maioria das estruturas, quando você usa o gerador de números aleatórios padrão, existe o mesmo problema de ser pseudo-aleatório.

A distribuição dos dígitos parece ser bastante semelhante aos geradores de números aleatórios padrão¹; portanto, os dígitos de π podem ser usados ​​para cenários comuns de geração de números aleatórios.

A questão é que o algoritmo provavelmente será muito lento, comparado aos geradores de números aleatórios comuns, portanto, não é muito útil na prática.


¹ Eu acredito que é verdade, mas não tenho nenhuma prova. Seria interessante (e não complicado) fazer uma comparação com base em uma grande quantidade de números.

Arseni Mourzenko
fonte
5
@NullUserException: Não, alguns geradores de números aleatórios usam uma fonte de entropia. Isso pode ser feito através de hardware especializado (a abordagem adotada pelo random.org ) ou usando fontes de entropia existentes (flutuações mensuráveis ​​nos sensores de hardware existentes, certos tipos de interações do usuário, micro-variações em certos tipos de testes de desempenho etc.) )
19712 Brian
11
@NullUserException: existem PRNG criptograficamente seguros, que ainda são pseudoaleatórios. Depois, há RNG real, que são baseados em informações do mundo real: o decaimento radioativo, ruído, etc.
Arseni Mourzenko
2
@MainMa Mas, mesmo assim, é discutível a aleatoriedade do decaimento radioativo, do ruído atmosférico, derivado da entrada do usuário etc. Só porque não reconhecemos um padrão, não significa que ele não exista.
NullUserException 19/10/12
11
@NullUserException: No ano passado, Colbeck / Renner publicou um artigo que pretende provar: "Nenhuma extensão da teoria quântica pode ter um poder preditivo aprimorado". Supondo que isso ocorra, pode haver uma fonte de entropia que é verdadeiramente imprevisível, ao invés de apenas impraticável de prever.
Brian
11
@ MainMa - você ainda realizaria testes matemáticos por aleatoriedade. Embora a física subjacente seja aleatória (até onde sabemos), isso não significa que a medição seja. Detectores de todos os tipos têm muito comportamento "interessante" no mundo real
Martin Beckett
2

A aleatoriedade dos dígitos de pi (ou, por outro lado, de qualquer outra sequência) pode ser comprovadamente testada pelos chamados "testes de bateria". Um teste de bateria popular é o Diehard Battery Test de George Marsaglia . Há também a publicação Especial NIST 800-22, que descreve vários desses testes e os resultados da aplicação desses testes a várias constantes físicas, incluindo - lo e eis - pi por mais de um milhão de bits. O resultado de pi é dado no Apêndice B do relatório e tem a seguinte aparência:

Statistical Test                            P-value
Frequency                                   0.578211
Block Frequency (m = 128)                   0.380615
Cusum-Forward                               0.628308
Cusum-Reverse                               0.663369
Runs                                        0.419268
Long Runs of Ones                           0.024390
Rank                                        0.083553
Spectral DFT                                0.010186
Non-overlapping Templates (m = 9, B = 000000001)          0.165757
Overlapping Templates (m = 9)               0.296897
Universal                                   0.669012
Approximate Entropy (m = 10)                0.361595
Random Excursions (x = +1)                  0.844143
Random Excursions Variant (x = -1)          0.760966
Linear Complexity (M = 500)                 0.255475
Serial (m = 16, 2m∇Ψ )                      0.143005

Pi é um bom gerador de sequência aleatória? Observe os resultados acima (ou pesquise os significados da variável da coluna da esquerda, se você não tem idéia do que eles significam) e verifique se ela atende às suas necessidades.

sm535
fonte
11
O leia-me do Diehard diz que ele precisa de 10 a 12 megabytes de dados binários (o melhor que pude encontrar são 32 kilobytes). Se você executá-lo com os dados ascii, o teste será bem diferente do esperado pelo aplicativo.
Minha resposta foi para a pergunta do OP e a pergunta original no Math.SE - nenhuma das quais mencionou nada sobre ascii versus dados binários ou o tamanho da amostra. Sem um conjunto de amostras grande o suficiente, como pode ser determinada a aleatoriedade estatística de qualquer sequência?
precisa saber é