Saya telah melihat generator nomor pseudo-acak ini untuk digunakan dalam shader yang dirujuk di sana-sini di seluruh web :
float rand(vec2 co){
return fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * 43758.5453);
}
Ini berbagai disebut "kanonik", atau "satu baris yang saya temukan di web di suatu tempat".
Apa asal mula fungsi ini? Apakah nilai-nilai konstan sewenang-wenang seperti yang terlihat atau adakah seni dalam pemilihannya? Apakah ada diskusi tentang manfaat fungsi ini?
EDIT: Referensi terlama untuk fungsi ini yang saya temukan adalah arsip ini dari Feb '08 , halaman asli sekarang telah hilang dari web. Tapi tidak ada lagi diskusi tentang itu di sana daripada di tempat lain.
Jawaban:
Pertanyaan yang sangat menarik!
Saya mencoba mencari tahu sambil mengetik jawabannya :) Pertama, cara mudah untuk bermain dengannya: http://www.wolframalpha.com/input/?i=plot%28+mod%28+sin%28x*12.9898 +% 2B + y * 78.233% 29 + * + 43758.5453% 2C1% 29x% 3D0..2% 2C + y% 3D0..2% 29
Kemudian mari kita pikirkan tentang apa yang kita coba lakukan di sini: Untuk dua koordinat masukan x, y kita mengembalikan sebuah "bilangan acak". Sekarang ini bukan nomor acak. Itu sama setiap kali kita memasukkan x, y yang sama. Ini adalah fungsi hash!
Hal pertama yang dilakukan fungsi ini adalah beralih dari 2d ke 1d. Itu sendiri tidak menarik, tetapi nomornya dipilih sehingga tidak berulang secara khas. Juga kami memiliki tambahan floating point di sana. Akan ada beberapa bit lagi dari y atau x, tetapi angkanya mungkin saja dipilih dengan benar sehingga tercampur.
Kemudian kami mengambil contoh fungsi kotak hitam sin (). Ini akan sangat bergantung pada implementasinya!
Terakhir, ini memperkuat kesalahan dalam implementasi sin () dengan mengalikan dan mengambil pecahan.
Saya tidak berpikir ini adalah fungsi hash yang baik dalam kasus umum. Sin () adalah kotak hitam, di GPU, secara numerik. Seharusnya mungkin untuk membangun yang jauh lebih baik dengan mengambil hampir semua fungsi hash dan mengubahnya. Bagian yang sulit adalah mengubah operasi integer tipikal yang digunakan dalam cpu hashing menjadi operasi float (setengah atau 32bit) atau titik tetap, tetapi itu harus memungkinkan.
Sekali lagi, masalah sebenarnya dengan ini sebagai fungsi hash adalah bahwa sin () adalah kotak hitam.
sumber
Asalnya mungkin adalah makalah: "Saat menghasilkan bilangan acak, dengan bantuan y = [(a + x) sin (bx)] mod 1", WJJ Rey, Pertemuan Ahli Statistik Eropa ke-22 dan Konferensi Vilnius ke-7 tentang Teori Probabilitas dan Statistik Matematika, Agustus 1998
EDIT: Karena saya tidak dapat menemukan salinan makalah ini dan referensi "TestU01" mungkin tidak jelas, berikut skema yang dijelaskan di TestU01 dalam pseudo-C:
#define A1 ??? #define A2 ??? #define B1 pi*(sqrt(5.0)-1)/2 #define B2 ??? uint32_t n; // position in the stream double next() { double t = fract(A1 * sin(B1*n)); double u = fract((A2+t) * sin(B2*t)); n++; return u; }
dimana satu-satunya nilai konstanta yang direkomendasikan adalah B1.
Perhatikan bahwa ini untuk aliran. Mengonversi ke 1D hash 'n' menjadi grid integer. Jadi tebakan saya adalah seseorang melihat ini dan mengubah 't' menjadi fungsi sederhana f (x, y). Menggunakan konstanta asli di atas yang akan menghasilkan:
float hash(vec2 co){ float t = 12.9898*co.x + 78.233*co.y; return fract((A2+t) * sin(t)); // any B2 is folded into 't' computation }
sumber
fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * (co.xy + vec2(43758.5453, SOMENUMBER))
agar sesuai dengan fungsi yang dibahas makalah ini.a
danb
) digunakan berulang-ulang tetap ada, tetapi mungkin telah digunakan dalam makalah yang Anda kutip.nilai konstanta berubah-ubah, terutama yang sangat besar, dan beberapa desimal jauh dari bilangan prima.
modulus di atas 1 dari sinus amplitudo hi dikalikan dengan 4000 adalah fungsi periodik. ini seperti tirai jendela atau logam bergelombang yang dibuat sangat kecil karena dikalikan dengan 4000, dan diputar pada suatu sudut oleh perkalian titik.
karena fungsinya adalah 2-D, hasil perkalian titik memiliki efek memutar fungsi periodik pada sumbu X dan Y secara relatif miring. Dengan rasio sekitar 13/79. Ini tidak efisien, Anda benar-benar dapat mencapai hal yang sama dengan melakukan sinus (13x + 79y) ini juga akan mencapai hal yang sama yang saya pikir dengan lebih sedikit matematika ..
Jika Anda menemukan periode fungsi di X dan Y, Anda dapat mengambil sampelnya sehingga akan terlihat seperti gelombang sinus sederhana lagi.
Berikut adalah gambar grafik yang diperbesar
Saya tidak tahu asalnya tetapi ini mirip dengan banyak lainnya, jika Anda menggunakannya dalam grafik secara berkala, itu akan cenderung menghasilkan pola moire dan Anda bisa melihatnya akhirnya berputar lagi.
sumber
(13x + 79y)
karenadot(XY, AB)
akan melakukan persis seperti yang Anda gambarkan, sebagai produk titik, yangx,y dot 13, 79 = (13x + 79y)
Mungkin itu beberapa pemetaan kacau yang tidak berulang, kemudian bisa menjelaskan banyak hal, tetapi juga bisa hanya beberapa manipulasi sewenang-wenang dengan jumlah besar.
EDIT: Pada dasarnya, fungsi frakt (sin (x) * 43758.5453) adalah fungsi seperti hash sederhana, sin (x) memberikan interpolasi sin halus antara -1 hingga 1, jadi sin (x) * 43758.5453 akan menjadi interpolasi dari - 43758.5453 hingga 43758.5453. Ini adalah rentang yang cukup besar, sehingga langkah kecil dalam x akan memberikan hasil langkah yang besar dan variasi yang sangat besar pada bagian pecahan. "Fraktur" diperlukan untuk mendapatkan nilai dalam kisaran -0,99 ... hingga 0,999 .... Sekarang, ketika kita memiliki sesuatu seperti fungsi hash, kita harus membuat fungsi untuk produksi hash dari vektor. Cara termudah adalah memanggil "hash" secara terpisah untuk x sembarang komponen y dari vektor masukan. Tetapi kemudian, kita akan memiliki beberapa nilai simetris. Jadi, kita harus mendapatkan beberapa nilai dari vektor tersebut, pendekatannya adalah mencari beberapa vektor acak dan menemukan perkalian "titik" ke vektor itu, ini dia: fract (sin (dot (co.xy, vec2 (12.9898,78.233))) * 43758.5453); Juga, menurut vektor yang dipilih, panjangnya harus cukup panjang untuk memiliki beberapa peroid dari fungsi "sin" setelah perkalian "titik" akan dihitung.
sumber