Dalam artikel ini, saya menyajikan urutan kuasi-acak rendah divergensi baru yang memberikan peningkatan signifikan terhadap urutan modern, seperti Sable, Niederreiter, dll.


Gambar 1. Perbandingan berbagai urutan kuasi-acak dengan divergensi rendah. Perhatikan bahwa yang saya usulkan $$$R$ -setelah menciptakan lebih banyak poin yang terdistribusi secara merata daripada semua metode lainnya. Selain itu, semua metode lain memerlukan pemilihan parameter dasar yang cermat, dan dalam kasus pemilihan yang salah menyebabkan degenerasi (misalnya, di kanan atas)

Topik yang dibahas dalam artikel ini

• Urutan Divergensi Rendah dalam Satu Dimensi
• Metode divergensi rendah dalam dua dimensi
• Jarak pengepakan
• Set Perbedaan Rendah Multiclass
• Urutan semu acak pada permukaan bola
• Ubin bidang semi-periodik
• Masker dithering dalam grafis komputer

Beberapa waktu yang lalu, posting ini diposting di beranda Hacker News. Anda bisa membaca pembahasannya di sana .

Pendahuluan: acak versus kuasi acak

Pada Gambar 1, Anda dapat melihat bahwa dengan pengambilan sampel acak seragam sederhana dari suatu titik di dalam satuan persegi, akumulasi titik diamati, dan juga area tanpa titik ("white noise") muncul. Sebuah urutan kuasi-acak dengan divergensi rendah adalah metode untuk membangun (tak terbatas) poin berurutan dengan cara deterministik, yang mengurangi kemungkinan akumulasi (divergensi), sambil memastikan cakupan yang seragam dari seluruh ruang ("blue noise").

Urutan acak semu dalam satu dimensi

Metode untuk membuat urutan quasirandom sepenuhnya ditentukan dengan divergensi rendah dalam satu dimensi sangat dipelajari dan dipecahkan secara umum. Dalam posting ini, saya terutama akan mempertimbangkan urutan terbuka (tak terbatas), pertama dalam satu dimensi, dan kemudian beralih ke dimensi yang lebih tinggi. Keuntungan mendasar dari sekuens terbuka (mis., Dapat diperpanjang dalam $$$n$ ) terletak pada kenyataan bahwa jika total kesalahan berdasarkan jumlah anggota yang terbatas terlalu besar, maka urutan dapat diperluas tanpa membuang semua poin yang dihitung sebelumnya. Ada banyak cara untuk membangun urutan terbuka. Anda dapat membagi tipe yang berbeda ke dalam kategori dengan metode membangun parameter dasar (hiper):

• fraksi irasional: Kronecker, Richtmayer, Ramshaw
• (Gonta-ganti) bilangan prima: Van der Corpute, Holton, Foret
• Polinomial Tak Tereduksi: Niederreiter
• Polinomial primitif: Sable

Demi singkatnya, dalam posting ini saya terutama akan membandingkan rekursif aditif baru $$$R$ - urutan yang termasuk dalam kategori pertama, yaitu, untuk metode rekursif berdasarkan bilangan irasional (sering disebut urutan Kronecker, Weil atau Richtmeier), yang merupakan peringkat 1 kisi, dan urutan Holton, yang didasarkan pada urutan van der Corpute satu dimensi canonical. Urutan rekursif kanonik Kronecker didefinisikan sebagai:

$$

$$R_1 (\ alpha): \; \; t_n = \ {s_0 + n \ alpha \}, \ quad n = 1,2,3, ...$$

dimana $$$\ alpha$ - bilangan irasional. Perhatikan bahwa entri $$$\ {x \}$ menunjukkan bagian pecahan $$$x$ . Dalam perhitungan, fungsi ini sering dinyatakan sebagai

$$

$$R_1 (\ alpha): \; \; t_n = s_0 + n \ alpha \; (\ textrm {mod} \; 1); \ quad n = 1,2,3, ...$$

Di $$$s_0 = 0$ beberapa anggota urutan pertama $$$R (\ phi)$ sama dengan:

$$

$$t_n = 0,618, \; 0,236, \; 0,854, \; 0,472, \; 0,090, \; 0,708, \; 0,327, \; 0,944, \; 0,562, \; 0,180, \; 798, \; 416, \; 0,034, \; 0,652, \; 0,271, \; 0,888, ...$$

Penting untuk diperhatikan artinya $$$s_0$ tidak mempengaruhi karakteristik umum dari urutan, dan dalam hampir semua kasus sama dengan nol. Namun, dalam menghitung opsi $$$s \ neq 0$ memberikan tingkat kebebasan tambahan, yang sering bermanfaat. Jika $$$s \ neq 0$ , maka urutan tersebut sering disebut "urutan kisi bergeser". Terlepas dari kenyataan bahwa secara default $$$s = 0$ Saya percaya bahwa ada pertimbangan teoretis dan praktis yang nilainya harus standar $$$s = 1/2$ . Nilai $$$\ alpha$ memberikan perbedaan terkecil yang mungkin jika $$$\ alpha = 1 / \ phi$ dimana $$$\ phi$ - Ini adalah rasio emas. Yaitu

$$

$$\ phi \ equiv \ frac {\ sqrt {5} +1} {2} \ simeq 1.61803398875 ...;$$

Sangat menarik untuk dicatat bahwa ada banyak nilai lain. $$$\ alpha$ , yang juga memungkinkan kami untuk mendapatkan perbedaan yang optimal, dan mereka semua terkait satu sama lain oleh transformasi Mobius

$$

$$\ alpha ’= \ frac {p \ alpha + q} {r \ alpha + s} \ quad \ textrm {untuk semua bilangan bulat} \; p, q, r, s \ quad \ textrm {sedemikian rupa} | ps-qr | = 1$$

Sekarang kita membandingkan metode rekursif ini dengan urutan van der Korput yang terkenal dengan urutan terbalik pembuangan [ van der Korput, 1935 ]. Sekuens Van der Corpute sebenarnya adalah sekuens sekuens, yang masing-masing didefinisikan oleh hiperparameter unik $$$b$ . Beberapa anggota pertama dari urutan dengan b = 2 sama:

$$

$$t_n ^ {[2]} = \ frac {1} {2}, \ frac {1} {4}, \ frac {3} {4}, \ frac {1} {8}, \ frac {5} {8}, \ frac {3} {8}, \ frac {7} {8}, \ frac {1} {16}, \ frac {9} {16}, \ frac {5} {16}, \ frac {13} {16}, \ frac {3} {16}, \ frac {11} {16}, \ frac {7} {16}, \ frac {15} {16}, ...$$

