Buat generator angka acak yang lulus tes Diehard

50

Sementara ada banyak pertanyaan kode golf di sini yang melibatkan keacakan, saya belum melihat satu yang benar-benar meminta untuk membangun generator nomor pseudorandom algoritmik. Ada satu ini yang meminta Anda untuk menghasilkan aliran bit, tetapi tes keacakan yang disediakan di salah satu yang tidak sangat ketat, dan itu bukan kode-golf.

Program yang Anda tulis akan memiliki fungsi yang dapat dipanggil tunggal yang akan mengembalikan integer acak dari 0 hingga 4294967295. Fungsi ini tidak boleh memanggil perpustakaan atau fungsi lain yang tidak juga ditulis sebagai bagian dari program, terutama panggilan ke / dev / random atau pustaka rand () bawaan bahasa. Lebih khusus, Anda terbatas pada operator dasar bahasa tempat Anda bekerja, seperti aritmatika, akses larik, dan pernyataan kontrol aliran bersyarat.

Skor program Anda dihitung sebagai berikut:

Score = C / R

Di mana C adalah panjang kode dalam karakter, dan R adalah jumlah tes Diehard yang dilewati generator Anda (Jika generator angka acak Anda tidak lulus setidaknya satu tes Diehard, nilainya tak terhingga dan didiskualifikasi). Generator Anda lulus uji Diehard jika file yang dihasilkannya memberikan kisaran nilai-P yang tampaknya didistribusikan secara merata di sepanjang interval [0, 1).

Untuk menghitung R, gunakan pembangkit angka acak Anda dengan seed default untuk menghasilkan file data biner 16 MB. Setiap panggilan fungsi mengembalikan empat byte; jika fungsi Anda terlalu lambat untuk mengembalikan byte, ini akan menjadi faktor trade-off untuk mencapai skor rendah dengan seberapa sulitnya untuk menguji. Kemudian, jalankan melalui tes Diehard dan periksa nilai-P yang disediakan. (Jangan mencoba dan menerapkannya sendiri; gunakan yang disediakan di sini )

Skor terendah menang, tentu saja.

Joe Z.
sumber
Apakah kode yang memerlukan konektivitas internet diperbolehkan? (tidak akan mengakses fungsi acak online, tapi mungkin ping atau nilai-nilai panggilan api)
elssar
"Fungsi ini tidak boleh memanggil perpustakaan atau fungsi lain yang tidak ditulis sebagai bagian dari program." Itu termasuk fungsi konektivitas Internet. Generasi Anda harus murni algoritmik.
Joe Z.
Suite diehard mengharapkan file input 10-11 MB.
Primo
Tautan ke tes tampaknya rusak, inilah alternatif yang mungkin.
Arcampion
Bagaimana seharusnya ini dilakukan untuk jawaban kritik-otak saya (dihapus di bawah)? Saya pikir kode ini terlalu lambat untuk praktis
Christopher

Jawaban:

6

Mathematica, 32/15 = 2.133

x=3;Mod[x=Mod[x^2,28!-67],2^32]&

Implementasi BBS yang mudah .

File biner dihasilkan dengan:

f = %; (* assigns anonymous function declared in the previous expression to f *)
Export["random.bin", Array[f, 2^22], "UnsignedInteger32"];

Ringkasan hasil:

 1. BIRTHDAY SPACINGS TEST           .684805
 2. OVERLAPPING 5-PERMUTATION TEST   .757608/.455899
 3. BINARY RANK TEST                 .369264/.634256
 4. BINARY RANK TEST                 .838396
 5. THE BITSTREAM TEST                (no summary p-value)    
 6. OPSO, OQSO and DNA                (no summary p-value)
 7. COUNT-THE-1's TEST               .649382/.831761
 8. COUNT-THE-1's TEST                (no summary p-value)
 9. PARKING LOT TEST                 .266079
