Come generare un valore BigInteger casuale in Java?

Question

Ho bisogno di generare numeri casuali arbitrariamente grandi nell'intervallo 0 (compreso) su n (esclusivo). Il mio primo pensiero era di chiamare nextDouble e moltiplicare per n, ma una volta che n diventa più grande di 2 , i risultati non sarebbero più distribuiti uniformemente.

BigInteger ha il seguente costruttore disponibile:

public BigInteger(int numBits, Random rnd) 

Costruisce un BigInteger generato in modo casuale, uniformemente distribuiti nell'intervallo da 0 a (2 ^numBits - 1) incluse.

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

Answer 1

usare un ciclo:

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

in media, ciò richiederà meno di due iterazioni, e la selezione sarà uniforme.

Edit: Se il RNG è costoso, è possibile limitare il numero di iterazioni 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 è preso più di una volta (meno di una possibilità in 2^100, vale a dire molto meno della probabilità che la macchina host si incendi 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 rnd sia eccezionalmente lenta.

Answer 2

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

Answer 3

Il seguente metodo utilizza il costruttore BigInteger(int numBits, Random rnd) e rifiuta il risultato se è maggiore 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 viene chiamato un numero imprecisato di volte, ma nel caso peggiore (n è solo leggermente più grande di una potenza di 2) il numero atteso di chiamate al costruttore dovrebbe essere solo circa 2 volte.

Answer 4

Perché non costruire 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 ?

Answer 5

Compila questo codice F # in una DLL e puoi anche fare riferimento al tuo C#/VB.programmi 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 6

Ecco come lo faccio in una classe denominata Generic_BigInteger disponibili via: 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

Basta usare riduzione modulare

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