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

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?

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

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

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

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.