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.

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.

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 ³² :

$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 ³² ( M = 50971 • 84263 ), dan setiap kali nilai ditemukan bahwa itu bukan bilangan bulat 32-bit yang valid (yaitu, lebih besar dari 2 ³² ), 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

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

Ruby, 32/15 = 2.1333

Ini adalah solusi Keith Randall, diimplementasikan di Ruby.

$v=3;def R;$v=$v**3%(2**32-5)end

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();
    }

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

}

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

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.

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

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