Pada bagian selanjutnya, kami membandingkan karakteristik umum dan efektivitas dari masing-masing urutan ini. Pertimbangkan masalah penghitungan integral tertentu

$$

$$A = \ int_0 ^ 1 f (x) \ textrm {d} x$$

Kami dapat memperkirakannya sebagai:

$$

$$A \ simeq A_n = \ frac {1} {n} \ sum_ {i = 1} ^ {n} f (x_i), \ quad x_i \ dalam [0,1]$$

• Jika $$$\ {x_i \}$ sama $$$i / n$ , ini adalah rumus segi empat ;
• Jika $$$\ {x_i \}$ dipilih secara acak, maka ini adalah metode Monte Carlo ; tapi
• Jika $$$\ {x_i \}$ adalah elemen dari urutan dengan divergensi rendah, maka ini adalah metode quasi-Monte Carlo .

Grafik di bawah ini menunjukkan kurva kesalahan khas. $$$s_n = | A-A_n |$ untuk memperkirakan integral tertentu yang terkait dengan fungsi ini, $$$f (x) = \ textrm {exp} (\ frac {-x ^ 2} {2}), \; x \ dalam [0,1]$ untuk: (i) titik kuasi-acak dari rekursi aditif, di mana $$$\ alpha = 1 / \ phi$ , (biru); (ii) titik acak semu dari urutan van der Corput, (oranye); (iii) titik yang dipilih secara acak, (hijau); (iv) Sable sequence (red).

Ini menunjukkan bahwa untuk $$$n = 10 ^ 6$ solusi poin dengan pengambilan sampel acak mengarah ke kesalahan $$$\ simeq 10 ^ {- 4}$ , urutan van der Corput menyebabkan kesalahan $$$\ simeq 10 ^ {- 6}$ sedangkan $$$R (\ phi)$ - urutannya menyebabkan kesalahan $$$\ simeq 10 ^ {- 7}$ itu di $$$\ sim$ 10 kali lebih baik daripada kesalahan van der Corput dan $$$\ sim$ 1000 kali lebih baik daripada pengambilan sampel acak (seragam).


Gambar 2. Perbandingan integrasi numerik satu dimensi menggunakan berbagai metode Monte Carlo kuasi-acak. Semakin rendah nilainya, semakin baik. Baru $$$R_2$ - urutan (biru) dan urutan Sable (merah) jelas yang terbaik.

Berikut ini layak disebutkan di sini:

• ini sesuai dengan pengetahuan bahwa kesalahan untuk pengambilan sampel acak yang seragam berkurang secara asimptotik $$$1 / \ sqrt {n}$ , dan kesalahan untuk kedua urutan kuasi-acak cenderung $$$1 / n$ .
• Hasil untuk $$$R_1 (\ phi)$ Urutan berikutnya (biru) dan Sable (merah) adalah yang terbaik.
• Grafik menunjukkan bahwa urutan van der Corpute memberikan hasil yang baik, tetapi sangat konsisten untuk tugas integrasi!
• Dapat dilihat di sini bahwa untuk semua nilai $$$n$ urutan $$$R_1 (\ phi)$ menghasilkan hasil yang lebih baik daripada urutan van der Corput.

Urutan baru $$$R_1$ , yang merupakan urutan Kronecker menggunakan rasio emas, adalah salah satu pilihan terbaik untuk metode integrasi Monte Carlo quasirandom satu dimensi (Quasirandom Monte Carlo, QMC).

Perlu dicatat juga bahwa meskipun $$$\ alpha = \ phi$ secara teoritis memberikan opsi yang terbukti optimal, $$$\ sqrt {2}$ sangat dekat dengan optimal, dan hampir semua nilai irasional lainnya $$$\ alpha$ memberikan kurva kesalahan yang unggul untuk integrasi satu dimensi. Itu sebabnya sangat sering digunakan $$$\ alpha = \ sqrt {p}$ untuk nomor prima apa pun. Selain itu, dari sudut pandang perhitungan, nilai acak yang dipilih dalam interval $$$\ alpha \ dalam [0,1]$ itu hampir pasti akan (dalam batas-batas akurasi mesin) bilangan irasional, dan karenanya merupakan pilihan yang baik untuk urutan dengan divergensi rendah. Untuk keterbacaan visual, gambar di atas tidak menunjukkan hasil dari urutan Niederreiter, karena mereka praktis tidak bisa dibedakan dari hasil urutan Sobol dan $$$R$ . Urutan Niederreiter dan Sable (bersama dengan pemilihan parameter yang dioptimalkan) yang digunakan dalam posting ini dihitung dalam Mathematica menggunakan apa yang disebut "generator tertutup dan sepenuhnya dioptimalkan dari perpustakaan Intel MKL" dalam dokumentasi.

Urutan semu acak dalam dua dimensi

Sebagian besar metode modern untuk membangun varian rendah dalam dimensi yang lebih tinggi hanya menggabungkan (komponen demi komponen) $$$d$ urutan satu dimensi. Untuk singkatnya, dalam posting kami terutama akan mempertimbangkan urutan Holton [ Holton, 1960 ], urutan Sable, dan $$$d$ Urutan Kronecker -dimensi.

Urutan Holton dibangun menggunakan sederhana $$$d$ berbagai deretan van der Corpute satu-dimensi, yang dasarnya sederhana untuk semua yang lain. Artinya, mereka adalah angka coprime berpasangan. Tanpa ragu, pilihan yang paling umum karena kesederhanaan dan logikanya yang jelas adalah pilihan yang pertama $$$d$ bilangan prima. Distribusi 625 poin pertama yang didefinisikan oleh urutan (2,3) Holton ditunjukkan pada Gambar 1. Meskipun banyak sekuens Holton dua dimensi adalah sumber sekuens yang sangat baik dengan divergensi rendah, telah diketahui bahwa banyak dari mereka sangat bermasalah dan tidak menunjukkan divergensi rendah. Sebagai contoh, Gambar 3 menunjukkan bahwa Holton's (11,13) -setelah menghasilkan garis yang sangat nyata. Upaya besar dilakukan untuk mengembangkan metode untuk memilih model dan pasangan bermasalah. $$$(p_1, p_2)$ . Dalam dimensi yang lebih tinggi, masalahnya menjadi lebih rumit.

