metodo - numeros aleatorios negativos y positivos en java

¿Es java.util.Random realmente que aleatorio? ¿Cómo puedo generar 52! ¿Secuencias posibles(factoriales)?

Question

He estado usando Random (java.util.Random) para barajar un mazo de 52 cartas. Hay 52! (8.0658175e + 67) posibilidades. Sin embargo, he descubierto que la semilla para java.util.Random es long , que es mucho más pequeña en 2 ^ 64 (1.8446744e + 19).

Desde aquí, sospecho si java.util.Random es realmente aleatorio ; ¿Es realmente capaz de generar los 52! posibilidades?

Si no, ¿cómo puedo generar de manera confiable una mejor secuencia aleatoria que pueda producir los 52! posibilidades?

Answer 1

En general, un generador de números pseudoaleatorios (PRNG) no puede elegir entre todas las permutaciones de una lista de 52 elementos si la longitud de su estado es inferior a 226 bits.

java.util.Random implementa un algoritmo con un módulo de 2 ⁴⁸ ; por lo tanto, su estado de longitud es de solo 48 bits, mucho menor que los 226 bits a los que me he referido. Deberá usar otro PRNG con una longitud de estado mayor, específicamente, uno con un período de 52 factorial o mayor.

Véase también "Barajar" en mi artículo sobre generadores de números aleatorios .

Esta consideración es independiente de la naturaleza del PRNG; se aplica igualmente a los PRNG criptográficos y no criptográficos (por supuesto, los PRNG no criptográficos son inapropiados cuando se trata de seguridad de la información).

Aunque java.security.SecureRandom permite la java.security.SecureRandom semillas de longitud ilimitada, la implementación de SecureRandom podría usar un PRNG subyacente (por ejemplo, "SHA1PRNG" o "DRBG"). Y depende del período de ese PRNG (y, en menor medida, de la longitud del estado) si es capaz de elegir entre 52 permutaciones factoriales. (Tenga en cuenta que defino "longitud de estado" como el "tamaño máximo de la semilla que un PRNG puede tomar para inicializar su estado sin acortar ni comprimir esa semilla ").

Answer 2

La selección de una permutación aleatoria requiere simultáneamente más y menos aleatoriedad de lo que implica su pregunta. Dejame explicar.

La mala noticia: necesita más aleatoriedad.

La falla fundamental en su enfoque es que está tratando de elegir entre ~ 2 ²²⁶ posibilidades usando 64 bits de entropía (la semilla aleatoria). Para elegir de manera justa entre ~ 2 ²²⁶ posibilidades, tendrá que encontrar una manera de generar 226 bits de entropía en lugar de 64.

Hay varias formas de generar bits aleatorios: hardware dedicado , instrucciones de CPU , interfaces de sistema operativo , servicios en línea . Ya existe una suposición implícita en su pregunta de que, de alguna manera, puede generar 64 bits, así que solo haga lo que fuera a hacer, solo cuatro veces, y done los excedentes a la caridad. :)

La buena noticia: necesita menos aleatoriedad.

Una vez que tienes esos 226 bits aleatorios, el resto se puede hacer de manera determinista y por lo tanto las propiedades de java.util.Random pueden hacerse irrelevantes . Aquí es cómo.

Digamos que generamos los 52! Permutaciones (soportar conmigo) y ordenarlas lexicográficamente.

Para elegir una de las permutaciones, todo lo que necesitamos es un solo entero aleatorio entre 0 y 52!-1 . Ese entero es nuestro 226 bits de entropía. Lo usaremos como un índice en nuestra lista ordenada de permutaciones. Si el índice aleatorio se distribuye de manera uniforme, no solo se le garantiza que todas las permutaciones se pueden elegir, sino que se elegirán de manera equipotrabable (lo que es una garantía más fuerte que la pregunta).

Ahora, realmente no necesitas generar todas esas permutaciones. Puede producir uno directamente, dada su posición elegida al azar en nuestra lista ordenada hipotética. Esto se puede hacer en tiempo O (n ² ) usando el código Lehmer ^[1] (vea también las permutaciones de numeración y el sistema de números factoriadic ). La n aquí es el tamaño de tu mazo, es decir, 52.

Hay una implementación de C en esta respuesta de . Hay varias variables enteras allí que se desbordarían para n = 52, pero afortunadamente en Java puede usar java.math.BigInteger . El resto de los cálculos se pueden transcribir casi como está:

public static int[] shuffle(int n, BigInteger random_index) {
    int[] perm = new int[n];
    BigInteger[] fact = new BigInteger[n];
    fact[0] = BigInteger.ONE;
    for (int k = 1; k < n; ++k) {
        fact[k] = fact[k - 1].multiply(BigInteger.valueOf(k));
    }

    // compute factorial code
    for (int k = 0; k < n; ++k) {
        BigInteger[] divmod = random_index.divideAndRemainder(fact[n - 1 - k]);
        perm[k] = divmod[0].intValue();
        random_index = divmod[1];
    }

    // readjust values to obtain the permutation
    // start from the end and check if preceding values are lower
    for (int k = n - 1; k > 0; --k) {
        for (int j = k - 1; j >= 0; --j) {
            if (perm[j] <= perm[k]) {
                perm[k]++;
            }
        }
    }

    return perm;
}

public static void main (String[] args) {
    System.out.printf("%s/n", Arrays.toString(
        shuffle(52, new BigInteger(
            "7890123456789012345678901234567890123456789012345678901234567890"))));
}

^[1] No debe confundirse con Lehrer . :)

Answer 3

Permítame disculparme por adelantado, porque es un poco difícil de entender ...

En primer lugar, ya sabes que java.util.Random no es completamente aleatorio. Genera secuencias de una manera perfectamente predecible a partir de la semilla. Es completamente correcto que, dado que la semilla tiene solo 64 bits de longitud, solo puede generar 2 ^ 64 secuencias diferentes. Si tuvieras que generar de alguna manera 64 bits aleatorios reales y usarlos para seleccionar una semilla, ¡no podrías usar esa semilla para elegir aleatoriamente entre todos los 52! Posibles secuencias con igual probabilidad.

Sin embargo, este hecho no tiene consecuencias , siempre y cuando no vaya a generar más de 2 ^ 64 secuencias, siempre que no haya nada ''especial'' o ''notablemente especial'' sobre las 2 ^ 64 secuencias que puede generar. .

Digamos que usted tenía un PRNG mucho mejor que usaba semillas de 1000 bits. Imagina que tienes dos formas de inicializarlo: una manera lo inicializarías utilizando la semilla completa y la otra manera reduciría la semilla a 64 bits antes de inicializarla.

Si no supiera qué inicializador fue cuál, ¿podría escribir algún tipo de prueba para distinguirlos? A menos que haya tenido la (mala) suerte de terminar inicializando el malo con los mismos 64 bits dos veces, entonces la respuesta es no. No se podría distinguir entre los dos inicializadores sin un conocimiento detallado de alguna debilidad en la implementación específica de PRNG.

Alternativamente, imagine que la clase Random tenía una matriz de 2 ^ 64 secuencias que se seleccionaron completamente y al azar en algún momento en el pasado distante, y que la semilla era solo un índice en esta matriz.

Por lo tanto, el hecho de que Random use solo 64 bits para su semilla no es necesariamente un problema estadístico, siempre que no haya una posibilidad significativa de que uses la misma semilla dos veces.

Por supuesto, para fines criptográficos , una semilla de 64 bits no es suficiente, porque lograr que un sistema use la misma semilla dos veces es computacionalmente factible.

EDITAR:

Debo añadir que, aunque todo lo anterior es correcto, la implementación real de java.util.Random no es impresionante. Si está escribiendo un juego de cartas, quizás use la API MessageDigest para generar el hash SHA-256 de "MyGameName"+System.currentTimeMillis() , y use esos bits para barajar el mazo. Según el argumento anterior, siempre que sus usuarios no estén realmente jugando, no tiene que preocuparse de que currentTimeMillis devuelva mucho. Si sus usuarios realmente están apostando, entonces use SecureRandom sin semilla.

Answer 4

Si considera que el número es solo una matriz de bits (o bytes), tal vez podría usar las soluciones (seguras) Random.nextBytes sugeridas en esta pregunta de desbordamiento de pila y luego asignar la matriz a un new BigInteger(byte[]) .

Answer 5

Solución corta que es esencialmente la misma de dasblinkenlight:

// Java 7
SecureRandom random = new SecureRandom();
// Java 8
SecureRandom random = SecureRandom.getInstanceStrong();

