Czy możesz użyć Pi jako prostego generatora liczb losowych?

30

Ostatnio widziałem to pytanie na stronie math.SE. Zmusiło mnie to do myślenia. Czy Pi można wykorzystać jako surowy generator liczb losowych? Mam na myśli, że wyniki są dobrze znane (jak długo do tej pory obliczono liczbę Pi?), Ale Pi wydaje się dość losowy, gdy jest pobierany 1 cyfra na raz.

Czy to w ogóle ma sens?

Earlz
źródło
Gdzie będą te losowe liczby?
NullUserException
2
Teoretycznie może być, ale prawdopodobnie byłby mniej optymalny niż obecne metody. Po prostu instynkt, ale wydaje się, że losowa pula jest w ten sposób większa i ma mniejszy narzut.
Rig
@NullUserException Nie jestem pewien ... Zastanawiałem się, czy można ich użyć WSZYSTKO. Zakładam, że zdecydowanie nie byłoby to w przypadku kryptografii ”
Earlz
3
@FrustratedWithFormsDesigner - jest to część pakietu ent. Wykorzystuje liczby losowe do obliczenia pola okręgu wpisanego w kwadrat, a na podstawie tego można obliczyć pi. Wykorzystując bity liczby pi jako liczby losowe, pewną elegancją jest wykorzystanie tych danych do obliczenia liczby pi.
1
@FrustratedWithFormsDesigner ent to zestaw kodów do analizy pseudolosowości wiązki bajtów. Jednym z zawartych w nim testów jest Monte Carlo do obliczania liczby pi i porównywania obliczeń losowych z rzeczywistą wartością, aby zobaczyć, jak jest losowa.

Odpowiedzi:

50

Kopanie ze strony http://www.befria.nu/elias/pi/binpi.html w celu uzyskania wartości binarnej liczby pi (aby łatwiej było przekonwertować ją na bajty niż próbować używać cyfr dziesiętnych), a następnie uruchomić ją przez ent Dostaję następujące do analizy losowego rozkładu bajtów:

Entropia = 7,954093 bitów na bajt.

Optymalna kompresja zmniejszyłaby rozmiar tego pliku 4096 bajtów o 0 procent.

Rozkład chi-kwadrat dla 4096 próbek wynosi 253,00 i losowo przekroczyłby tę wartość 52,36 procent razy.

Średnia arytmetyczna bajtów danych wynosi 126,6736 (127,5 = losowo).

Wartość Monte Carlo dla Pi wynosi 3.120234604 (błąd 0,68 procent).

Współczynnik korelacji szeregowej wynosi 0,028195 (całkowicie nieskorelowany = 0,0).

Tak więc, użycie pi do losowych danych dałoby ci dość losowe dane ... wiedząc, że są to dobrze znane losowe dane.


Z powyższego komentarza ...

W zależności od tego, co robisz, ale myślę, że możesz użyć dziesiętnych pierwiastków kwadratowych z dowolnej liczby pierwszej jako generatora liczb losowych. Powinny one mieć przynajmniej równomiernie rozmieszczone cyfry. - Paxinum

Tak więc obliczyłem pierwiastek kwadratowy z 2 w postaci binarnej, aby rozwiązać ten sam zestaw problemów. Używając iteracji Wolframa napisałem prosty skrypt perla

#!/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);

Uruchomiłem to dla pierwszych 10 pasujących A095804, więc byłem pewien, że mam sekwencję. Wartość v n jak zapisana binarnie z punktem binarnym umieszczonym po pierwszej cyfrze daje przybliżenie pierwiastka kwadratowego z 2.

Użycie ent przeciwko tym danym binarnym powoduje:

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).

źródło
Właśnie tego rodzaju odpowiedzi szukałem. Nie mam pojęcia, jak obliczyć wszystkie tego typu rzeczy
Earlz,
Nawet jeśli rozkład liczb jest dość losowy, czy nie musisz znaleźć sposobu, aby losowo wybrać jego część?
Blumer,
1
@Blumer nr. Losowość mierzy się za pomocą sekwencji liczb. Mówi się, że sekwencja cyfr pi jest losowa. Zobacz en.wikipedia.org/wiki/Statistic_randomness
Simon Bergot
11
Całkowita racja. A ponieważ są to dobrze znane losowe dane, nigdy nie waż się wykorzystywać ich do celów kryptograficznych.
Falcon
3
+1 za „dobrze znane losowe dane”. Jeśli potrzebujesz losowych danych, których nikt nie zgadnie, pi nie jest dla ciebie, jeśli z jakiegoś powodu potrzebujesz tylko kilku losowych liczb, działa dobrze.
jmoreno
5