Ketika menggeneralisasi ke dimensi yang lebih tinggi, metode rekursif Kronecker mengalami kesulitan yang bahkan lebih besar. Meskipun menggunakan $$$\ alpha = \ sqrt {p}$ sekuens satu dimensi yang sangat baik diciptakan, sangat sulit untuk bahkan menemukan pasangan bilangan prima yang dapat digunakan sebagai dasar untuk kasus dua dimensi yang tidak bermasalah! Disarankan untuk menggunakan nomor irasional terkenal lainnya sebagai solusi, misalnya $$$\ phi, \ pi, e, ...$ . Mereka memberikan hasil yang cukup dapat diterima, tetapi umumnya tidak digunakan, karena mereka biasanya tidak sebagus urutan Holton yang dipilih dengan benar. Upaya besar sedang dilakukan untuk memecahkan masalah degenerasi ini.

Solusi yang diusulkan menggunakan skipping / burning, leaping / thinning. Dan untuk pengkodean (pengacakan) dari urutan terakhir, teknik lain digunakan, sering digunakan untuk mengatasi masalah ini. Perebutan tidak dapat digunakan untuk membuat urutan terbuka (tak terbatas) dengan divergensi rendah.


Gambar 3. Urutan (11,13) -Holton jelas bukan urutan divergensi rendah (kiri). Juga tidak aditif rekursif (11,13) -setelah (di tengah). Beberapa urutan rekursif dua dimensi aditif yang menggunakan bilangan irasional terkenal cukup baik (kanan).

Demikian pula, meskipun secara umum hasil yang lebih baik dari urutan Sable, kompleksitasnya dan, yang lebih penting, kebutuhan untuk pemilihan hyperparameter yang sangat hati-hati membuatnya tidak begitu ramah.

Jadi sekali lagi, di $$$d$ pengukuran:

• urutan Kronecker khas membutuhkan pilihan $$$d$ bilangan irasional yang bebas linear;
• Urutan Holton membutuhkan $$$d$ bilangan bulat berpasangan satu sama lain; tapi
• Urutan Sable membutuhkan pilihan $$$d$ nomor panduan.

Urutan baru $$$R_d$ - satu-satunya $$$d$ -dimensi kuasi-acak dimensional dengan divergensi rendah, tidak memerlukan pilihan parameter dasar.

Generalisasi Rasio Emas

tl; dr Di bagian ini saya akan berbicara tentang cara membangun kelas baru $$$d$ -dimensi terbuka (tak terbatas) berdimensi rendah, tidak memerlukan pilihan parameter dasar, memiliki sifat unggul divergensi rendah.

Ada banyak cara untuk menggeneralisasi urutan Fibonacci dan / atau rasio emas. Metode yang diusulkan di bawah ini untuk menggeneralisasi rasio emas bukanlah hal baru [ Krchadinac, 2005 ]. Selain itu, polinomial karakteristik dikaitkan dengan banyak area aljabar, termasuk bilangan Perron dan bilangan Piso-Vijayaraghavan . Namun, hubungan eksplisit antara bentuk umum ini dan konstruksi urutan dimensi tinggi dengan divergensi rendah adalah baru di dalamnya. Kami mendefinisikan pandangan umum rasio emas $$$\ phi_d$ sebagai akar positif yang unik $$$x ^ {d + 1} = x + 1$ . Itu adalah,

Untuk $$$d = 1$ , $$$\ phi_1 = 1.61803398874989484820458683436563 ...$ , yang merupakan rasio emas kanonik.

Untuk $$$d = 2$ , $$$\ phi_2 = 1.32471795724474602596090885447809 ...$ . Nilai ini sering disebut konstanta plastik dan memiliki sifat yang indah (lihat juga di sini ). Diasumsikan bahwa nilai ini kemungkinan besar akan optimal untuk masalah dua dimensi yang sesuai [ Hensley, 2002 ].

Untuk $$$d = 3$ , $$$\ phi_3 = 1.220744084605759475361685349108831 ...$

Untuk $$$d> 3$ , meskipun akar persamaan ini tidak memiliki bentuk aljabar tertutup, kita dapat dengan mudah memperoleh perkiraan numerik baik dengan metode standar, misalnya, metode Newton, atau dengan mencatatnya untuk urutan berikut $$$R_d (\ phi_d)$ :

$$

$$t_0 = t_1 = ... = t_ {d} = 1;$$

$$

$$t_ {n + d + 1} \; = \; t_ {n + 1} + t_n, \ quad \ textrm {for} \; n = 1,2,3, ..$$

Urutan konstanta khusus ini $$$\ phi_d$ dinamai pada tahun 1928 oleh arsitek dan biksu Hans van de Laan sebagai " angka harmonik ". Makna khusus ini dapat diungkapkan dengan sangat elegan sebagai berikut:

$$

$$\ phi_1 = \ sqrt {1+ \ sqrt {1+ \ sqrt {1+ \ sqrt {1+ \ sqrt {1 + ...}}}}}$$

$$

$$\ phi_2 = \ sqrt [3] {1+ \ sqrt [3] {1+ \ sqrt [3] {1+ \ sqrt [3] {1+ \ sqrt [3] {1 + ...}}}}}$$

$$

$$\ phi_3 = \ sqrt [4] {1+ \ sqrt [4] {1+ \ sqrt [4] {1+ \ sqrt [4] {1+ \ sqrt [4] {1 + ...}}}}}$$

Kami juga memiliki properti yang sangat elegan berikut:

$$

$$\ phi_d = \ lim_ {n \ to \ infty} \; \; \ frac {t_ {n + 1}} {t_n}$$

Urutan ini, kadang-kadang disebut urutan Fibonacci umum atau ditangguhkan, telah dipelajari cukup dalam [ As, 2004 , Wilson, 1993 ], dan urutan untuk $$$d = 2$ sering disebut urutan Padovan [ Stuart, 1996 , OEIS A000931 ], dan urutan $$$d = 3$ tercantum dalam [ OEIS A079398 ]. Seperti yang dinyatakan di atas, tugas utama dari posting ini adalah untuk menggambarkan hubungan eksplisit antara urutan umum dan konstruksi ini $$$d$ Urutan -dimensi dengan divergensi rendah.

Hasil utama: berikut nonparametrik $$$d$ -Dimensi urutan terbuka (tak terbatas) $$$R_d (\ phi_d)$ memiliki karakteristik perbedaan rendah yang sangat baik dibandingkan dengan metode lain yang ada.

$$

$$\ mathbf {t} _n = \ {n \ pmb {\ alpha} \}, \ quad n = 1,2,3, ...$$

$$

$$\ textrm {where} \ quad \ pmb {\ alpha} = (\ frac {1} {\ phi_d}, \ frac {1} {\ phi_d ^ 2}, \ frac {1} {\ phi_d ^ 3}, ... \ frac {1} {\ phi_d ^ d})$$

