generare qualsiasi numero intero casuale
Chiedo scusa in anticipo perché non ho molta esperienza con alcuna nozione formale di casualità.
Il titolo dice quasi tutto: voglio generare un numero intero casuale entro un tempo ragionevole, in cui ogni numero intero può apparire, con uguale frequenza o meno non è importante. Inoltre, la memoria del computer non è un problema, poiché anche con uno spazio di memoria infinito per memorizzare questi numeri generati non è ovvio come si possa farlo. Non ho fatto alcun progresso nel capire effettivamente un algoritmo adeguato, ma ecco le mie osservazioni.
Se è possibile generare un numero reale in modo casuale, è possibile utilizzare funzioni come la funzione floor per generare qualsiasi numero intero. Se potessi generare in modo casuale qualsiasi numero reale tra qualsiasi intervallo$[a,b]$, allora potresti usare funzioni asintotiche come $\tan$ per generare qualsiasi numero reale.
In generale, se ho un insieme S che ha una cardinalità maggiore o uguale agli interi e posso generare casualmente un elemento all'interno di S, allora posso generare casualmente qualsiasi numero intero mappando i membri di S sugli interi.
So che ci sono sequenze, come la sequenza prime gap, che sono casuali e contengono numeri interi arbitrariamente grandi, ma non sono calcolabili facilmente.
Tuttavia questo è tutto per quanto riguarda ciò che posso pensare. Non sarei sorpreso se non ci fosse una soluzione facile al problema, ma se qualcuno ha una ragione sul perché questo non è possibile, vorrei sentire anche io.
Risposte
La dimensione arbitraria non ha alcun significato poiché il calcolo non può fermarsi!
Considera che lanci una moneta per ogni bit dell'intero casuale, quindi puoi vedere che il lancio della moneta non finisce mai.
Bisogna stare attenti quando si gioca con la dimensione arbitraria. Matematicamente puoi dire che lascia$x$ essere un numero intero casuale, ad es $x \stackrel{R}{\leftarrow} \mathbb Z$tuttavia, quando proverai a trovare un valore di questo, affronterai la sua generazione. Se vuoi un numero intero casuale uniforme, ovviamente fallirà!
Ora supponi di avere un limite come $0\color{red}{<} x \leq 2^L$quindi puoi usare LFSR per generare numeri casuali nell'intervallo. Se un LFSR con size$L$ è massimo, quindi è periodico e ha un periodo di $2^L-1$. In questo periodo visita tutto il possibile$L$-bit numeri eccetto lo stato tutto zero. Puoi ottenere un seme dal tempo e iniziare a usarlo.
Nota che LFSR è ben lungi dall'essere uno pseudo generatore casuale crittograficamente sicuro (CSPRNG). Avere solo$2L$ L'output di bit dall'LFSR è sufficiente per determinare i bit successivi a causa dell'algoritmo Berlakamp-Massay - e in realtà, l'eliminazione gaussiana è sufficiente, tuttavia, BM è molto più veloce-.