Terinspirasi secara acak dengan tangan terikat :

Target

Tujuan dari tantangan ini adalah untuk menulis sebuah program yang menghasilkan bit stream pseudorandom, yang merupakan string 1s dan 0s yang tampaknya murni acak, tetapi sebenarnya dihasilkan dengan cara deterministik. Program Anda harus menampilkan string 1 dan 0s (dengan spasi kosong opsional) dan harus melewati persyaratan berikut:

1. Dengan waktu dan memori yang tidak terbatas, program Anda harus terus menghasilkan string 1s dan 0s selamanya
2. Program Anda harus mengeluarkan lebih dari 1000 bit acak dalam waktu sekitar satu menit, pada mesin yang masuk akal. Jika persyaratan ini tidak mungkin, maka saya akan menguranginya.
3. String bit dapat diulang, tetapi panjang bagian berulang harus lebih dari 1000 bit.
4. String bit harus lulus sebanyak mungkin tes keacakan (dijelaskan di bawah) sebanyak mungkin.
5. Program tidak boleh mengambil input dari sumber eksternal apa pun atau menggunakan fungsi bawaan () - seperti apa pun.
6. Karena persyaratan di atas, program harus menampilkan string bit yang persis sama setiap kali dijalankan.

Uji Keacakan # 1

String bit pseudorandom tidak boleh menyertakan pola yang jelas pada inspeksi visual.

Uji Keacakan # 2 (dapat berubah berdasarkan komentar)

String bit harus mengandung distribusi yang sama antara 1s dan 0s. Untuk menguji ini (dan hal lainnya juga), aliran bit dipecah menjadi segmen yang panjangnya 3 bit, seperti 101|111|001.

Dari semua segmen ini, 1/8 dari mereka harus memiliki tiga 1s dan tidak ada 0s, 3/8 dari mereka harus memiliki dua 1s dan satu 0, 3/8 dari mereka harus memiliki satu 1 dan dua 0s, dan 1/8 dari mereka seharusnya tidak memiliki 1 dan tiga 0.

Uji Keacakan # 3

"Jalankan" didefinisikan sebagai serangkaian bit berurutan yang semuanya memiliki nilai yang sama. String 1001001110memiliki tiga kali run ukuran 1 ( 1..1.....0), dua kali run ukuran 2 ( .00.00....) dan satu kali run dari ukuran 3 ( ......111.). Perhatikan bahwa menjalankan tidak tumpang tindih.

Dari string 1000 bit acak, harus ada sekitar 250 run ukuran 1, 125 run ukuran 2, 62 run ukuran 3, dll. Secara umum, untuk run size R, harus ada sekitar 1000/(2**(R+1))run dari ukuran itu.

Uji Keacakan # 4

840 bit pertama dibagi menjadi dua bagian masing-masing 420 bit. Setiap bit di babak pertama dibandingkan dengan bit yang sesuai di babak kedua. Dua bit harus cocok dengan sekitar lima puluh persen dari waktu.

Berikut ini adalah kode sumber dari program Perl yang melakukan tes 2 hingga 4. Sampai sekarang, itu memerlukan string bit tidak mengandung spasi.

Waktu Kriteria Kemenangan yang Objektif!

Pemenangnya adalah program yang lulus semua 6 persyaratan dan semua tes keacakan sejauh tidak bisa dibedakan dari keacakan. Jika beberapa program mencapai ini, maka program yang membutuhkan waktu paling lama untuk mengulang akan menang. Jika beberapa program mencapai ini, maka saya mungkin harus menemukan lebih banyak tes keacakan untuk bertindak sebagai tie-breaker.

C, 61

main(s,n){for(n=1u<<31;putchar((s%=n)/(n/2)&1|48);s*=65539);}

Ya, saya tahu ini bukan kode golf. Ini jelas merupakan anti-solusi ... tetapi cukup memenuhi kriteria Anda.

keluar | head -c840
$ ./a.out | head -c840 | perl tester.pl
Test 2: 1 (1) 2.93333333333333 (3) 3.1 (3) 0.96666666666666667 (1)
Uji 3: 214 99 71 24 7 5 1 1 2 2
Uji 4: 0.495238095238095

Panjang periode adalah 2²⁹.

Mathematica 78 53 karakter

Angka-angka dari representasi biner dari Pi tampaknya berperilaku seolah-olah mereka diproduksi secara kacau meskipun ini tidak terbukti.