$$

$$\ textrm {and} \; \ phi_d \ \ textrm {adalah root positif unik} x ^ {d + 1} = x + 1$$

Untuk dua dimensi, urutan umum untuk $$$n = 150$ ditunjukkan pada gambar 1. Poin-poinnya jelas terdistribusi jauh lebih merata $$$R_2$ -setelah dari pada (2, 3) -Holton, Urutan Kronecker berdasarkan $$$(\ sqrt {3}, \ sqrt {7})$ , Urutan Niederreiter dan Sable. (Karena kompleksitas urutan Niederreiter dan Sable, mereka dihitung dalam Mathematica menggunakan kode eksklusif yang disediakan oleh Intel.) Jenis urutan di mana vektor dasar $$$\ pmb {\ alpha}$ adalah fungsi dari nilai material tunggal, sering disebut urutan Korobov [Korobov, 1959]

Lihat lagi Gambar 1 untuk membandingkan berbagai urutan kuasi-acak dua dimensi dan divergensi rendah.

Kode dan Demo

Dalam satu dimensi, pseudo-code untuk $$$n$ anggota ( $$$n$ = 1,2,3, ....) didefinisikan sebagai

 g = 1.6180339887498948482 a1 = 1.0/g x[n] = (0.5+a1*n) %1 

Dalam dua dimensi, pseudo-code untuk koordinat $$$x$ dan $$$y$$$$n$ anggota ( $$$n$ = 1,2,3, ....) Didefinisikan sebagai

 g = 1.32471795724474602596 a1 = 1.0/g a2 = 1.0/(g*g) x[n] = (0.5+a1*n) %1 y[n] = (0.5+a2*n) %1 

Kodesemu dalam tiga dimensi untuk koordinat $$$x$ , $$$y$ dan $$$z$$$$n$ anggota ( $$$n$ = 1,2,3, ....) didefinisikan sebagai

 g = 1.22074408460575947536 a1 = 1.0/g a2 = 1.0/(g*g) a3 = 1.0/(g*g*g) x[n] = (0.5+a1*n) %1 y[n] = (0.5+a2*n) %1 z[n] = (0.5+a3*n) %1 

Templat kode python. (perhatikan bahwa array dan loop Python mulai dari awal!)

 import numpy as np # Using the above nested radical formula for g=phi_d # or you could just hard-code it. # phi(1) = 1.61803398874989484820458683436563 # phi(2) = 1.32471795724474602596090885447809 def phi(d): x=2.0000 for i in range(10): x = pow(1+x,1/(d+1)) return x 

 # Number of dimensions. d=2 # number of required points n=50 g = phi(d) alpha = np.zeros(d) for j in range(d): alpha[j] = pow(1/g,j+1) %1 z = np.zeros((n, d)) # This number can be any real number. # Common default setting is typically seed=0 # But seed = 0.5 is generally better. for i in range(n): z[i] = (seed + alpha*(i+1)) %1 print(z) 

Saya menulis kode sedemikian rupa sehingga sesuai dengan notasi matematika yang digunakan dalam posting ini. Namun, untuk alasan konvensi pemrograman dan / atau efisiensi, beberapa modifikasi perlu disebutkan. Pertama, sejak itu $$$R_2$ adalah urutan rekursif aditif, formulasi alternatif $$$z$ yang tidak memerlukan perkalian floating point dan mempertahankan akurasi tinggi untuk sangat besar $$$n$ memiliki bentuk

 z[i+1] = (z[i]+alpha) %1 

Kedua, dalam bahasa yang dapat membuat vektor, kode fungsi fraksional dapat di-vectorisasi sebagai berikut:

 for i in range(n): z[i] = seed + alpha*(i+1) z = z %1 

Akhirnya, kita bisa mengganti penambahan angka floating point dan integer ini dengan mengalikan semua konstanta dengan $$$2 ^ {32}$ , dan kemudian mengubah fungsi frac (.) sesuai. Berikut adalah demo kode sumber yang dibuat oleh orang lain berdasarkan urutan ini:

• beta.observablehq.com/@jrus/plastic- berikutnyaence , dikembangkan oleh Jake Rus :
• www.shadertoy.com/view/4dtBWH , developer @ Stirners Host (XGKICK):

Jarak pengepakan minimum

Baru $$$R_2$ -setelah itu adalah satu-satunya kuasi dua dimensi - urutan acak dengan divergensi rendah di mana jarak pengepakan minimum dikurangi hanya menjadi $$$1 / \ sqrt {n}$ .

Meskipun analisis teknis standar perhitungan perbedaan adalah untuk mengevaluasi $$$d ^ *$ - perbedaan, pertama-tama kita akan menyebutkan beberapa cara geometris lainnya (dan mungkin jauh lebih intuitif!) untuk menunjukkan seberapa banyak urutan baru lebih disukai daripada metode standar lainnya. Jika kita menyatakan jarak antar titik $$$i$ dan $$$j$ untuk $$$d_ {ij}$ , dan $$$d_0 = \ textrm {inf} \; d_ {ij}$ maka grafik di bawah ini menunjukkan bagaimana itu bervariasi $$$d_0 (n)$ untuk $$$R$ -followingences, (2,3) - Holton, Sable, urutan Niederreiter dan urutan acak. Ini bisa dilihat pada Gambar 6.

Seperti pada gambar sebelumnya, nilai jarak minimum dinormalisasi dengan koefisien $$$1 / \ sqrt {n}$ . Anda mungkin memperhatikannya setelah itu $$$n = 300$ poin dalam urutan acak (hijau) hampir pasti muncul dua poin yang sangat dekat satu sama lain. Terlihat juga bahwa meskipun -sekitar Holton (2,3) jauh lebih baik daripada pengambilan sampel secara acak, sayangnya, asimtotik menurun menjadi nol. Untuk urutan Sable, alasan normalisasi berkurang menjadi nol $$$d_0$ terletak pada fakta bahwa Sable sendiri menunjukkan bahwa urutan Sable jatuh dengan cepat $$$/ n$ - yang bagus, tapi jelas jauh lebih buruk daripada $$$R_2$ yang berkurang hanya sebesar $$$1 / \ sqrt {n}$ .

Untuk urutan $$$R (\ phi_2)$ (biru) jarak minimum antara dua titik secara konstan jatuh ke dalam interval dari $$$0,549 / \ sqrt {n}$ sebelumnya $$$0,868 / \ sqrt {n}$ . Perhatikan bahwa diameter optimal 0,868 sesuai dengan faktor pengemasan 59,2%. Bandingkan ini dengan paket lingkaran lainnya .

