generar cualquier entero aleatorio
Me disculpo de antemano porque no tengo mucha experiencia con ninguna noción formal de aleatoriedad.
El título dice la mayor parte: quiero generar un número entero aleatorio dentro de un tiempo razonable, donde cada número entero puede aparecer, ya sea con la misma frecuencia o no, no es importante. Como complemento, la memoria de la computadora no es un problema, ya que incluso con un espacio de memoria infinito para almacenar estos números generados, no es obvio cómo se puede hacer esto. No he progresado en la búsqueda de un algoritmo adecuado, pero aquí están mis observaciones.
Si puede generar cualquier número real al azar, entonces podría usar funciones como la función de piso para generar cualquier número entero. Si pudiera generar aleatoriamente cualquier número real entre cualquier intervalo$[a,b]$, entonces podrías usar funciones asintóticas como $\tan$ para generar cualquier número real.
En general, si tengo un conjunto S que tiene una cardinalidad mayor o igual a los números enteros, y puedo generar aleatoriamente un elemento dentro de S, entonces puedo generar aleatoriamente cualquier número entero mapeando miembros de S en los enteros.
Sé que hay secuencias, como la secuencia de espacios primos, que son aleatorias y contienen enteros arbitrariamente grandes, pero no se pueden calcular fácilmente.
Sin embargo, eso es todo con respecto a lo que puedo pensar. No me sorprendería que no hubiera una solución fácil al problema, pero si alguien tiene una razón de por qué esto no es posible, me gustaría escuchar también.
Respuestas
¡El tamaño arbitrario no tiene sentido ya que el cálculo no puede detenerse!
Considere que lanza una moneda por cada bit del entero aleatorio, entonces puede ver que el lanzamiento de la moneda es interminable.
Hay que tener cuidado al jugar con el tamaño arbitrario. Matemáticamente puedes decir que deja$x$ ser un número entero aleatorio, es decir $x \stackrel{R}{\leftarrow} \mathbb Z$sin embargo, cuando intente encontrar un valor de este, se enfrentará a la generación del mismo. Si quieres un entero aleatorio uniforme, ¡obviamente fallará!
Ahora suponga que tiene un límite como $0\color{red}{<} x \leq 2^L$entonces puede usar LFSR para generar números aleatorios en el rango. Si un LFSR con tamaño$L$ es máxima, entonces es periódica y tiene un período de $2^L-1$. En este período visita todos los posibles$L$-números de bits excepto el estado todo-cero. Puede obtener una semilla de la época y comenzar a usarla.
Tenga en cuenta que LFSR está lejos de ser un pseudogenerador aleatorio criptográficamente seguro (CSPRNG). Tener solo$2L$ La salida de bits del LFSR es suficiente para determinar los siguientes bits debido al algoritmo de Berlakamp-Massay, y en realidad, la eliminación gaussiana es suficiente, sin embargo, BM es mucho más rápido.