¿Cómo generar un valor BigInteger aleatorio en Java?

Question

Necesito generar enteros aleatorios arbitrariamente grandes en el rango de 0 (inclusive) a n (exclusivo). Mi idea inicial era llamar al nextDouble y multiplicar por n, pero una vez que n llega a ser mayor que 2 , los resultados ya no se distribuirán uniformemente.

BigInteger tiene la siguiente constructor disponibles:

public BigInteger(int numBits, Random rnd) 

Construye un BigInteger generado aleatoriamente, uniformemente distribuida en el intervalo de 0 a (2 ^numBits - 1), ambos inclusive.

¿Cómo se puede utilizar esto para obtener un valor aleatorio en el rango 0 - n, donde n no es una potencia de 2?

Answer 1

utilizar un bucle:

BigInteger r; 
do { 
    r = new BigInteger(n.bitLength(), rnd); 
} while (r.compareTo(n) >= 0); 

en promedio, esto requerirá menos de dos iteraciones, y la selección será uniforme.

Editar: Si el generador de números aleatorios es caro, se puede limitar el número de iteraciones de la siguiente manera:

int nlen = n.bitLength(); 
BigInteger nm1 = n.subtract(BigInteger.ONE); 
BigInteger r, s; 
do { 
    s = new BigInteger(nlen + 100, rnd); 
    r = s.mod(n); 
} while (s.subtract(r).add(nm1).bitLength() >= nlen + 100); 
// result is in 'r' 

Con esta versión, es altamente improbable que el bucle se toma más de una vez (menos de una oportunidad en 2^100, es decir, mucho menos que la probabilidad de que la máquina host se incendie espontáneamente en el siguiente segundo siguiente). Por otro lado, la operación mod() es computacionalmente costosa, por lo que esta versión probablemente sea más lenta que la anterior, a menos que la instancia rnd sea excepcionalmente lenta.

Answer 2

El enfoque más simple (en un largo camino) sería usar el constructor especificado para generar un número aleatorio con el número correcto de bits (floor(log2 n) + 1), y luego tirarlo si es mayor que n. En el peor de los casos posibles (por ejemplo, un número en el rango [0, 2 ⁿ + 1) tirará la mitad de los valores que crea, en promedio.

Answer 3

El siguiente método usa el constructor BigInteger(int numBits, Random rnd) y rechaza el resultado si es mayor que el n especificado.

public BigInteger nextRandomBigInteger(BigInteger n) { 
    Random rand = new Random(); 
    BigInteger result = new BigInteger(n.bitLength(), rand); 
    while(result.compareTo(n) >= 0) { 
     result = new BigInteger(n.bitLength(), rand); 
    } 
    return result; 
} 

El inconveniente de esto es que el constructor se llama un número indeterminado de veces, pero en el peor de los casos (n es sólo ligeramente mayor que una potencia de 2) el número esperado de llamadas al constructor debe ser solo alrededor de 2 veces

Answer 4

¿Por qué no construir un BigInteger aleatorio y luego construir un BigDecimal a partir de él? Hay un constructor en BigDecimal: public BigDecimal(BigInteger unscaledVal, int scale) que parece relevante aquí, ¿no? Dale un BigInteger aleatorio y una escala aleatoria int, y tendrás un BigDecimal aleatorio. No ?

Answer 5

Compila este código F # en un archivo DLL y también puedes hacer referencia a él en tu C#/VB.programas de redes de

type BigIntegerRandom() = 
    static let internalRandom = new Random() 

    /// Returns a BigInteger random number of the specified number of bytes. 
    static member RandomBigInteger(numBytes:int, rand:Random) = 
     let r = if rand=null then internalRandom else rand 
     let bytes : byte[] = Array.zeroCreate (numBytes+1) 
     r.NextBytes(bytes) 
     bytes.[numBytes] <- 0uy 
     bigint bytes 

    /// Returns a BigInteger random number from 0 (inclusive) to max (exclusive). 
    static member RandomBigInteger(max:bigint, rand:Random) = 
     let rec getNumBytesInRange num bytes = if max < num then bytes else getNumBytesInRange (num * 256I) bytes+1 
     let bytesNeeded = getNumBytesInRange 256I 1 
     BigIntegerRandom.RandomBigInteger(bytesNeeded, rand) % max 

    /// Returns a BigInteger random number from min (inclusive) to max (exclusive). 
    static member RandomBigInteger(min:bigint, max:bigint, rand:Random) = 
     BigIntegerRandom.RandomBigInteger(max - min, rand) + min 

Answer 6

Así es como lo hago en una clase llamada Generic_BigInteger disponible a través de: Andy Turner's Generic Source Code Web Page

/** 
* There are methods to get large random numbers. Indeed, there is a 
* constructor for BigDecimal that allows for this, but only for uniform 
* distributions over a binary power range. 
* @param a_Random 
* @param upperLimit 
* @return a random integer as a BigInteger between 0 and upperLimit 
* inclusive 
*/ 
public static BigInteger getRandom(
     Generic_Number a_Generic_Number, 
     BigInteger upperLimit) { 
    // Special cases 
    if (upperLimit.compareTo(BigInteger.ZERO) == 0) { 
     return BigInteger.ZERO; 
    } 
    String upperLimit_String = upperLimit.toString(); 
    int upperLimitStringLength = upperLimit_String.length(); 
    Random[] random = a_Generic_Number.get_RandomArrayMinLength(
     upperLimitStringLength); 
    if (upperLimit.compareTo(BigInteger.ONE) == 0) { 
     if (random[0].nextBoolean()) { 
      return BigInteger.ONE; 
     } else { 
      return BigInteger.ZERO; 
     } 
    } 
    int startIndex = 0; 
    int endIndex = 1; 
    String result_String = ""; 
    int digit; 
    int upperLimitDigit; 
    int i; 
    // Take care not to assign any digit that will result in a number larger 
    // upperLimit 
    for (i = 0; i < upperLimitStringLength; i ++){ 
     upperLimitDigit = new Integer(
       upperLimit_String.substring(startIndex,endIndex)); 
     startIndex ++; 
     endIndex ++; 
     digit = random[i].nextInt(upperLimitDigit + 1); 
     if (digit != upperLimitDigit){ 
      break; 
     } 
     result_String += digit; 
    } 
    // Once something smaller than upperLimit guaranteed, assign any digit 
    // between zero and nine inclusive 
    for (i = i + 1; i < upperLimitStringLength; i ++) { 
     digit = random[i].nextInt(10); 
     result_String += digit; 
    } 
    // Tidy values starting with zero(s) 
    while (result_String.startsWith("0")) { 
     if (result_String.length() > 1) { 
      result_String = result_String.substring(1); 
     } else { 
      break; 
     } 
    } 
    BigInteger result = new BigInteger(result_String); 
    return result; 
} 

Answer 7

sólo tiene que utilizar la reducción modular

new BigInteger(n.bitLength(), new SecureRandom()).mod(n)