Perhatikan juga bahwa pengambilan sampel disk Bridson Poisson , yang tidak dapat diperluas $$$n$ dan biasanya direkomendasikan secara default, itu masih menciptakan faktor pengemasan 49,4%. Perlu mempertimbangkan konsep itu $$$d_0$ mengikat urutan $$$\ phi_d$ perbedaan rendah dengan angka / vektor yang kurang tepat di $$$d$ pengukuran [ Hensley, 2001 ]. Meskipun kita tahu sedikit tentang angka-angka buruk yang dapat diperkirakan dalam dua dimensi, konstruksi $$$\ phi_d$ dapat memberi kami tampilan baru pada angka yang kurang dapat diperkirakan dalam dimensi yang lebih tinggi.


Gambar 4. Jarak berpasangan minimum untuk berbagai urutan dengan divergensi rendah. Catat itu $$$R_2$ - urutan (biru) selalu merupakan opsi terbaik; selain itu, ini adalah satu-satunya urutan di mana jarak yang dinormalisasi cenderung tidak nol pada $$$n \ rightarrow \ infty$ . Urutan Holton (oranye) menempati urutan kedua, dan urutan Sable (hijau) dan Niederreiter (merah) tidak begitu baik, tetapi masih jauh lebih baik daripada urutan acak (ungu). Semakin besar, semakin baik, karena ini sesuai dengan jarak pengemasan yang lebih panjang.

Diagram Voronoi

Cara lain untuk memvisualisasikan distribusi titik yang seragam adalah dengan membuat diagram Voronoi dari yang pertama $$$n$ titik-titik urutan dua dimensi dengan pewarnaan berikutnya masing-masing daerah tergantung pada daerahnya . Gambar di bawah ini menunjukkan bagan warna Voronoi untuk (i) $$$R_2$ - selanjutnya; (ii) (2,3) urutan Holton, (iii) rekursi utama; dan (iv) pengambilan sampel acak sederhana. Untuk semua angka digunakan skala warna yang sama. Di sini lagi, jelas sekali $$$R_2$ Urutan ini memberikan distribusi yang jauh lebih seragam daripada urutan Holton atau pengambilan sampel acak sederhana. Gambarnya sama seperti di atas, hanya diwarnai sesuai dengan jumlah simpul di setiap sel Voronoi. Tidak hanya jelas di sini $$$R$ - urutan memberikan distribusi yang lebih seragam daripada Holton atau pengambilan sampel acak sederhana, tetapi fakta bahwa nilai-nilai utama lebih terlihat $$$n$ hanya terdiri dari segi enam! Jika kita mempertimbangkan urutan Fibonacci umum, maka $$$A_1 = A_2 = A_3 = 1; \ quad A_ {n + 3} = A_ {n + 1} + A {n}$ . Yaitu $$$A_n$ :

$$$$ menampilkan $$ \ begin {array} {r} 1 & 1 & 1 & 2 & 2 & 3 & 4 & 5 & 7 \\ 9 & \ textbf {12} & 16 & 21 & 28 & 37 & \ textbf {49} & 65 & 86 \\ 114 & \ textbf {151 } & 200 & 265 & 351 & 465 & \ textbf {616} & 816 & 1081 \\ 1432 & \ textbf {1897} & 2513 & 3329 & 4410 & 5842 & \ textbf {7739} & 10252 & 13581 \\ 17991 & \ textbf {23833} & 31572 & 41824 & 55405 & 7 {97229} & 128801 & 170625 \\ 226030 & \ textbf {299426} & 396655 & 525456 & 69.081 & 922111 & \ textbf {1221537} & 1618192 & 2143648 \\ \ end {array} $$ display $$ $$

Semua nilai di mana $$$n = A_ {9k-2}$ atau $$$n = A_ {9k + 2}$ hanya terdiri dari segi enam.


Gambar 4. Visualisasi bentuk diagram Voronoi berdasarkan luas masing-masing poligon Voronoi untuk (i) $$$R_2$ - selanjutnya; (ii) (2,3) - selanjutnya berdasarkan bilangan prima; (iii) (2,3) setelah Holton, (iv) Niederraiter; (v) Sable; dan (iv) pengambilan sampel acak sederhana. Warna menunjukkan jumlah sisi setiap poligon Voronoi. Saya ulangi: sudah jelas itu $$$R (\ phi)$ -setelah memberikan distribusi yang jauh lebih seragam daripada urutan lainnya dengan divergensi rendah.

Pada nilai-nilai tertentu $$$n$ Kotak Voronoi untuk $$$R_2$ -setelah hanya terdiri dari segi enam.

Gambar 5. Visualisasi bentuk diagram Voronoi berdasarkan jumlah sisi setiap poligon Voronoi untuk (i) $$$R_2$ - selanjutnya; (ii) (2,3) - selanjutnya berdasarkan bilangan prima; (iii) (2,3) setelah Holton, (iv) Niederraiter; (v) Sable; dan (iv) pengambilan sampel acak sederhana. Warna menunjukkan jumlah sisi setiap poligon Voronoi. Saya ulangi: sudah jelas itu $$$R (\ phi)$ -setelah memberikan distribusi yang jauh lebih seragam daripada urutan lainnya dengan divergensi rendah.

Ubin semi-acak Delaunay untuk pesawat

$$$R$ -afterence adalah satu-satunya urutan kuasi-acak dengan divergensi rendah yang dapat digunakan untuk membuat $$$d$ - Dimensi periodik semi-dimensional menggunakan Delaunay mesh-nya.

Triangulasi Delaunay, yang mirip dengan Count Voronoi, memberikan kesempatan untuk melihat distribusi ini secara berbeda. Namun, yang lebih penting, triangulasi Delaunay menyediakan metode baru untuk membuat ubin kuasi periodik (ubin mosaik) dari sebuah pesawat. Triangulasi Delaunay $$$R_2$ -setelah memberikan pola yang jauh lebih seragam daripada urutan Holton atau pengambilan sampel acak. Secara khusus, jika triangulasi distribusi titik Delaunay dilakukan, di mana $$$n$ sama dengan salah satu urutan Fibonacci umum: $$$A_N = $ 1,1,1,2,3,4,5,7,9,12,16,21,28,37, ...$ , maka triangulasi Delaunay hanya terdiri dari tiga segitiga yang dipasangkan secara identik, yaitu, dari jajaran genjang (rhomboids)! (Kecuali untuk segitiga yang memiliki simpul umum dengan cembung cembung.) Selain itu,