Rutin sederhana berikut secara deterministik mengembalikan sebagai string digit biner pi, yang sesuai dengan ddigit desimal:

f[d_]:=ToString@FromDigits@RealDigits[N[Pi,d],2][[1]]

Pemakaian

Jika kami meminta rekanan dari 301 digit desimal Pi, kami menerima 1000 digit biner.

f[301]
StringLength[%]

(* out *)
1100100100001111110110101010001000100001011010001100001000110100110001001100011001100010100010111000000011011100000111001101000100101001000000100100111000001000100010100110011111001100011101000000001000001011101111101010011000111011000100111001101100100010010100010100101000001000011110011000111000110100000001001101110111101111100101010001100110110011110011010011101001000011000110110011000000101011000010100110110111110010010111110001010000110111010011111110000100110101011011010110110101010001110000100100010111100100100001011011010101110110011000100101111001111110110001101111010001001100010000101110100110100110001101111110110101101011000010111111111101011100101101101111010000000110101101111110110111101110001110000110101111111011010110101000100110011111101001011010111010011111001001000001000101111100010010110001111111100110010010010010100001100110010100011110110011100100010110110011110111000010000000000111110010111000101000010110001110111111000001011001100011011010010010000011011000011100011

1000 (* characters *)

Karena Pi adalah bilangan irasional, tidak ada periode. Namun, akan ada kendala praktis karena perangkat keras berjalan.

Tes 1 Terlihat bagus untuk saya.

Tes 2

d=301;
Partition[RealDigits[N[Pi,d],2][[1]],{3}];
Tally[%]
(* out *)
{{{1,1,0},35},{{0,1,0},45},{{0,0,0},41},{{1,1,1},40},
{{0,1,1},50},{{1,0,1},32},{{1,0,0},43},{{0,0,1},47}}

Pemeriksaan lebih teliti:

d=10^6;
Partition[RealDigits[N[Pi,d],2][[1]],{3}];
Tally[%]

{{{1,1,0},138565},{{0,1,0},138146},{{0,0,0},138260},{{1,1,1},138427},
{{0,1,1},139119}, {{1,0,1},138404},{{1,0,0},137926},{{0,0,1},138462}}

Tes 3: Berlari

d=10^6;
res3=SortBy[Tally@Split@RealDigits[N[Pi,d],2][[1]],Last]/.{a_,b_}:> {Length[a],b}
ListPlot[res3 ,AxesLabel-> {"Run Length","Runs"},AxesOrigin->{0,0}]

Saya menjalankan sejumlah besar kasus untuk memeriksa distribusi proses secara sistematis. Dalam kira-kira 3 juta digit biner, ada 830k berjalan dari 1, 416k berjalan dari 2, 208k berjalan dari 3, 104k berjalan dari 4, dll.

Tes 4: Pencocokan data bagian pertama dan kedua

Pertandingan adalah 212 kasus 0 dan 2; ketidakcocokan adalah 208 kasus di mana jumlah dari masing-masing digit adalah 1.

d=301;
Tally[Plus@@Partition[Take[RealDigits[N[Pi,d],2][[1]],840],420]]

(* out *)
{{1,208},{0,108},{2,104}}

Pengaturan waktu

Dibutuhkan di bawah dua detik untuk menghitung 3321928 digit biner (sesuai dengan 10 ^ 6 angka desimal).

(r=f[10^6]);//AbsoluteTiming
StringLength[r]

(*out*)
{1.785928,Null}    
3321928

Python, 90

g=[19]
print(''.join("01"[(g.append((11*g[-1]+13)%1024)or g[-1])>512]for i in range(1000)))

gadalah nilai benih. Pengambilan sampel secara acak menunjukkan distribusi yang luar biasa normal, pengulangan sampel secara acak dari sampel berarti menghasilkan rata-rata 0.506dan standar deviasi .0473(ukuran sampel 1000). Sayangnya, keacakan sangat sensitif terhadap benih awal. Benih dalam kode di atas memberi saya keacakan yang terbaik: p

MEMPERBARUI

Mari kita lihat bagaimana kode ini bertahan pada pengujian OP:

Tes # 1

Yang ini agak subyektif ... tapi kelihatannya tidak biasa bagi saya.

Tes # 2

Tiga 1: 0.141
Dua 1: 0.371
Satu 1: 0.353
Nol 1: 0.135

Tes # 3

