E 'possibile ottenere un'approssimazione di un seme in base a una sequenza finita di numeri casuali pseudo?
Domanda
supponiamo di avere alcuni numeri che formano una serie per esempio: 652,328,1,254 e voglio ottenere un seme che, se io, per esempio, fare
srand(my_seed);
mi metterò qualche tipo di approssimazione con l'errore limitato alla mia successione origonal, quando tutti i numeri che compaiono nello stesso ordine.
Soluzione
Dipende l'algoritmo utilizzato per la generazione pseudo-casuale. Se l'algoritmo è un semplice href="http://en.wikipedia.org/wiki/Linear_congruential_generator" lineare congruenziale generatore , quindi ottenere il seme posteriore è solo una questione di risolvendo un'equazione modulare lineare (si noti che la soluzione può essere non univoco, ma come un tale generatore è senza memoria, non importa).
Se l'algoritmo è più complesso, questo può essere impossibile.
Si noti che l'algoritmo utilizzato nella libreria standard C non è limitata dalla norma, in modo da piattaforme diverse possono avere diverse implementazioni.
Altri suggerimenti
Non si può avere un errore legato in generale. O il vostro algoritmo funziona o non è così. La ragione di questo è che un errore ragionevole bound è ovviamente molto più piccolo che RAND_MAX. Che a sua volta significa che i bit bassi non sono casuale come i bit superiori. Ma un buon PRNG fa certo che tutti i bit sono ugualmente casuale.
Si consideri l'esempio lento ma matematicamente suono di un algoritmo RNG:
int rand() {
state = AES_encrypt(state);
return state % RAND_MAX;
}
void srand(int seed) {
state = AES_encrypt(seed);
}
Se si riesce a trovare alcuna correlazione significativa tra la sequenza di uscita e la state
precedente, l'algoritmo AES dovrebbe essere considerato rotto.
La definizione di un PRNG crytographic è quello in cui questa struttura esatta è computazionalmente impossibile - tuttavia, come è stato detto, ci sono PRNGs per cui ciò è possibile molto più debole (molto più veloce e). Quindi dipende dal vostro algoritmo.