Comment générer une valeur aléatoire BigInteger en Java ?

Question

J'ai besoin de générer des nombres entiers aléatoires de taille arbitraire, compris entre 0 (inclus) et n (exclus). Ma première idée était d'appeler nextDouble et multiplier par n, mais une fois que n devient plus grand que 2 53 les résultats ne seraient plus uniformément distribués.

BigInteger dispose du constructeur suivant :

public BigInteger(int numBits, Random rnd)

Construit un BigInteger généré de manière aléatoire, uniformément distribué sur la plage de 0 à (2 numBits - 1), inclusivement.

Comment peut-on l'utiliser pour obtenir une valeur aléatoire comprise entre 0 et n, où n n'est pas une puissance de 2 ?

Answer 1

Utilisez une boucle :

BigInteger randomNumber;
do {
    randomNumber = new BigInteger(upperLimit.bitLength(), randomSource);
} while (randomNumber.compareTo(upperLimit) >= 0);

en moyenne, cela nécessitera moins de deux itérations, et la sélection sera uniforme.

Edit : Si votre RNG est coûteux, vous pouvez limiter le nombre d'itérations de la manière suivante :

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

Avec cette version, il est très improbable que la boucle soit prise plus d'une fois (moins d'une chance sur deux d'être prise). 2^100 c'est-à-dire beaucoup moins que la probabilité que la machine hôte prenne feu spontanément dans la seconde qui suit). D'autre part, la mod() est coûteuse en calcul, donc cette version est probablement plus lente que la précédente, à moins que l'option randomSource L'instance est exceptionnellement lente.

Answer 2

La méthode suivante utilise le BigInteger(int numBits, Random rnd) et rejette le résultat s'il est plus grand que le n spécifié.

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

L'inconvénient de cette méthode est que le constructeur est appelé un nombre indéterminé de fois, mais dans le pire des cas (n est légèrement supérieur à une puissance de 2), le nombre attendu d'appels au constructeur ne devrait être que de 2 fois environ.

Answer 3

L'approche la plus simple (de loin) serait d'utiliser le constructeur spécifié pour générer un nombre aléatoire avec le bon nombre de bits ( floor(log2 n) + 1 ), puis le jette s'il est supérieur à n. Dans le pire des cas (par exemple un nombre dans l'intervalle [0, 2 n + 1) vous allez jeter un peu moins de la moitié des valeurs que vous créez, en moyenne.

Answer 4

Pourquoi ne pas construire un BigInteger aléatoire, puis construire un BigDecimal à partir de celui-ci ? Il existe un constructeur dans BigDecimal : public BigDecimal(BigInteger unscaledVal, int scale) cela semble pertinent ici, non ? Donnez-lui un BigInteger aléatoire et un int d'échelle aléatoire, et vous aurez un BigDecimal aléatoire. Non ?

Answer 5

Compilez ce code F# dans une DLL et vous pourrez également y faire référence dans vos programmes 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