10. MINIMUM DISTANCE TEST            .493300
11. 3DSPHERES TEST                   .492809
12. SQEEZE                           .701241
13. OVERLAPPING SUMS test            .274531
14. RUNS test                        .074944/.396186/.825835/.742302
15. CRAPS TEST                       .403090/.403088/.277389

Penuh random.bindisini.

File log lengkap di sini.

2012 Arcampion
sumber
28!-67agak penghalang. Apakah ada nilai yang lebih kecil yang cocok dengan integer 64-bit?
Primo
@ primo Seperti Python, bilangan bulat Mathematica secara arbitrary-presisi secara default, sehingga tidak menimbulkan masalah.
Arcampion
Saya sedang berpikir secara khusus untuk portabilitas ke C.
primo
@primo gmplib.org
2012rcampion
21

Perl 28/13 ≈ 2.15

sub r{$s^=~($s^=$s/7215)<<8}

file log di sini

Perl 29/13 ≈ 2.23

sub r{$s^=~($s^=$s<<8)/60757}

file log di sini

Ini adalah sesuatu variasi pada Xorshift , menggunakan pembagian floating point alih-alih shift yang tepat. Keduanya lulus 13 dari 15 tes, hanya gagal tes 6 dan 7.

Saya tidak yakin berapa lama siklusnya, tetapi karena kode berikut ini tidak berakhir dalam waktu singkat, kemungkinan penuh 2 32 :

$start = r();
$i++ while $start != r();
print $i;

Perl 39/10 = 3,9

$s=$^T;sub r{~($s=$s*$s%4294969373)||r}

Catatan: jika Anda mencari PRNG Blum-Blum-Shub-esque, solusi Keith Randall jauh lebih baik daripada keduanya.

Seperti dengan solusi asli saya di bawah ini, ini juga merupakan implementasi dari Blum Blum Shub, dengan satu perbedaan utama. Saya menggunakan modulus sedikit lebih besar dari 2 32 ( M = 50971 • 84263 ), dan setiap kali nilai ditemukan bahwa itu bukan bilangan bulat 32-bit yang valid (yaitu, lebih besar dari 2 32 ), ia mengembalikan nilai berikutnya dalam rotasi sebagai gantinya. Pada dasarnya, nilai-nilai ini dipangkas, meninggalkan sisa rotasi tidak terganggu, menghasilkan distribusi yang hampir seragam.

Tampaknya telah membantu. Selain lulus 9 tes yang sama seperti sebelumnya, sekarang dengan meyakinkan melewati tes Jarak Minimum. File log sampel dapat ditemukan di sini .


Perl 33/9 ≈ 3.67 (Tidak valid?)

 $s=$^T;sub r{$s=$s*$s%4294951589}

Catatan: solusi ini mungkin dianggap tidak valid, karena 0,00037% teratas dari rentang tidak akan pernah diamati.

Implementasi Blum Blum Shub yang cepat dan kotor . Saya mengklaim hasil berikut:

 1. passed - Birthday Spacings
 2. FAILED - Overlapping Permutations
 3. passed - Ranks of 31x31 and 32x32 Matrices
 4. passed - Ranks of 6x8 Matrices
 5. FAILED - Monkey Tests on 20-bit Words
 6. FAILED - Monkey Tests OPSO, OQSO, DNA
 7. FAILED - Count the 1s in a Stream of Bytes
 8. passed - Count the 1s for Specific Bytes
 9. passed - Parking Lot Test
10. FAILED - Minimum Distance Test
11. passed - Random Spheres Test
12. FAILED - The Squeeze Test
13. passed - Overlapping Sums Test
14. passed - Runs Test
15. passed - The Craps Test

File log sampel dapat ditemukan di sini , jangan ragu untuk menyengketakan hasil apa pun. File untuk diehard dapat dibuat dengan cara berikut:

print pack('N', r()) for 1..4194304