Dijalankan berdasarkan ukuran:

8: 11
7: 3
6: 7
5: 13
4: 32
3: 67
2: 119
1: 216

Tes # 4

Rasio persamaan: 0.94 Ini adalah salah ketik. Akan segera diperbarui dengan nomor yang benar.

Haskell 74 58

main=print$iterate(read.take 9.show.(^3))7>>=show.(`mod`2)

Berkat shiona untuk penyederhanaannya. Hasil:

/ pseudorandom | head -c 1000

./pseudorandom | head -c 1000 | perl test.pl

Tes 2: 0.966666666666667 (1) 2.4 (3) 3.3 (3) 1.33333333333333 (1)

Tes 3: 260 108 66 33 15 11 5 2

Tes 4: 0.495238095238095

Ini juga merupakan generator pseudo-acak yang mengerikan (mirip dengan yang digunakan oleh von-Neuman). Bagi mereka yang tidak sadar concatMap == (=<<) == flip . (>>=)(untuk daftar)

Pertanyaannya pada dasarnya setara dengan "mengimplementasikan stream cipher". Jadi saya mengimplementasikan RC4, karena ini relatif sederhana.

Saya tidak menggunakan kunci, dan menjatuhkan 100000 bit pertama, karena awal RC4 agak bias, terutama karena saya melewatkan jadwal kunci. Tapi saya berharap untuk lulus ujian Anda bahkan tanpa itu (menghemat 20 karakter kode).

Biasanya satu akan menghasilkan byte penuh per siklus, tetapi mengkonversi ke biner agak jelek di C #, jadi saya hanya membuang semuanya kecuali yang paling tidak signifikan.

var s=Enumerable.Range(0,256).ToArray();
byte i=0,j=0;
for(int k=0;;k++)
{
    i++;
    j+=(byte)s[i];
    var t=s[i];s[i]=s[j];s[j]=t;
    if(k>99999)
        Console.Write(s[i]+s[j]&1);
}

Atau tanpa spasi:

var s=Enumerable.Range(0,256).ToArray();byte i=0,j=0;for(int k=0;;k++){i++;j+=(byte)s[i];var t=s[i];s[i]=s[j];s[j]=t;if(k>99999)Console.Write(s[i]+s[j]&1);}

C #, 156 karakter, bekerja dalam mode pernyataan LinqPad. Untuk program C # lengkap tambahkan boilerplate biasa.

Kita juga dapat menggunakan primitif kripto bawaan (solusi Penipu):

var h=SHA256.Create();for(BigInteger i=0;;i++){Console.Write(h.ComputeHash(i.ToByteArray())[0]%2);}

