generatore casuale non è abbastanza buono?

Problemi principali del tuo approccio:

• System.nanoTime () non è (da solo) un'utile fonte di bit casuali - è molto probabile che produca lo stesso valore più volte di seguito se lo si chiama in rapida successione perché molti sistemi in realtà non lo fanno avere un timer sufficientemente accurato. Anche se era accurato al nano secondo, è probabile che si ottengano modelli prevedibili dai bit più bassi se lo si campiona in un ciclo stretto. Gli usi validi di System.nanoTime nella generazione di numeri casuali potrebbero essere: a) inizializzazione una tantum di un valore di seme o b) occasionalmente aggiungendo un po 'di casualità in più in un pool di entropia (non è garantito che sia vantaggioso, ma non può ferire)
• Anche se i bit fossero veramente casuali, aggiungendo i valori 0/1 n volte si creerebbe una distribuzione in stile binomiale con una media di n / 2, cioè non una distribuzione uniforme che è presumibilmente ciò che l'intervistatore si aspettava .
• Il tuo algoritmo è O (n) - non buono per generare numeri casuali con un grande valore di n!

Preferisci idealmente un PRNG che generi nuovi bit pseudo-casuali da uno stato interno. Ecco quello che uso:

private static volatile long state = 0xCAFEBABE; // initial non-zero value

public static final long nextLong() {
  long a=state;
  state = xorShift64(a);
  return a;
}

public static final long xorShift64(long a) {
  a ^= (a << 21);
  a ^= (a >>> 35);
  a ^= (a << 4);
  return a;
}

public static final int random(int n) {
  if (n<0) throw new IllegalArgumentException();
  long result=((nextLong()>>>32)*n)>>32;
  return (int) result;
}

Questo è basato sull'algoritmo XORShift di George Marsaglia. Produce buoni numeri pseudocasuali ed è molto veloce (in genere anche più veloce di un generatore a congruenza lineare poiché gli xors e i turni sono più economici di moltiplica e si divide sulla maggior parte dell'hardware).

Detto questo, non mi aspetto che le persone memorizzino questo tipo di algoritmo per un colloquio a meno che tu non stia specificatamente facendo domanda per un ruolo come programmatore di crittografia!

prima disponi di una distribuzione binomiale (i valori verso n / 2 hanno maggiori probabilità di verificarsi rispetto a 0 o n-1)

un modo migliore sarebbe stato generare i bit di ceil (log2 (n)) e restituire il valore quando il valore è inferiore a n e riavviare altrimenti

public static int random(int n) {
    while(true){
        int r = 0;
        for (int i =1; i<n;i<<=1) {
            r=(r<<1)|helper();
        }
        if(r<n)return r;
    }
}

anche nanoTime () è preciso esattamente come il sistema può fornire, il che significa che t%2 potrebbe essere distorto 1 o 0 . Chiamarlo in un circuito così stretto dà una probabilità molto alta che i valori restituiti siano gli stessi su una macchina con una bassa precisione

una soluzione molto migliore sarebbe implementare un RNG appropriato come un generatore a congruenza lineare e utilizzarlo per la generazione del bit casuali

Come altri hanno già detto, il problema è che stai riassumendo i tuoi bit. Quando scegli un numero tra 0 e 4 il tuo algoritmo sceglierà il due il più delle volte perché ci sono molti altri modi per ottenere un due sommando i bit:

0: 0+0+0+0
1: 1+0+0+0, 0+1+0+0, 0+0+1+0, 0+0+0+1
2: 1+1+0+0, 1+0+1+0, 1+0+0+1, 0+1+1+0, 0+1+0+1, 0+0+1+1  
2: 0+1+1+1, 1+0+1+1, 1+1+0+1, 1+1+1+0
4: 1+1+1+1

L'uso dei bit shifts ti avrebbe dato una distribuzione molto migliore, ma avresti comunque ottenuto valori cattivi da un timer in un ciclo stretto.

Non lo so con certezza, ma immagino che ci siano ben collaudate funzioni di hash normalmente distribuite nelle librerie standard di Java. A partire da un seme di, ad esempio il timer, potresti fare qualcosa di simile:

