Un generatore di numeri casuali può mai produrre output diversi a parità di semi identici?

9

Il titolo lo riassume. Sono interessato a sapere se esiste un algoritmo in grado di produrre output variabile dato input identico senza fare affidamento su altre fonti per casualità come DateTime.Ora o un numero generato da un sensore di luce ecc. Inoltre, l'algoritmo non può essere eseguito in sequenza, solo due esecuzioni distinte, non correlate che producono output diversi.

    
posta ConditionRacer 15.07.2013 - 06:53
fonte

4 risposte

13

I'm interested to know if there exists an algorithm capable of producing variable output given identical input without relying on other sources for randomness such as DateTime.Now or a number generated from a light sensor etc.

No, ciò è fondamentalmente impossibile, perché la definizione stessa di un algoritmo è che è ben definita e deterministica, dato che lo stesso input produrrà sempre lo stesso risultato. Ci sono algoritmi randomizzati, ma richiedono la casualità come input.

Inoltre, il determinismo è il più importante obiettivo di progettazione dell'hardware del computer. Una CPU che non produce lo stesso output dato lo stesso input sarebbe completamente inutile per la maggior parte degli scopi.

    
risposta data 15.07.2013 - 11:33
fonte
14

No, un algoritmo di generazione di numeri pseudo-casuali produrrà sempre lo stesso risultato dato lo stesso seme (quindi pseudo -random).

Trovo interessante il fatto che tu abbia usato il termine "algoritmo" piuttosto che "programma". Questo esclude una certa classe di risposte sì (errori soft nella RAM, intrecci di thread diversi in un RNG multi-thread, ecc.). Se si dà per scontato che ogni esecuzione dell'algoritmo prenda lo stesso input su ciascuna iterazione sia ben specificata senza casualità, allora genererà lo stesso output su ogni esecuzione.

Detto questo, anche le cose basilari come la temperatura della CPU sono abbastanza imprevedibili da comportarsi come una fonte di entropia se vengono normalizzate in modo appropriato. Quindi, non pensate che ciò implichi che un generatore di numeri casuali "crittograficamente sicuro" possa essere previsto se si sa a che ora è stato eseguito; molti di loro fanno uso del feed di entropia generato dal sistema.

    
risposta data 15.07.2013 - 07:19
fonte
7

Sapevi che le persone lavorano molto duramente per garantire che, dato lo stesso seme, la stessa sequenza di numeri casuali sia prodotta ogni volta? Questa è una proprietà desiderabile per cose come la simulazione Monte Carlo, in quanto significa che i risultati sono pienamente riproducibili. Se non specifichi il seme, verrà usato qualcosa come il tempo, ma quella riproducibilità esatta è davvero desiderata.

Gli unici RNG in cui questo è veramente indesiderato sono quelli usati per la crittografia, e quelli in genere ottengono ciò usando la sorgente di numeri casuali del sistema operativo (che non è riavvolgibile in circostanze normali e che può usare hardware di fantasia) per fornire il loro seme.

    
risposta data 15.07.2013 - 07:52
fonte
1

Suppongo che se hai implementato l'algoritmo su piattaforme hardware diverse e hai usato tecniche come prendere gli N bit medi da un numero intero, potresti avere risposte diverse se la codifica dei numeri interi era diversa (big / little / mid-endian). Inoltre potresti incorrere in problemi in esecuzione su macchine con FPU rispetto a quelli che non funzionano se stai manipolando numeri in virgola mobile. Probabilmente non è un problema sui computer di classe desktop, ma potrebbe essere un problema sui telefoni.

    
risposta data 15.07.2013 - 18:33
fonte

Leggi altre domande sui tag