Genera numeri casuali senza utilizzare alcuna funzione esterna

Question

Queste sono state le domande poste in una delle interviste a cui ho partecipato di recente.

Per quanto ne so un numero casuale tra due numeri può essere generato come segue

public static int rand(int low, int high) { 
    return low + (int)(Math.random() * (high - low + 1)); 
} 

Ma qui sto usando Math.random() per generare un numero casuale compreso tra 0 e 1 e l'utilizzo che per aiutami a generare tra basso e alto. C'è un altro modo che posso fare direttamente senza usare le funzioni esterne?

Answer 1

Tipici generatori di numeri pseudo-casuali calcolano nuovi numeri in base a quelli precedenti, quindi in teoria sono completamente deterministici. L'unica casualità è garantita fornendo un buon seed (inizializzazione dell'algoritmo di generazione di numeri casuali). Finché i numeri casuali non sono molto critici per la sicurezza (ciò richiederebbe numeri "reali" casuali), un generatore di numeri casuali ricorsivo spesso soddisfa i bisogni.

La generazione ricorsiva può essere espressa senza alcuna funzione "esterna", una volta fornito un seme. Ci sono un paio di algoritmi per risolvere questo problema. Un buon esempio è lo Linear Congruential Generator.

Un'implementazione pseudo-codice potrebbe essere simile alla seguente:

long a = 25214903917; // These Values for a and c are the actual values found 
long c = 11;   // in the implementation of java.util.Random(), see link 
long previous = 0; 

void rseed(long seed) { 
    previous = seed; 
} 

long rand() { 
    long r = a * previous + c; 
    // Note: typically, one chooses only a couple of bits of this value, see link 
    previous = r; 
    return r; 
} 

Hai ancora bisogno di seminare questo generatore con un certo valore iniziale. Questo può essere fatto eseguendo una delle seguenti operazioni:

• Utilizzando qualcosa come l'ora corrente (bene nella maggior parte dei casi non critici per la sicurezza come i giochi)
• Utilizzando hardware rumore (buono per casualità critici per la sicurezza)
• Utilizzando un numero costante (buona per il debug, dato che si ottiene sempre la stessa sequenza)
• Se non è possibile utilizzare qualsiasi funzione e non si desidera utilizzare un seme costante, e se si utilizza un linguaggio che consente questo, è anche possibile utilizzare alcuni memoria non inizializzata. Ad esempio, in C e C++, definire una nuova variabile, non assegnargli alcunché e utilizzarne il valore per inizializzare il generatore. Ma notate che questo è ben lungi dall'essere un "buon seme" e solo un trucco per soddisfare le vostre esigenze. Non usare mai questo nel codice reale.

noti che non v'è alcun algoritmo che può generare diversi valori per differenti corre con gli stessi ingressi senza accesso ad alcune fonti esterne come l'ambiente di sistema. Ogni generatore di numeri casuali ben seminato fa uso di alcune fonti esterne.

Answer 2

È possibile utilizzare l'indirizzo di una variabile o combinare l'indirizzo del più variabili per fare una più complessa ...

Answer 3

Si potrebbe ottenere l'ora di sistema corrente, ma che richiederebbe anche una funzione nella maggior parte delle lingue .

Answer 4

Il numero System.currentTimeMillis() conta come esterno?Si può sempre ottenere questo e calcolare mod da qualche valore massimo:

int rand = (int)(System.currentTimeMillis()%high)+low; 

Answer 5

lo si può fare senza le funzioni esterne, se si è permesso di usare un certo stato esterno (ad esempio un lungo inizializzato con il tempo di sistema attuale). Questo è sufficiente per implementare un semplice generatore di numeri psuedo-random.

In ogni chiamata alla funzione casuale, si utilizza lo stato per creare un nuovo valore casuale e aggiornare lo stato, in modo che le chiamate successive ottengano risultati diversi.

È possibile eseguire questa operazione con normali operazioni aritmetiche e/o bit a bit di Java, quindi non sono necessarie funzioni esterne.

Answer 6

Qui sto suggerendo alcune fonti con commento può essere utile a trovare:

• Time System: Monotonic in una giornata povera casuale. Veloce, facile.
• Punto del mouse: Casuale Ma non utile sul sistema standalone.
• Socket raw/rete locale (parte informativa del pacchetto): buono casuale Tecnico e richiede tempo: è possibile modellare una modalità di attacco per ridurre la casualità.
• Alcuni testo di input con permutazione: Veloce, modo comune e buono (secondo me).
• Tempi dell'interruzione dovuti a tastiera, unità disco e altri eventi: Modo comune - soggetto a errori se non utilizzato con attenzione.
• Un altro approccio è quello di alimentare un segnale di rumore analogico: esempio come temp.

• /procdati file: su sistema Linux. Sento che dovresti usare questo.

  /proc/sys/kernel/random: Questa directory contiene vari parametri per il controllo del funzionamento del file /dev/random.

  I file speciali di carattere /dev/random e /dev/urandom (presenti dal Linux 1.3.30) forniscono un'interfaccia al generatore di numeri casuali del kernel.

  provare questo commads:

  $cat /dev/urandom 
  

  e

  $cat /dev/random 
  

  È possibile scrivere un file di funzione che leggere da questo file leggere.

  Read (suggerisce anche): Is a rand from /dev/urandom secure for a login key?

`

Answer 7

si può arrivare vicino casualità (in realtà caotica e sicuramente non uniforme *) dalla mappa logistica x = 4x(1-x) a partire da un "non razionale" x tra 0 e 1.

La "casualità" appare a causa di gli errori di arrotondamento sul bordo della precisione della rappresentazione in virgola mobile.

(*) È possibile annullare l'inclinazione quando si sa che è lì.

Answer 8

Poisson Generatore casuale

Diciamo si parte con un valore di 'v' attesa dei numeri casuali. Quindi dire che una sequenza di numeri interi non negativi soddisfa una distribuzione di Poisson con valore atteso v significa che su sottosequenze, la media (media) del valore apparirà 'v'. La distribuzione di Poisson fa parte delle statistiche e i dettagli possono essere trovati su wikipedia. Ma qui il vantaggio principale di utilizzare questa funzione è: 1. Vengono generati solo valori interi. 2. La media di questi numeri interi sarà uguale al valore inizialmente fornito.

È utile in applicazioni in cui i valori frazionali non hanno senso. Come il numero di aerei che arrivano su un aeroporto in 1min è 2,5 (non ha senso) ma implica che in 2 minuti arrivano 5 piani.

int poissonRandom(double expectedValue) { 
    int n = 0; //counter of iteration 
    double limit; 
    double x; //pseudo random number 
    limit = exp(-expectedValue); 
    x = rand()/INT_MAX; 
    while (x > limit) { 
    n++; 
    x *= rand()/INT_MAX; 
    } 
    return n; 
} 

La linea

rand()/INT_MAX 

dovrebbe generare un numero casuale compreso tra 0 e 1. Quindi possiamo usare il tempo del sistema. Secondi/60 serviranno allo scopo. Quale funzione dovremmo usare dipende totalmente dall'applicazione.