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

generar numeros aleatorios y sumarlos en java

Question

Necesito generar enteros aleatorios arbitrariamente grandes en el rango de 0 (inclusive) a n (exclusivo). Mi idea inicial fue llamar a 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 el siguiente constructor disponible:

public BigInteger(int numBits, Random rnd)

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

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

Answer 1

¿Por qué no construir un BigInteger aleatorio y luego construir un BigDecimal a partir de él? Hay un constructor en BigDecimal: 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 2

Aquí es cómo lo hago en una clase llamada Generic_BigInteger disponible a través de: Página web genérica de código fuente de Andy Turner

/**
* 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 3

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

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 4

El enfoque más simple (por 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) arrojará a la mitad menos que los valores que crea, en promedio.

Answer 5

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 no especificado de veces, pero en el peor de los casos (n es solo un poco mayor que una potencia de 2), el número esperado de llamadas al constructor debería ser solo 2 veces.

Answer 6

Solo use reducción modular

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

Answer 7

Use 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 su RNG es costoso, 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 ciclo se tome más de una vez (menos de una posibilidad 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.