dan kemudian menyalurkan output ke file. Jarak Minimum sepertinya sudah terlewati, tetapi jika Anda menjalankannya berkali-kali selalu sangat dekat dengan 1,0 , yang mengindikasikan kegagalan.


Detail

Secara umum, Blum Blum Shub adalah PRNG yang mengerikan, tetapi kinerjanya dapat ditingkatkan dengan memilih modulus yang baik. The M Aku telah memilih adalah 7027 • 611.207 . Kedua faktor utama ini, p dan q , memiliki residu modular 3 (mod 4) , dan gcd (φ (p-1), φ (q-1)) = 2 , yang serendah mungkin.

Meskipun ini adalah satu-satunya kriteria yang tercantum pada halaman wiki, sepertinya tidak cukup. Hampir semua modulo yang saya coba gagal setiap tes. Tetapi ada beberapa yang akan lulus beberapa tes, dan yang saya pilih tampaknya sangat bagus, untuk alasan apa pun.

Sebagai catatan terakhir, Tes 5 sendiri tampaknya menjadi indikator yang cukup baik tentang seberapa baik PRNG. Jika hampir tidak lulus Tes 5, itu akan gagal sisanya secara spektakuler.


BONUS: Perl 62/14 ≈ 4.43

$t=$^T;sub r{$t|=(($s=$s/2|$t%2<<31)^($t/=2))<<31for 1..37;$t}

Hanya untuk geekery, ini adalah versi 32-bit dari PRNG yang digunakan dalam Tetris asli untuk NES. Hebatnya, ini lulus 14 dari 15 tes!

 1. passed - Birthday Spacings
 2. passed - Overlapping Permutations
 3. passed - Ranks of 31x31 and 32x32 Matrices
 4. passed - Ranks for 6x8 Matrices
 5. passed - Monkey Tests on 20-bit Words
 6. passed - Monkey Tests OPSO, OQSO, DNA
 7. FAILED - Count the 1s in a Stream of Bytes
 8. passed - Count the 1s for Specific Bytes
 9. passed - Parking Lot Test
10. passed - Minimum Distance Test
11. passed - Random Spheres Test
12. passed - The Squeeze Test
13. passed - Overlapping Sums Test
14. passed - Runs Test
15. passed - The Craps Test

Sampel file log bisa sebelum di sini .

Memang, 1..37bit itu bukan transkripsi yang tepat. Dalam versi asli, rutin entropi diperbarui 60 kali per detik, dan kemudian ditanyai secara acak, sebagian besar tergantung pada input pengguna. Bagi siapa pun yang ingin membongkar ROM, rutinitas entropi dimulai pada 0xAB47.

Kode semu gaya-python:

carry = entropy_1 & 1
entropy_1 >>= 1
entropy_2 = (entropy_2 >> 1) | (carry << 31)
carry = (entropy_1 & 1) ^ (entropy_2 & 1)
entropy_1 |= carry << 31
primo
sumber
Ya, saya perhatikan bahwa algoritme Anda "gagal" dalam uji bitstream, tetapi sebenarnya memiliki beberapa nilai di bawah 0,999999. Namun, tes Anda tampaknya akurat.
Joe Z.
Namun, ada satu masalah, dan itu adalah bahwa angka dari 4294951589 ke 4294967295 tidak memiliki peluang untuk terjadi (walaupun saya kira itu adalah bagian dari alasan kegagalan beberapa tes Diehard).
Joe Z.
1
@ JoZeng ya, itu masalah. Ini paling jelas dalam Tes 5: proses pertama memiliki 151 ribu kata yang hilang, dan sisanya hanya 143 ribu hilang. Salah satu solusinya adalah dengan memilih modulus sedikit lebih besar dari 2 ^ 32, dan memungkinkan nilai-nilai yang terlalu besar untuk membungkus ke nol, tetapi saya tidak dapat menemukan satu yang berfungsi dengan baik. Jika saya melakukannya, saya akan memperbarui posting.
Primo
7