(C #, 99 karakter, berfungsi dalam mode pernyataan LinqPad. Untuk compiler C # yang normal, Anda perlu menambahkan sedikit boilerplate)

Output dari fungsi hash kriptografis dirancang agar tidak dapat dibedakan dari data acak, jadi saya berharap ini untuk lulus semua tes keacakan (mati lebih keras, ...) Anda melemparkannya, tapi saya terlalu malas untuk menguji.

C, 52 karakter

main(a){for(a=1;putchar(48+a%2);a=a/2^-(a%2)&576);}

Ini adalah LFSR 10 bit, hasil pengujian:

$ ./a.out |head -c 1000 | perl randtest.pl
Test 2: 1.13333333333333 (1) 2.86666666666667 (3) 3.16666666666667 (3) 0.833333333333333 (1)
Test 3:  251 122 64 32 16 8 4 2  1
Test 4: 0.466666666666667

Sage / Python

Program ini mencetak digit biner paling kanan yang umum untuk setiap menara eksponensial yang cukup tinggi dari bentuk 3 ^{3 3 3 . .} . Untuk semua yang bisa dihasilkan secara layak, ini adalah angka biner paling kanan dari nomor Graham . Urutan digit tidak terbatas, dan tidak periodik.

m = 1; x = 3; last = 0
while True:
    m *= 2; x = pow(3,x,m); l = len(bin(x))
    print '1' if l > last else '0',
    last = l

Untuk 1000 digit, ini membutuhkan waktu kurang dari 2 detik; Namun, waktu akan meningkat lebih cepat daripada linear dalam jumlah digit.

Hasil pengujian menggunakan program OP adalah

Test 2: 1.26666666666667 (1) 3.16666666666667 (3) 2.8 (3) 0.766666666666667 (1)
Test 3:  268 126 61 30 20 7 2  1 1
Test 4: 0.466666666666667

(Lihat Apakah digit paling kanan dari G acak? Untuk lebih dari 32.000 digit dan tes statistik tambahan.)

Jawa, 371 317

Berdasarkan LFSR 128 bit (ketukan bit berasal dari xilinx app note 52 )

EDIT: Saya tidak puas menggunakan BigInteger sehingga versi ini tidak. Menyimpan beberapa karakter. Output mungkin sedikit kurang acak karena saya tidak bisa memikirkan metode 'seeding' yang baik.

Kode Baru: Argumen: BITS_TO_PRINT

class R{public static void main(String[]a){int L=65536;int[]v={0,128,126,101,99};int[]b=new int[L];for(int x=0;x<L;x++)b[x]=(x*x)&1;for(int i=0;i<Integer.parseInt(a[0])+L;i++){if(1!=(b[v[1]]^b[v[2]]^b[v[3]]^b[v[4]]))b[v[0]]=1;else b[v[0]]=0;if(i>L)System.out.print(b[v[0]]);for(int j=0;j<5;j++)v[j]=(v[j]-1)&(L-1);}}}

Versi Lama: Argumen: SEED, BITS_TO_PRINT

import java.math.BigInteger;class R{public static void main(String[]a){BigInteger v=new BigInteger(a[0]);BigInteger m=new BigInteger("ffffffffffffffffffffffffffffffff",16);for(int i=Integer.parseInt(a[1]);i>0;i--){v=v.shiftLeft(1);if(!(v.testBit(128)^v.testBit(126)^v.testBit(101)^v.testBit(99))){v=v.setBit(0);}v=v.and(m);java.lang.System.out.print(v.testBit(0)?1:0);}}}

Versi Baru: Contoh output, bit = 100:

011001100111000110010100100111011100100111000111001111110110001001100000100111111010111001100100011

JavaScript - 1ms to 2ms untuk 1000 pseudo-random bits (139ms to 153ms untuk 100000 bits)

Solusi ini menggunakan fakta bahwa akar kuadrat itu tidak rasional, dan dengan demikian cukup acak. Pada dasarnya, dibutuhkan akar kuadrat dari 2 untuk memulai, mengubahnya menjadi biner, membuang bagian terkemuka yang cocok dengan root sebelumnya, menambahkannya ke string acak, mengulangi dengan angka yang lebih tinggi berikutnya (atau kembali ke 2 jika angka tersebut diulang dan setidaknya 30 bit panjang), dan mengembalikan string acak setelah cukup lama.

var getDeterministicPseudoRandString = function(length){
    var randString = '';

    var i = 2;
    var prevRand = '';

    outerLoop:
    while(randString.length < length){
        var nextRand, nextFullRand = Math.sqrt(i++).toString(2).substring(1).replace('.', '');
        nextRand = nextFullRand;
        for(var j = prevRand.length; j > 0; j--){
            var replaceString = prevRand.substring(0, j);

            nextRand = nextFullRand;

            if(nextFullRand.indexOf(replaceString) == 0){
                if(j == prevRand.length && j > 30){
                    //start i over at 2
                    console.log('max i reached: ' + i);

                    i = 2;
                    continue outerLoop;
                } else {
                    nextRand = nextFullRand.replace(replaceString, '');
                }

                break;
            }
        }
        prevRand = nextFullRand;

        randString += nextRand;
    }

    return randString.substring(0, length);//Return the substring with the appropriate length
};

Saya belum menjalankan tes, tetapi saya membayangkan itu akan berhasil pada mereka. Ini biola sehingga Anda bisa melihatnya beraksi. Untuk waktu saya, saya hanya menjalankan program beberapa kali dan mengambil nilai tercepat dan paling lambat sebagai rentang.

Python

import hashlib
x=''
while 1:
    h=hashlib.sha512()
    h.update(x)
    x=h.digest()
    print ord(x[0])%2

Seharusnya memiliki periode sekitar 2 ^ 512.

perl, 44 byte

Saya tahu ini bukan kode golf, tapi saya selalu suka mengambil bit orde rendah dari fungsi kuadratik sederhana, misalnya:

$x=1/7;print substr($x*=4-4*$x,9,1)%2while 1

Periode lebih dari 3 miliar, tetapi saya sudah kehabisan ruang disk untuk menghitung lebih banyak.