Sunting: Jadi pada dasarnya yang ingin saya tulis adalah hash 1 bit double
.
Saya ingin memetakan double
ke true
atau false
dengan peluang 50/50. Untuk itu saya menulis kode yang mengambil beberapa angka acak (seperti contoh, saya ingin menggunakan ini pada data dengan keteraturan dan masih mendapatkan hasil 50/50) , memeriksa bit terakhir mereka dan kenaikan y
jika itu adalah 1, atau n
jika itu adalah 0.
Namun, kode ini secara konstan menghasilkan 25% y
dan 75% n
. Mengapa bukan 50/50? Dan mengapa distribusi yang aneh, tetapi langsung (1/3)?
public class DoubleToBoolean {
@Test
public void test() {
int y = 0;
int n = 0;
Random r = new Random();
for (int i = 0; i < 1000000; i++) {
double randomValue = r.nextDouble();
long lastBit = Double.doubleToLongBits(randomValue) & 1;
if (lastBit == 1) {
y++;
} else {
n++;
}
}
System.out.println(y + " " + n);
}
}
Contoh output:
250167 749833
java
random
double
bit-manipulation
probability
gvlasov
sumber
sumber
doubleValue % 1 > 0.5
, tapi itu akan terlalu kasar karena dapat memperkenalkan keteraturan yang terlihat dalam beberapa kasus (semua nilai berada dalam kisaran panjang 1). Jika itu terlalu berbutir kasar, maka haruskah kita mencoba rentang yang lebih kecil, sepertidoubleValue % 1e-10 > 0.5e-10
? Baiklah. Dan mengambil bit terakhir sebagai hash daridouble
apa yang terjadi ketika Anda mengikuti pendekatan ini sampai akhir, dengan modulo sesedikit mungkin.(lastbit & 3) == 0
akan bekerja meskipun aneh.Jawaban:
Karena nextDouble berfungsi seperti ini: ( sumber )
next(x)
membuatx
bit acak.Sekarang mengapa ini penting? Karena sekitar setengah angka yang dihasilkan oleh bagian pertama (sebelum pembagian) kurang dari
1L << 52
, dan karena itu signifikansi mereka tidak sepenuhnya mengisi 53 bit yang bisa diisi, berarti bit paling signifikan dari signifikansi selalu nol untuk mereka.Karena besarnya perhatian yang diterima ini, berikut adalah beberapa penjelasan tambahan tentang seperti apa bahasa
double
Java (dan banyak bahasa lainnya) dan mengapa itu penting dalam pertanyaan ini.Pada dasarnya,
double
terlihat seperti ini: ( sumber )Detail yang sangat penting yang tidak terlihat dalam gambar ini adalah bahwa angka-angka "dinormalisasi" 1 sehingga fraksi 53 bit dimulai dengan 1 (dengan memilih eksponen sedemikian rupa), 1 kemudian dihilangkan. Itu sebabnya gambar menunjukkan 52 bit untuk fraksi (signifikansi) tetapi ada efektif 53 bit di dalamnya.
Normalisasi berarti bahwa jika dalam kode untuk
nextDouble
bit ke -53 diatur, bit itu adalah yang terdepan 1 dan hilang, dan 52 bit lainnya disalin secara harfiah ke signifikansi yang dihasilkandouble
. Namun, jika bit itu tidak disetel, bit yang tersisa harus digeser ke kiri sampai ditetapkan.Rata-rata, setengah angka yang dihasilkan masuk ke dalam kasus di mana signifikansi tidak bergeser ke kiri sama sekali (dan sekitar setengahnya memiliki 0 sebagai bit paling signifikan), dan setengah lainnya digeser oleh setidaknya 1 (atau hanya sepenuhnya nol) jadi bit paling signifikan mereka selalu 0.
1: tidak selalu, jelas itu tidak dapat dilakukan untuk nol, yang tidak memiliki angka tertinggi 1. Angka-angka ini disebut angka denormal atau subnormal, lihat wikipedia: nomor denormal .
sumber
random.nextDouble()
biasanya merupakan cara "terbaik" untuk apa yang dimaksudkan, tetapi kebanyakan orang tidak mencoba untuk menghasilkan hash 1-bit dari double acak mereka. Apakah Anda mencari distribusi yang seragam, resistensi terhadap kriptanalisis, atau apa?next
harus mengembalikanint
, sehingga hanya dapat memiliki hingga 32 bitDari dokumen :
Tapi itu juga menyatakan yang berikut (penekanan milikku):
Catatan ini sudah ada sejak Java 5 setidaknya (dokumen untuk Java <= 1.4 berada di belakang panel masuk, terlalu malas untuk memeriksa). Ini menarik, karena masalahnya ternyata masih ada bahkan di Jawa 8. Mungkin versi "tetap" tidak pernah diuji?
sumber
Hasil ini tidak mengejutkan saya mengingat bagaimana angka floating-point direpresentasikan. Misalkan kita memiliki tipe floating-point yang sangat pendek dengan presisi hanya 4 bit. Jika kita menghasilkan angka acak antara 0 dan 1, didistribusikan secara seragam, akan ada 16 nilai yang mungkin:
Jika itu yang mereka lihat di mesin, Anda bisa menguji bit orde rendah untuk mendapatkan distribusi 50/50. Namun, IEEE float direpresentasikan sebagai kekuatan 2 kali mantissa; satu bidang dalam float adalah kekuatan 2 (ditambah offset tetap). Kekuatan 2 dipilih sehingga bagian "mantissa" selalu berupa angka> = 1.0 dan <2.0. Ini berarti bahwa, pada dasarnya, angka-angka selain
0.0000
akan diwakili seperti ini:(
1
Sebelum titik biner adalah nilai tersirat; untuk mengapung 32- dan 64-bit, sebenarnya tidak ada bit yang dialokasikan untuk menampung ini1
.)Tetapi melihat di atas harus menunjukkan mengapa, jika Anda mengubah representasi menjadi bit dan melihat bit rendah, Anda akan mendapatkan nol 75% dari waktu. Ini disebabkan oleh semua nilai kurang dari 0,5 (biner
0.1000
), yang merupakan setengah dari nilai yang mungkin, setelah mantisa mereka bergeser, menyebabkan 0 muncul dalam bit rendah. Situasinya pada dasarnya sama ketika mantissa memiliki 52 bit (tidak termasuk 1 tersirat) seperti yangdouble
dilakukan.(Sebenarnya, seperti yang disarankan @sneftel dalam komentar, kami dapat menyertakan lebih dari 16 nilai yang mungkin dalam distribusi, dengan menghasilkan:
Tapi saya tidak yakin itu jenis distribusi yang kebanyakan programmer harapkan, jadi mungkin tidak bermanfaat. Plus itu tidak banyak membantu Anda ketika nilai digunakan untuk menghasilkan bilangan bulat, seperti nilai floating-point acak sering.)
sumber