Python, 46/15 = 3.0666

v=3
def R():global v;v=v**3%(2**32-5);return v

Menggunakan eksponensial modular untuk menghasilkan keacakan. 2 ** 32-5 adalah prime terbesar kurang dari 2 ^ 32. (Kesepakatan yang sama dengan tidak bisa menjalankan tes # 2.)

Keith Randall
sumber
Bisakah Anda menempelkan file log?
primo
Masuk di sini: codepad.org/ZWhoGe0t
Keith Randall
1
Windows bodoh. Itu mengubah semua kejadian dari \rdan \nke \r\n, yang jelas mengacaukan hasilnya. Cara mengatasinya adalah menulis file secara langsung menggunakan f = open('file.bin', 'wb')dan f.write.
Primo
Skor baru ini memotong skor sebelumnya, jadi sekarang adalah jawaban yang diterima.
Joe Z.
Skor baru ini sudah dipotong lagi, jadi saya telah mengubah jawaban yang diterima.
Joe Z.
4

Ruby, 32/15 = 2.1333

Ini adalah solusi Keith Randall, diimplementasikan di Ruby.

$v=3;def R;$v=$v**3%(2**32-5)end
YenTheFirst
sumber
@ Joz Ini sepertinya jawaban terendah yang baru, diikat dengan jawaban Mathematica baru.
Bersepeda
3

C # 144/15 = 9,6

uint a=15,b=26,y;uint q(int n){y=(a*1414549U+876619U)^(b*889453U+344753U);b=a;a=y>>12;return(a%256)<<n;}uint r(){return q(24)|q(16)|q(8)|q(0);}

Ini melewati semua tes.

Dengan tidak terlalu banyak karakter, ia melewati TestU01.

Hasil: http://codepad.org/iny6usjV

    uint a = 15;
    uint b = 26;

    byte prng8()
    {
        uint y = ((a * 1414549U + 876619U) ^ (b * 889453U + 344753U)) >> 12;
        b = a;
        a = y;
        return (byte)y;
    }

    uint prng32()
    {
        return ((uint)prng8() << 24) | ((uint)prng8() << 16) | ((uint)prng8() << 8) | (uint)prng8();
    }
Andrew P.
sumber
2

C # - 103/14 = 7.36

double j=999;uint N(){uint i=0,n=0;for(;i++<4;n=n*256+(uint)j%256)for(j/=277;j<100000;j*=j);return n;}

Hasil

Lewati semua kecuali tes # 6
Lihat hasil di http://codepad.org/k1NSoyQW

Penjelasan

C # tidak bisa bersaing dengan Ruby dan Python untuk mendapatkan kesederhanaan, seperti biasa, tetapi saya senang mencoba. Tentu saja ada nilai-nilai lain yang akan berfungsi dengan baik (yaitu, nilai awal untuk j = 999, dan pembagi = 277). Saya memilih ini setelah eksperimen singkat.

Dengan pembungkus pembuatan file

class R
{
    public static void Main(string[] args)
    {
        var r = new R();
        using (var f = new System.IO.FileStream(".\\out.bin", System.IO.FileMode.Create, System.IO.FileAccess.Write, System.IO.FileShare.Read))
        using (var b = new System.IO.BinaryWriter(f))
        {
            for (long i = 0; i < 12 * 1024 * 1024; i += 4)
            {

                b.Write(r.N());
            }
        }
    }

    double j = 999;

    uint N()
    {
        uint i = 0, n = 0;
        for (; i++ < 4; n = n * 256 + (uint)j % 256)
            for (j /= 277; j < 100000; j *= j) ;
        return n;
    }

}
Richard II
sumber
1

Python, 41/15 = 2.73333

v=0
def R():global v;v=hash(`v`);return v

Agak curang menggunakan built-in fungsi hash, tetapi adalah built-in, sehingga tidak ada lagi kecurangan daripada menggunakan builtin lainnya, seperti len. Di sisi lain, saya harus membayar untuk global v;pernyataan ...

Lulus semua tes Diehard (saya punya masalah dengan tes # 2, itu SEGV pada mesin OSX saya. Untuk skor saya, saya menganggap itu akan lulus).

Inilah driver untuk menghasilkan file 16MB:

import sys
for i in xrange(1<<22):
  r=R()
  sys.stdout.write('%c%c%c%c'%(r&255, r>>8&255, r>>16&255, r>>24&255))
Keith Randall
sumber
"Fungsi ini tidak boleh memanggil perpustakaan apa pun atau fungsi lain yang tidak juga ditulis sebagai bagian dari program, terutama panggilan ke / dev / acak atau perpustakaan built-in rand () library." Maaf, tapi itu mendiskualifikasi entri Anda.
Joe Z.
Agar lebih jelas, "len" juga akan mendiskualifikasi entri Anda.
Joe Z.
Di mana Anda menggambar garis? Apakah +fungsi bawaan, dan karenanya didiskualifikasi?
Keith Randall
6
Tetapi dalam banyak bahasa, operator dan fungsinya identik. Lihat +dan__add__ dalam python, atau operator kelebihan dalam c ++. Saya tahu saya agak suka membelah rambut, jadi pertimbangkan contoh ini. Dengan python, bisakah saya membuat peta seperti ini {'a':5}:? Anda mungkin akan mengatakan ya, tetapi kemudian mempertimbangkan bahwa di balik selimut, hash('a')dipanggil ketika Anda melakukan itu.
Keith Randall
2
Saya kira saya akan menarik garis ketika Anda perlu merujuk fungsi secara sintaksis dengan cara itu. Jika Anda dapat menemukan retasan dalam Python yang akan memungkinkan Anda untuk langsung mengakses alamat peta tanpa secara sintaksis merujuk ke fungsi "hash", saya mungkin menerimanya.
Joe Z.
1

C, 38/15 = 2.533

long long x;f(){return(x+=x*x+9)>>32;}

Saya tidak bisa mendapatkan tes Diehard bekerja pada mesin saya, tetapi melewati suite PractRand hingga 8GB output jadi saya berasumsi itu akan melewati semuanya.

pengguna1502040
sumber
0

Brain-Flak , 344 / (tertunda)

<>((()()){})<> push the amount of iterations to do for the PRNG
(((((((((((((((((((((((((((((((((((()()()){}()){})){}{}){()()()()({}[()])}{})){}{})){}{})()){}{})()){}{})){}{})){}{}){}())){}{})){}{})()){}{})()){}{})){}{})){}{})()){}{})()){}{}) push M (one of the values for the Blum Blum Shub PRNG
((((((((((((()()()){}){}){})){}{}){()({}[()])}{}){}())){}{})()){}{}) push s see above
<>{({}[()])<>starts the loop
(({({})({}[()])}{}) squares the current number
(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]({}))mods by M
<>}{}<>loop ends

Cobalah online!

Ini berfungsi dengan baik tetapi tautan tes diehard semuanya rusak :( jadi sampai kami mendapatkan yang baru saya tidak memiliki skor akhir

Ini menggunakan Blum Blum Shub PRNG sehingga harus melewati sebagian besar kasus. Jumlah yang digunakan cukup besar, tidak ada pola yang akan muncul dalam 16 MB kasus uji

Christopher
sumber
jika ini tidak valid, beri tahu saya
Christopher
1
Saya menghitung 344. Teorema: Tidak ada program Brain-flak yang sepenuhnya golf memiliki jumlah byte yang ganjil.
user202729
0

Objective-C, 40/1 = 40

Pendekatan yang cukup pintar, mengeksploitasi .hashagak curang di sini, tapi saya suka

for(int v=9;v=@(v).hash;printf("%i",v));
Albert Renshaw
sumber