Pada nilai $$$n = A_k$ Triangulasi Delaunay $$$R_2$ -bentuk berikutnya membentuk quasi periodic tilings, yang masing-masing hanya terdiri dari tiga segitiga dasar (merah, kuning, biru), yang selalu terhubung berpasangan dan membentuk ubin quasi periodic (ubin) pesawat dengan tiga jajaran genjang (rhomboids).

Gambar 6. Visualisasi triangulasi Delaunay untuk (i) $$$R (\ phi_2)$ - selanjutnya; (ii) (2,3) urutan Holton, (iii) rekursi utama; dan (iv) pengambilan sampel acak sederhana. Warna menunjukkan luas setiap segitiga. Keempat grafik menggunakan skala yang sama. Dan di sini sekali lagi jelas sekali $$$R (\ phi_2)$ -setelah memberikan distribusi yang jauh lebih seragam daripada urutan lainnya dengan divergensi rendah.
Catat itu $$$R_2$ berdasarkan $$$\ phi_2 = 1.32471795724474602596$ menjadi piso dengan jumlah terkecil, (a $$$\ phi = 1.61803 ...$ Merupakan jumlah terbesar dari piano). Koneksi ubin kuasi periodik dengan angka kuadratik dan kubik Piso bukanlah hal baru [ Elkharrat dan Masakova], tapi saya percaya bahwa untuk pertama kali ubin kuasi periodik dibuat berdasarkan $$$\ phi_2 = 1.324719 ...$ .

Animasi di bawah ini menunjukkan bagaimana jaring Delaunay untuk urutan $$$R_2$ berubah dengan penambahan poin secara bertahap. Perhatikan bahwa ketika jumlah poin sama dengan anggota dari deret Fibonacci umum, maka seluruh grid Delaunay hanya terdiri dari jajaran genjang merah, biru, dan kuning (rhomboids), yang disusun dalam bentuk kuasi periodik ganda.


Gambar 7

Meskipun susunan jajaran genjang merah menunjukkan keteraturan yang cukup besar, orang dapat dengan jelas melihat bahwa jajaran genjang biru dan kuning ditempatkan dalam bentuk kuasi periodik. Spektrum Fourier dari kisi ini dapat dilihat pada Gambar 11, yang mewakili spektrum titik klasik. (Perhatikan bahwa urutan rekursif berdasarkan bilangan prima juga tampaknya quasi periodic dalam arti bahwa itu adalah pola non-berulang yang dipesan. Namun, polanya dalam interval $$$n$ tidak begitu konstan, dan juga sangat tergantung pada pilihan parameter dasar. Oleh karena itu, kami akan memfokuskan minat kami pada tilt quasi periodik hanya dengan urutan $$$R_2$ .) Ini hanya terdiri dari tiga segitiga: merah, kuning, biru. Perhatikan bahwa dalam urutan ini $$$R (\ phi_2)$ semua jajaran genjang dari setiap warna memiliki ukuran dan bentuk yang sama. Rasio aspek dari segitiga individu ini sangat elegan. Yaitu

$$

$$\ textrm {Area (merah): Area (kuning): Area (biru)} = 1: \ phi_2: \ phi_2 ^ 2 $$$

Hal yang sama berlaku untuk frekuensi relatif segitiga:

$$

$$f (\ textrm {red}): f (\ textrm {yellow}): f (\ textrm {blue}) = 1: \ phi_2: 1$$

Dari sini dapat disimpulkan bahwa total area relatif yang dicakup oleh tiga segitiga dalam ruang adalah:

$$

$$f (\ textrm {red}): f (\ textrm {yellow}): f (\ textrm {blue}) = 1: \ phi_2 ^ 2: \ phi_2 ^ 2 $$$

Dapat juga diasumsikan bahwa kita dapat membuat ubin quasi periodic ini melalui substitusi berdasarkan urutan A. Yaitu

$$

$$A \ rightarrow B; \ quad B \ rightarrow C; \ quad C \ rightarrow BA$$

Untuk tiga dimensi, jika kita mempertimbangkan urutan Fibonacci umum, maka $$$B_1 = B_2 = B_3 = B_4 = 1; \ quad B_ {n + 4} = B_ {n + 1} + B {n}$ . Yaitu

$$

