La respuesta de Dave Buchfuhrer es correcta, bajo el supuesto de que puede acceder a un bit arbitrario en la representación de [math] n [/ math] en tiempo constante. Esta es una suposición razonable: los detalles de acceso a la representación bit a bit de la entrada generalmente se suprimen en el tiempo de ejecución asintótico de un algoritmo, y estamos imaginando (de manera algo fantasiosa) una máquina que opera con números enteros de precisión arbitraria en tiempo constante.
Pero estrictamente hablando, esto no se puede hacer. Su algoritmo recibe un número [math] n [/ math] como entrada, por lo que necesita al menos [math] \ log (n) [/ math] pasos solo para leer lo que le da. Si solo se permiten operaciones de nivel de bit [math] O (1) [/ math], nunca podría producir más de [math] 2 ^ {O (1)} [/ math] salidas diferentes, por lo que solo puede producir secuencias repetitivas
Si permite las operaciones [math] \ log (n) [/ math], hay una miríada de cosas que puede hacer para codificar los dígitos de la entrada en algo suave. La sugerencia de Dave de tomar el segundo dígito más significativo está bien en el sentido de que es estadísticamente uniforme a nivel de un solo bit y no se repite. Pero definitivamente no pasará pruebas de aleatoriedad más fuertes, ya que produce una secuencia altamente estructurada:
- ¿Cuándo debo usar un árbol de sufijos sobre una matriz de sufijos?
- Cómo resolver este problema con un árbol de segmentos o BIT
- ¿Las estructuras de datos son más importantes o es el lenguaje?
- ¿Qué patrones de diseño y algoritmos comunes necesito saber para el desarrollo de Android?
- ¿Cómo funciona el algoritmo de búsqueda de ruta de StarCraft II?
01010011000011110000000011111111…
Si necesita algo más suave, básicamente está buscando un solo bit (o dígito) de una función hash fuerte que opera en tiempo lineal en el tamaño de su entrada (que es el número de bits, a saber, [math] \ log ( n) [/ matemáticas]). El objetivo de las funciones hash criptográficas es que procesan una entrada de longitud arbitraria y producen un valor de longitud fija que tiene varias propiedades de suavidad. Esa es solo tu pregunta.
Por las razones que mencioné, no puede esperar que una función de hash funcione en tiempo constante. Debe permitir el tiempo de ejecución logarítmico, es decir, el tiempo lineal en términos de la longitud de la cadena, que es la representación en bits de [math] n [/ math]. Con eso en mente, cualquier función hash fuerte funcionaría; hoy, probablemente importaría la biblioteca BLAKE y la usaría.
