Perché questo valore casuale ha una distribuzione 25/75 anziché 50/50?

Question

Modifica: Quindi in pratica quello che sto cercando di scrivere è un hash 1 bit per double.

voglio mappare una double a true o false con una possibilità 50/50. Per questo ho scritto il codice che seleziona alcuni numeri casuali (proprio come un esempio, voglio usarlo sui dati con regolarità e ottenere comunque un risultato 50/50), controlla il loro ultimo bit e incrementa y se è 1, o n se è 0.

Tuttavia, questo codice produce costantemente il 25% di e il 75% di n. Perché non è 50/50? E perché una distribuzione così strana, ma semplice (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); 
    } 
} 

uscita Esempio:

250167 749833 

Answer 1

Poiché nextDouble funziona così: (source)

public double nextDouble() 
{ 
    return (((long) next(26) << 27) + next(27))/(double) (1L << 53); 
} 

next(x) rende x bit casuali.

Ora, perché questo importa? Perché circa la metà dei numeri generati dalla prima parte (prima della divisione) sono inferiori a 1L << 52, e quindi il loro significato e non riempie interamente i 53 bit che potrebbe riempire, ovvero il bit meno significativo del significato e sempre zero per quelli .

---

A causa della quantità di attenzione questo sta ricevendo, ecco qualche spiegazione in più di ciò che un double in Java (e molte altre lingue) Sembra veramente e perché avesse importanza in questa domanda.

Fondamentalmente, un double appare così: (source)

Un dettaglio molto importante non visibile in questa immagine è che i numeri sono "normalizzate" tali che inizia frazione 53 bit con un 1 (scegliendo l'esponente in modo tale che sia così), quel 1 viene quindi omesso. Questo è il motivo per cui l'immagine mostra 52 bit per la frazione (significato e) ma ci sono effettivamente 53 bit in esso.

La normalizzazione significa che se nel codice per nextDouble viene impostato il bit 53a, che è il bit 1 iniziale implicito e va via, e gli altri 52 bit vengono copiati letteralmente il significante della risultante double. Se quel bit non è impostato, i bit rimanenti devono essere spostati a sinistra finché non viene impostato.

In media, la metà dei numeri generati cadere nel caso in cui il significante era non spostata a sinistra a tutti (e circa la metà quelli hanno un 0 come loro bit meno significativo), e l'altra metà viene spostato da almeno 1 (o è solo completamente zero) quindi il loro bit meno significativo è sempre 0.

1: non sempre, chiaramente non può essere fatto per zero, che non ha il massimo 1. Questi numeri sono chiamati numeri denormali o subnormali, vedere wikipedia:denormal number.

Answer 2

Dal docs:

Il metodo nextDouble è implementato da classe Random come per:

public double nextDouble() { 
    return (((long)next(26) << 27) + next(27)) 
    /(double)(1L << 53); 
} 

Ma afferma anche quanto segue (sottolineatura mia):

[Nelle prime versioni di Java, il risultato è stato calcolato erroneamente come:

return (((long)next(27) << 27) + next(27)) 
    /(double)(1L << 54); 

Questo potrebbe sembrare equivalenti, se non migliore, ma in realtà introdotto un grande disuniformità causa della distorsione nel arrotondamento dei numeri in virgola mobile: era tre volte più probabile che il basso il bit di ordine del significato e sarebbe 0 di quello che sarebbe 1! Questa non uniformità probabilmente non importa molto, in pratica, ma costante ricerca della perfezione.]

Questa nota è lì dal Java 5, almeno (documentazione per Java < = 1.4 sono dietro un loginwall, troppo pigro per controllare). Questo è interessante, perché il problema apparentemente esiste ancora anche in Java 8. Forse la versione "fissa" non è mai stata testata?

Answer 3

Questo risultato non mi sorprende dato come vengono rappresentati i numeri in virgola mobile. Supponiamo di avere un tipo a virgola mobile molto breve con solo 4 bit di precisione. Se dovessimo generare un numero casuale compreso tra 0 e 1, distribuita in modo uniforme, ci sarebbero 16 possibili valori:

0.0000 
0.0001 
0.0010 
0.0011 
0.0100 
... 
0.1110 
0.1111 

Se questo è il modo in cui guardavano nella macchina, si potrebbe verificare il bit a basso fine di ottenere un Distribuzione 50/50. Tuttavia, i galleggianti IEEE sono rappresentati come una potenza di 2 volte una mantissa; un campo nel float è la potenza di 2 (più un offset fisso). La potenza di 2 è selezionata in modo che la parte "mantissa" sia sempre un numero> = 1.0 e < 2.0. Ciò significa che, in effetti, i numeri diversi 0.0000 sarebbero rappresentati simili:

0.0001 = 2^(-4) x 1.000 
0.0010 = 2^(-3) x 1.000 
0.0011 = 2^(-3) x 1.100 
0.0100 = 2^(-2) x 1.000 
... 
0.0111 = 2^(-2) x 1.110 
0.1000 = 2^(-1) x 1.000 
0.1001 = 2^(-1) x 1.001 
... 
0.1110 = 2^(-1) x 1.110 
0.1111 = 2^(-1) x 1.111 

(Il 1 prima del punto binario è un valore implicito; per galleggianti 32 e 64 bit, nessun bit è in realtà assegnato per contenere questo 1.)

Ma guardando a quanto sopra dovrebbe dimostrare perché, se si converte la rappresentazione in bit e si guarda il bit basso, si otterrà zero il 75% delle volte. Ciò è dovuto a tutti i valori inferiori a 0,5 (binario 0.1000), che è la metà dei valori possibili, avendo spostato la loro mantissa, causando la comparsa di 0 nel bit basso. La situazione è essenzialmente la stessa quando la mantissa ha 52 bit (escluso l'implicito 1) come fa double.

(In realtà, come @sneftel suggerito in un commento, abbiamo potuto includere più di 16 possibili valori nella distribuzione, generando:

0.0001000 with probability 1/128 
0.0001001 with probability 1/128 
... 
0.0001111 with probability 1/128 
0.001000 with probability 1/64 
0.001001 with probability 1/64 
... 
0.01111 with probability 1/32 
0.1000 with probability 1/16 
0.1001 with probability 1/16 
... 
0.1110 with probability 1/16 
0.1111 with probability 1/16 

Ma io non sono sicuro che sia il tipo di distribuzione la maggior parte dei programmatori si aspetterebbe, quindi probabilmente non ne vale la pena, in più non guadagna molto quando i valori vengono utilizzati per generare numeri interi, come spesso accade con valori a virgola mobile casuali.)