Cóż, oprócz innych właściwości generatora liczb losowych, prawdopodobnie chcesz, aby był on liczbą normalną . I kilka odpowiedzi z pytania matematycznego.

psr
źródło
2

Taki generator byłby generatorem pseudoliczbowym, tzn. Biorąc pod uwagę to samo ziarno, wynik byłby zawsze taki sam. To powiedziawszy, w większości platform, kiedy używasz standardowego generatora liczb losowych, istnieje ten sam problem bycia pseudolosowym.

Rozkład cyfr wydaje się być dość podobny do standardowych generatorów liczb losowych¹, więc cyfry π mogą być użyte w zwykłych scenariuszach generowania liczb losowych.

Problem polega na tym, że algorytm będzie prawdopodobnie bardzo wolny w porównaniu ze zwykłymi generatorami liczb losowych, więc nie jest zbyt przydatny w praktyce.


¹ Wierzę, że to prawda, ale nie mam żadnych dowodów. Interesujące (i nie komplikujące) byłoby porównanie na podstawie dużej liczby liczb.

Arseni Mourzenko
źródło
5
@NullUserException: Nie, niektóre generatory liczb losowych używają źródła entropii. Można tego dokonać albo za pomocą specjalistycznego sprzętu (podejście stosowane przez random.org ) lub przy użyciu istniejących źródeł entropii (mierzalne fluktuacje w obrębie istniejących czujników sprzętowych, określone rodzaje interakcji użytkownika, mikrozmienność niektórych rodzajów testów wydajności itp. ).
Brian
1
@NullUserException: istnieją kryptograficznie bezpieczne PRNG, które są nadal pseudolosowe. Są też prawdziwe RNG oparte na danych ze świata rzeczywistego: rozpad radioaktywny, hałas itp.
Arseni Mourzenko
2
@MainMa Ale nawet wtedy losowość rozpadu promieniotwórczego, hałasu atmosferycznego pochodzącego z danych wejściowych użytkownika itp. Jest dyskusyjna. To, że nie rozpoznajemy wzoru, nie oznacza, że ​​nie istnieje.
NullUserException
1
@NullUserException: W ubiegłym roku Colbeck / Renner opublikował artykuł, który ma udowodnić: „Żadne rozszerzenie teorii kwantowej nie mogłoby poprawić mocy predykcyjnej”. Zakładając, że tak się utrzyma, może istnieć źródło entropii, które jest naprawdę nieprzewidywalne, a nie tylko niemożliwe do przewidzenia.
Brian,
1
@MainMa - nadal przeprowadzałbyś matematyczne testy losowości. Chociaż podstawowa fizyka jest losowa (zgodnie z naszą najlepszą wiedzą), nie oznacza to, że pomiar jest. Detektory wszystkich typów mają wiele „interesujących” zachowań w prawdziwym świecie
Martin Beckett
2

Losowość cyfr liczby pi (lub, w tym przypadku, dowolnej innej sekwencji) można prawdopodobnie przetestować za pomocą tak zwanych „testów baterii”. Jednym z popularnych testów baterii jest Diehard Battery Test George'a Marsaglii . Istnieje również specjalna publikacja NIST 800-22, która opisuje szereg takich testów i wyniki zastosowania tych testów do szeregu stałych fizycznych, w tym - lo i patrz - pi dla ponad miliona bitów. Wynik pi jest podany w załączniku B do raportu i wygląda następująco:

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

Czy pi jest dobrym generatorem losowych sekwencji? Spójrz na powyższe wyniki (lub wyszukaj znaczenie zmiennej lewej kolumny, jeśli nie masz pojęcia, co one oznaczają) i sprawdź, czy spełnia twoje potrzeby.

sm535
źródło
1
Przeczytaj mnie dla Diehard mówi, że potrzebuje około 10-12 megabajtów danych binarnych (najlepsze, co mogłem znaleźć, to 32 kilobajty). Jeśli uruchomisz go z danymi ascii, test byłby całkiem daleko od tego, czego oczekuje aplikacja.
Moja odpowiedź dotyczyła pytania OP i pierwotnego pytania na Math.SE - żadne z nich nie wspominało o danych ascii w porównaniu z danymi binarnymi ani o długości próbki. Jak można ustalić statystyczną losowość dowolnej sekwencji bez wystarczająco dużego zestawu próbek?
sm535