Collections.shuffle(deck, random);

No tienes que preocuparte por el estado interno. Explicación larga por qué:

Cuando crea una instancia de SecureRandom esta manera, accede a un generador de números aleatorios verdaderos específico del sistema operativo. Esto es un conjunto de entropía donde se accede a valores que contienen bits aleatorios (por ejemplo, para un temporizador de nanosegundos, la precisión de nanosegundos es esencialmente aleatoria) o un generador de números de hardware interno.

Esta entrada (!) Que aún puede contener trazas espurias se alimenta a un hash criptográficamente fuerte que elimina esas trazas. ¡Esa es la razón por la que se usan esos CSPRNG, no para crear esos números ellos mismos! SecureRandom tiene un contador que rastrea la cantidad de bits que se usaron ( getBytes() , getLong() etc.) y rellena SecureRandom con bits de entropía cuando es necesario .

En resumen: simplemente olvide las objeciones y use SecureRandom como verdadero generador de números aleatorios.

Answer 6

Su análisis es correcto: sembrar un generador de números pseudoaleatorios con cualquier semilla específica debe producir la misma secuencia después de un orden aleatorio, limitando el número de permutaciones que podría obtener a 2 ⁶⁴ . Esta afirmación es fácil de verificar experimentalmente llamando a Collection.shuffle dos veces, pasando un objeto Random inicializado con la misma semilla y observando que las dos aleatorias aleatorias son idénticas.

Una solución a esto, entonces, es usar un generador de números aleatorios que permita una semilla más grande. Java proporciona SecureRandom clase SecureRandom que podría inicializarse con una matriz de byte[] de tamaño virtualmente ilimitado. Luego puede pasar una instancia de SecureRandom a Collections.shuffle para completar la tarea:

byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);

Answer 7

Un algoritmo muy simple es aplicar SHA-256 a una secuencia de enteros que se incrementan de 0 en adelante. (Si se desea, se puede agregar una sal para "obtener una secuencia diferente".) Si suponemos que la salida de SHA-256 es "tan buena como" enteros distribuidos uniformemente entre 0 y 2 ²⁵⁶ - 1, entonces tenemos suficiente entropía para el tarea.

Para obtener una permutación de la salida de SHA256 (cuando se expresa como un entero), simplemente se necesita reducir el módulo 52, 51, 50 ... como en este pseudocódigo:

deck = [0..52]
shuffled = []
r = SHA256(i)

while deck.size > 0:
    pick = r % deck.size
    r = floor(r / deck.size)

    shuffled.append(deck[pick])
    delete deck[pick]

Answer 8

Voy a tomar un poco de una manera diferente en esto. Tienes razón en tus suposiciones: ¡tu PRNG no podrá alcanzar los 52! posibilidades

La pregunta es: ¿cuál es la escala de su juego de cartas?

¿Si estás haciendo un juego simple al estilo klondike? Entonces definitivamente no necesitas los 52! posibilidades En vez de eso, míralo así: un jugador tendrá 18 quintillones de juegos distintos. Incluso teniendo en cuenta el "Problema de cumpleaños", tendrían que jugar miles de millones de manos antes de encontrarse con el primer juego duplicado.

¿Si estás haciendo una simulación de monte-carlo? Entonces probablemente estés bien. Es posible que tenga que lidiar con artefactos debido a la ''P'' en PRNG, pero probablemente no tendrá problemas simplemente debido a un bajo espacio inicial (nuevamente, está viendo quintillones de posibilidades únicas). Por otro lado, si está trabajando con una gran cantidad de iteraciones, entonces, sí, su bajo espacio inicial podría ser un factor decisivo.

¿Si estás haciendo un juego de cartas multijugador, particularmente si hay dinero en la línea? Luego, tendrá que hacer un poco de googlear sobre cómo los sitios de póquer en línea manejan el mismo problema que usted pregunta. Porque si bien el problema del espacio inicial reducido no es perceptible para el jugador promedio, es explotable si vale la pena el tiempo invertido. (Todos los sitios de póquer pasaron por una fase en la que sus PRNG fueron "pirateados", permitiendo que alguien vea las cartas ocultas de todos los demás jugadores, simplemente deduciendo la semilla de las cartas expuestas). No busque simplemente un PRNG mejor, tendrá que tratarlo tan seriamente como un problema de Crypto.