randomBits = hashFunction(seed)
seed = randomBits
return seed % n

Non sono un matematico e sono un po 'preoccupato che il modulo alla fine possa distorcere la distribuzione, ma sarebbe molto più casuale della somma dei bit e potrebbe essere scritto rapidamente in un'intervista.

Una semplice classe di generatori di numeri casuali sono i generatori congruenziali lineari , che generano numeri attraverso state = (state * a + b) % c .

La classe Random di Java funziona esattamente così, usando l'ora del sistema come stato iniziale. Lo stato in java.util.Random ha una dimensione di 48 bit, mentre restituisce sempre al massimo 32 bit, quindi sembra "abbastanza casuale". I LGC non sono grandi generatori di numeri casuali, ma svolgono il loro lavoro se sono necessari solo pochi valori.

Probabilmente si aspettava che tu usassi la classe Random di Java .

La tua attuale implementazione prende una somma di risultati di "lancio della moneta" per determinare un numero casuale. Anche se i risultati saranno alquanto casuali, non saranno equamente distribuiti. Se tiri due dadi, finirai con un totale di 7 circa la metà del tempo. Questo approccio alla generazione di numeri casuali è soggetto alla stessa matematica.

Le persone che implementano le librerie Java hanno fatto di tutto per risolvere molti dei problemi legati alla generazione casuale di numeri, e di solito è meglio usarli quando offrono una soluzione al tuo problema. Non c'è bisogno di reinventare la ruota.

Se vuoi sapere come generare un buon generatore di numeri casuali, puoi sempre leggere su come Java implementa il loro!

Per la risposta di cratchet freak aggiungerei che l'intervistatore probabilmente ha considerato il tuo uso di System.nanoTime() come imbroglio dal , in un certo senso, si tratta di un generatore di numeri casuali esterno, anche se non molto buono da solo.

Probabilmente voleva che tu implementassi un generatore chiaramente deterministico da zero, come quello di Wikipedia evidenziato da "cratchet freak" .

Potresti usare la tua attuale implementazione per fornire 0 (o buoni) casuali buoni 0 non 1 aggiungendo un timer per qualche entropia. Abbiamo organizzato un piccolo concorso e questa soluzione è stata tra le migliori: eri molto vicino:

public static void random(int iterations) throws InterruptedException{
    for(int i = 1 ; i <= iterations ; i++){
        System.out.print(System.nanoTime() % 2);
        Thread.sleep(0, 200);
        if(i % 1000 == 0){
            System.out.println();
        }
    }
}

Ecco la risposta corretta: la creazione di un buon generatore di numeri casuali è difficile . Se non è qualcosa che hai appreso in modo specifico, allora è impossibile trovare qualcosa di remotamente utile. Se l'hai imparato, allora non è ancora qualcosa che probabilmente potresti fare dalla memoria.

Potresti sapere di un generatore di numeri casuali congruenziali lineari, ma ci sono alcune costanti coinvolte che necessitano di analisi molto complicate per avere ragione. Qualcosa che avresti cercato su internet. Potresti aver sentito parlare dell'algoritmo KISS di Marsaglia o del twister di Mersenne. Ognuno che non proverei nemmeno a implementare senza cercare i dettagli su Internet.

Ci sono pochissimi lavori di programmazione in cui vorrei tenerlo contro di te se non riesci a scrivere un buon generatore di numeri casuali. Detto questo, quello che dovresti dire è: "Non l'ho mai fatto, non so se il risultato sarebbe stato buono". Quindi scrivi un algoritmo: il risultato di qualsiasi cosa è positivo. E poi la cosa importante: scrivi del codice che testa il generatore di numeri casuali. Ad esempio, utilizza n = 20 e verifica che il risultato non sia mai inferiore a 0 o superiore a 20 e stampa la frequenza con cui ogni numero da 0 a 20 viene visualizzato in 2100 chiamate (ci si augura che ciascuna venga visualizzata circa 100 volte ).

In pratica, al di fuori dell'intervista, avresti bisogno di qualcuno che sappia come scrivere un generatore di numeri casuali rispetto ai ragazzi responsabili del codice nella libreria Java. Quella persona sarebbe piuttosto rara.