$$B_n = \ {1,1,1,1,2,2,2,4,4,4,5,7,8,9,12,15,17,21,27,32,38,48,59 , 70,86.107.129, ...$$

Pada nilai-nilai tertentu $$$n = B_k$ 3D Delaunay mesh terkait dengan urutan $$$R_3$ , mendefinisikan kisi kristal kuasi periodik.

Pengemasan yang tidak digunakan, bagian 2

Gambar di bawah ini menunjukkan yang pertama $$$n = 2500$ poin untuk setiap urutan dua dimensi dengan divergensi rendah. Selain itu, masing-masing sel 50 × 50 = 2500 berwarna hijau hanya jika mengandung tepat 1 titik. Artinya, semakin banyak kotak hijau, semakin seragam distribusi 2500 poin dalam 2500 sel. Persentase sel hijau untuk masing-masing angka adalah sebagai berikut: $$$R_2$ (75%), Holton (54%), Kronecker (48%), Niederreiter (54%), Sable (49%) dan acak (38%).

Gelombang suara

Hanya untuk bersenang-senang, atas permintaan pembaca News Hacker, saya memodelkan bagaimana semua distribusi titik kuasi-acak ini bisa terdengar ! Saya menggunakan fungsi Listplay dari Mathematica: " ListPlay [{a1, a2, ...}] membuat objek yang mereproduksi sebagai suara, yang amplitudonya diberikan sebagai urutan level." Karena itu, tanpa komentar, saya akan membiarkan Anda memutuskan sendiri mana yang paling Anda sukai di antara distribusi kuasi-acak satu-dimensi (mono) dan distribusi kuasi-acak dua-dimensi (stereo).

	Mono	Stereo
Acak	http://extremelearning.com.au/wp-content/uploads/2018/04/random_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/random_2D.mp3
Sable	http://extremelearning.com.au/wp-content/uploads/2018/04/Sobol_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Sobol_2D.mp3
Niederreiter	http://extremelearning.com.au/wp-content/uploads/2018/04/Nied_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Nied_2D.mp3
Holton	http://extremelearning.com.au/wp-content/uploads/2018/04/Halton_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Halton_2D.mp3
Kronecker	http://extremelearning.com.au/wp-content/uploads/2018/04/Kronecker_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/Kronecker_2D.mp3
R	http://extremelearning.com.au/wp-content/uploads/2018/04/R1_1D.mp3	http://extremelearning.com.au/wp-content/uploads/2018/04/R2_2D.mp3

Set Perbedaan Rendah Multiclass

Beberapa sekuens divergensi rendah menunjukkan apa yang disebut "divergensi rendah multi-kelas". Hingga saat ini, kami mengasumsikan bahwa ketika kami perlu mendistribusikannya serata mungkin $$$n$ poin, maka semua poin adalah sama dan tidak dapat dibedakan satu sama lain. Namun, dalam banyak situasi, ada berbagai jenis titik. Kami mempertimbangkan masalah distribusi seragam $$$n$ sehingga tidak hanya semua poin didistribusikan secara merata, tetapi juga poin dari kelas yang sama. Secara khusus, anggaplah ada $$$n_k$ ketik poin $$$k$ , (dimana $$$n_1 + n_2 + n_3 + ... + n_k = n$ ), maka distribusi multiset dengan distribusi rendah adalah distribusi di mana masing-masing $$$n_k$ poin didistribusikan secara merata. Dalam kasus kami, kami menemukan itu $$$R$ -Rangkaian dan urutan Holton mudah untuk beradaptasi dengan urutan multiset dengan divergensi rendah, cukup dengan menempatkan titik bergantian dari setiap jenis.

Gambar di bawah ini menunjukkan bagaimana mereka didistribusikan $$$n = 150$ titik, sedangkan 75 berwarna biru, 40 pedas, 25 berwarna hijau, dan 10 berwarna merah. Untuk urutan rekursif aditif, ini dipecahkan secara sepele: 75 anggota pertama hanya sesuai dengan biru, 40 berikutnya ke oranye, 25 berikutnya ke hijau, dan 10 terakhir ke titik merah. Teknik ini hampir bekerja untuk urutan Holton dan Kronecker, tetapi berkinerja sangat buruk di urutan Niederreiter dan Sable. Selain itu, tidak ada teknik yang dikenal untuk generasi berkelanjutan dari distribusi titik multi-skala di urutan Niederreiter dan Sable. Ini menunjukkan bahwa distribusi titik multiclass , misalnya, seperti mata ayam , sekarang dapat dijelaskan dan dibangun langsung menggunakan urutan dengan divergensi rendah.

Urutan $$$R_2$ Adalah urutan kuasi-acak divergensi rendah yang menyediakan konstruksi mudah dari divergensi rendah multi-kelas.

Gambar 9. Urutan multiskala dengan divergensi rendah. Secara berurutan $$$R$ tidak hanya semua titik didistribusikan secara merata, tetapi juga titik masing-masing warna.

Poin acak semu di bola

Dalam bidang grafis dan fisika komputer, sering kali perlu untuk mendistribusikan titik pada permukaan bola tiga dimensi secara merata. Ketika menggunakan urutan kuasi-acak terbuka (tidak terbatas), masalah ini berkurang hanya untuk menempatkan titik-titik kuasi-acak yang terdistribusi secara merata dalam satuan persegi pada permukaan bola menggunakan proyeksi Lambert yang sama. Lambert mengubah proyeksi standar menempatkan titik $$$(u, v) \ dalam U [0,1] \ hingga (x, y, z) \ dalam S ^ 2$ memiliki bentuk:

$$

$$(x, y, z) = (\ cos \ lambda \ cos \ phi, \ cos \ lambda \ sin \ phi, \ sin \ lambda)$$

$$

$$\ textrm {where} \ quad \ cos (\ lambda - \ pi / 2) = (2u-1); \ quad \ phi = 2 \ pi v$$

Sejak ini $$$\ phi_2$ - Urutan benar-benar terbuka, memungkinkan Anda untuk mengambil urutan titik tak terbatas ke permukaan bola, satu titik pada suatu waktu. Ini kontras dengan metode lain, seperti kisi - kisi spiral Fibonacci , yang membutuhkan mengetahui jumlah poin di muka. Pada inspeksi visual, kita dapat melihatnya kembali dengan jelas $$$n = 1200$ baru $$$R (\ phi_2)$ - Urutan terdistribusi lebih baik daripada overlay Holton atau Kronecker, yang, pada gilirannya, jauh lebih seragam daripada pengambilan sampel acak.


Gambar 10

Grafik komputer dithering

Kebanyakan teknik dithering modern (misalnya, dithering Floyd-Steinberg) didasarkan pada distribusi kesalahan, yang tidak terlalu cocok untuk pemrosesan paralel dan / atau optimalisasi langsung dalam GPU. Dalam kasus seperti itu, titik dithering dengan topeng gentar statis (mis., Sepenuhnya tergantung pada gambar target) menunjukkan karakteristik kinerja yang sangat baik. Mungkin topeng dithering yang paling terkenal dan banyak digunakan didasarkan pada matriks Bayer , tetapi yang lebih baru mencoba mensimulasikan karakteristik noise biru lebih dekat. Kesulitan non-sepele menciptakan topeng gentar berdasarkan urutan divergensi rendah dan / atau noise biru adalah bahwa urutan divergensi rendah ini memproyeksikan integer $$$Z$ ke titik dua dimensi dalam interval $$$[0,1)^2$ . Tetapi untuk topeng dithering, diperlukan fungsi yang memproyeksikan koordinat bilangan dua dimensi dari topeng raster menjadi nilai kecerahan / ambang batas nyata dalam interval. $$$[0,1)$ . Saya menyarankan pendekatan berikut berdasarkan $$$R$- selanjutnya. Untuk setiap piksel (x, y) dalam topeng, kami menetapkan nilai kecerahannya$$$I(x,y)$ dimana:

$$

$$I(x,y) = \alpha_1 x + \alpha_2 y \; ( \textrm{mod} 1);$$

$$

$$\textrm{} \quad \pmb{\alpha} =(\alpha_1,\alpha_2) = (\frac{1}{\phi_2}, \frac{1}{\phi_2^2})$$

$$

$$\textrm{} \; \phi_2\ \textrm{ - } x^3\;=x+1$$

Yaitu $$$x = 1.32471795724474602596…$ , yang artinya

$$

$$\alpha_1 = 0.75487766624669276; \alpha_2 = 0.569840290998$$

Selain itu, jika fungsi gelombang segitiga ditambahkan untuk menghilangkan diskontinuitas yang disebabkan oleh fungsi frac (.) Pada setiap batas integer:

$$

$$T(z) =\begin{cases} 2z, & \text{if } 0\leq z <1/2 \\ 2-2z, & \text{if} 1/2 \leq z < 1 \end{cases}$$

$$

$$I(x,y) = T \left[ \alpha_1 x + \alpha_2 y \; ( \textrm{mod} 1) \right];$$

kemudian mask dan diagram Fourier / frekuensi ditingkatkan lebih lanjut. Kami juga mencatat bahwa sejak itu

$$

$$\lim_{n \rightarrow \infty} \frac{A_n}{A_{n+1}} = 0.754878 ; \quad \lim_{n \rightarrow \infty} \frac{A_n}{A_{n+2}} = 0.56984$$

maka bentuk ungkapan di atas terkait dengan persamaan kongruen berikut

$$

$$A_n x + A_{n+1} y \; (\textrm{mod} A_{n+2}) \textrm{ for integers } \;\; x,y$$

Dithering R-mask menciptakan hasil yang bersaing dengan metode modern berdasarkan pada blue noise mask. Tapi tidak seperti topeng noise biru, mereka tidak perlu dihitung terlebih dahulu, karena mereka dapat dihitung secara real time.

Perlu dicatat bahwa struktur ini juga diusulkan oleh Mittring , tetapi ia menemukan koefisien secara empiris (dan tidak mereproduksi nilai akhir). Selain itu, ini membantu dalam memahami mengapa rumus empiris Jorge Jimenez digunakan untuk membuat "Call of Duty" (sering disebut "Interleaved Gradient Noise") bekerja dengan sangat baik .

$$

$$I(x,y) = (\textrm{FractionalPart}[52.9829189*\textrm{FractionalPart}[0.06711056*x + 0.00583715*y]]$$

Namun, ini membutuhkan 3 perkalian floating point dan dua% 1 operator, dan rumus sebelumnya menunjukkan bahwa kita bisa melakukan ini hanya dengan dua perkalian floating point dan satu operasi% 1. Tetapi yang lebih penting, posting ini memberikan pemahaman matematis yang lebih jelas tentang mengapa topeng gentar dalam bentuk ini sangat efektif, jika tidak optimal. Hasil matriks dithering ini ditunjukkan di bawah ini menggunakan gambar uji Lena 256 × 256 klasik serta pola tes catur sebagai contoh. Ini juga menunjukkan hasil menggunakan masker dithering standar Bayer, serta satu contoh dengan noise biru. Dua metode noise biru yang paling umum adalah pengambilan sampel Void-and-Cluster dan Poisson. Untuk singkatnya, saya hanya menunjukkan hasil dari metode Void dan cluster. [ Peters] Noise gradien yang disisipkan bekerja lebih baik daripada Bayer dan noise biru, tetapi tidak sebagus$$$R$dithering. Anda dapat melihat bahwa Bayer dithering menunjukkan disonansi putih yang terlihat jelas di area abu-abu terang. Dithering$$$R$- Urutan dan noise biru umumnya sebanding, meskipun perbedaan kecil dapat dibuat. Perlu dicatat beberapa aspek dari R-dithering:

• Dia bukan isotropik! Spektrum Fourier hanya menunjukkan titik-titik individual dan diskrit. Ini adalah fitur klasik dari tasi quasi periodik dan spektra difraksi kristal quasicry. Secara khusus, spektrum Fourier untuk$$$R$ -masus sesuai dengan fakta bahwa triangulasi Delaunay untuk sekuens R-kanonik terdiri dari ubin kuasi periodik dari tiga jajar genjang.
• R-dithering saat dikombinasikan dengan gelombang segitiga memberikan topeng yang sangat seragam!
• R- , .
• , , R- , .
• $$$(I(x,y)$ , .

Gambar 11. Dari kiri ke kanan: (i) Gambar asli (ii) R-sequence dikombinasikan dengan fungsi gelombang segitiga; (iii) urutan R terpisah; (iv) topeng dithering kebisingan biru, dan (v) Bayer standar. Masker dithering R-sequence cukup kompetitif terhadap topeng modern lainnya. Perhatikan bahwa R2 menunjukkan kualitas terbaik pada wajah dan pundak Lena. Selain itu, tidak seperti topeng noise biru, R-mask dithering sangat sederhana sehingga tidak memerlukan perhitungan awal.

Dimensi yang lebih tinggi

Mirip dengan bagian sebelumnya, tetapi untuk lima (5) pengukuran, grafik di bawah ini menunjukkan jarak minimum (global) antara dua titik untuk $$$R(\phi_5)$-afterences, (2,3,5,7,11) -Holton dan urutan acak. Kali ini, nilai normal jarak minimum dinormalisasi oleh faktor$$$1/ \sqrt[5]{n}$ . Dapat dilihat bahwa karena "kutukan dimensi", distribusi acak lebih baik daripada semua urutan dengan divergensi rendah - dengan pengecualian $$$R_5$- selanjutnya. Masuk$$$R(\phi_5)$ -setelah bahkan dengan $$$n \simeq 10^6$ poin, jarak minimum antara dua titik masih terus dekat $$$0.8/\sqrt{n}$ dan selalu lebih tinggi $$$0.631/\sqrt{n}$ .

Urutan $$$R_2$ - satu-satunya $$$d$ - Urutan dimensi dengan divergensi rendah, di mana jarak pengemasan mulai turun hanya dengan kecepatan $$$n^{-1/d}$ .

Gambar 12. Ini menunjukkan bahwa urutan R (biru) secara konsisten lebih baik daripada Holton (oranye); Sable (hijau); Niederreiter (merah); dan acak (ungu). Perlu diingat bahwa semakin besar semakin baik, karena ini sesuai dengan jarak pengepakan yang lebih lama.

Integrasi numerik

Grafik berikut menunjukkan kurva kesalahan khas. $$$s_n = |A-A_n|$ untuk memperkirakan integral tertentu yang terkait dengan fungsi Gaussian setengah lebar $$$\sigma = \sqrt{d}$ , $$$f(x) = \textrm{exp}(\frac{-x^2}{2d}), \; x \in [0,1]$ , sementara: (i) $$$R_{\phi}$(biru); (ii) Urutan Holton (oranye); (iii) acak (hijau); (iv) Sable (merah). Grafik menunjukkan bahwa untuk$$$n=10^6$sekarang ada lebih sedikit perbedaan antara pengambilan sampel acak dan urutan Holton. Namun, seperti yang ditunjukkan dalam kasus satu dimensi,$$$R$- Urutan dan Sable selalu lebih baik daripada urutan Holton. Ini juga memberi tahu kami bahwa urutan Sable sedikit lebih baik.$$$R$ - selanjutnya.


Gambar 13. Metode acak semu Monte Carlo untuk integrasi 8 dimensi. Semakin rendah nilainya, semakin baik. Urutan R-baru dan urutan Sable menunjukkan diri mereka jauh lebih baik daripada urutan Holton.