Come generare un valore BigInteger casuale in Java?

Ho bisogno di generare numeri casuali arbitrariamente grandi nel range 0 (compreso) in n (esclusivo). Il mio pensiero iniziale era di chiamare nextDouble e moltiplicare per n, ma quando n nextDouble più grande di 2 53 , i risultati non sarebbero più distribuiti uniformsmente.

BigInteger ha il seguente costruttore disponibile:

 public BigInteger(int numBits, Random rnd) 

Costruisce un BigInteger generato casualmente, distribuito uniformsmente nell’intervallo da 0 a (2 numBits – 1), incluso.

Come può essere usato per ottenere un valore casuale nell’intervallo 0 – n, dove n non è una potenza di 2?

Usa un ciclo:

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

in media, questo richiederà meno di due iterazioni e la selezione sarà uniforms.

Modifica: se il tuo RNG è costoso, puoi limitare il numero di iterazioni nel seguente modo:

 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 questa versione, è altamente improbabile che il ciclo sia preso più di una volta (meno di una possibilità in 2 ^ 100 , cioè molto meno della probabilità che la macchina ospite incazzi spontaneamente nel secondo successivo). D’altra parte, l’operazione mod() è computazionalmente costosa, quindi questa versione è probabilmente più lenta della precedente, a meno che l’istanza di rnd sia eccezionalmente lenta.

Il seguente metodo utilizza il BigInteger(int numBits, Random rnd) e rifiuta il risultato se è più grande del n specificato.

 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; } 

Lo svantaggio di questo è che il costruttore è chiamato un numero imprecisato di volte, ma nel peggiore dei casi (n è appena leggermente maggiore di una potenza di 2) il numero previsto di chiamate al costruttore dovrebbe essere solo circa 2 volte.

L’approccio più semplice (in un modo piuttosto lungo) sarebbe quello di utilizzare il costruttore specificato per generare un numero casuale con il giusto numero di bit ( floor(log2 n) + 1 ), e poi buttarlo via se è maggiore di n. Nel peggiore dei casi ansible (ad es. Un numero compreso nell’intervallo [0, 2 n + 1), in media getti via meno della metà dei valori che crei.

Perché non build un BigInteger casuale, quindi creare un BigDecimal da esso? C’è un costruttore in BigDecimal: public BigDecimal(BigInteger unscaledVal, int scale) che sembra rilevante qui, no? Dagli un BigInteger casuale e una scala casuale int, e avrai un BigDecimal casuale. No ?

Ecco come lo faccio in una class chiamata Generic_BigInteger disponibile tramite: Pagina Web generica del codice sorgente di 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; } 

Basta usare la riduzione modulare

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

Compilare questo codice F # in una DLL e si può anche fare riferimento a esso nei programmi 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