Как создать случайное значение BigInteger в Java?
Мне нужно генерировать произвольно большие случайные целые числа в диапазоне от 0 (включительно) до n (исключая). Моей первоначальной мыслью было позвонить nextDouble и умножить на n, но как только n станет больше 2 53, результаты больше не будут распределяться равномерно.
BigIntegerимеет следующий конструктор:
public BigInteger(int numBits, Random rnd)
Создает случайно сгенерированный BigInteger, равномерно распределенный в диапазоне от 0 до (2 numBits - 1) включительно.
Как это можно использовать для получения случайного значения в диапазоне 0 - n, где n не является степенью 2?
9 ответов
Используйте цикл:
BigInteger randomNumber;
do {
randomNumber = new BigInteger(upperLimit.bitLength(), randomSource);
} while (randomNumber.compareTo(upperLimit) >= 0);
в среднем для этого потребуется менее двух итераций, и выбор будет равномерным.
Изменить: Если ваш ГСЧ дорог, вы можете ограничить количество итераций следующим образом:
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'
В этой версии крайне маловероятно, что цикл будет выполнен более одного раза (менее одного шанса в 2 ^ 100, т. Е. Намного меньше, чем вероятность того, что хост-машина самопроизвольно загорится в следующую следующую секунду). С другой стороны, mod() операция в вычислительном отношении дорогая, поэтому эта версия, вероятно, медленнее, чем предыдущая, если только randomSource Экземпляр исключительно медленный.
Следующий метод использует BigInteger(int numBits, Random rnd) конструктор и отклоняет результат, если он больше указанного n.
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;
}
Недостаток этого заключается в том, что конструктор вызывается неопределенное количество раз, но в худшем случае (n чуть больше, чем степень 2) ожидаемое количество обращений к конструктору должно составлять только около 2 раз.
Самый простой подход (довольно длинный путь) состоит в том, чтобы использовать указанный конструктор для генерации случайного числа с правильным количеством битов (floor(log2 n) + 1), а затем выбросить, если оно больше n. В худшем из возможных случаев (например, число в диапазоне [0, 2n + 1) вы в среднем отбрасываете чуть меньше половины созданных вами значений.
Для тех, кто все еще задает этот вопрос и ищет способ генерировать произвольно большие случайные числа BigInteger в диапазоне положительных целых чисел, вот что я придумал. Этот генератор случайных чисел работает, не перебирая кучу чисел, пока одно из них не будет соответствовать диапазону. Вместо этого он будет генерировать случайное число напрямую, которое будет соответствовать заданному диапазону.
private static BigInteger RandomBigInteger(BigInteger rangeStart, BigInteger rangeEnd){
Random rand = new Random();
int scale = rangeEnd.toString().length();
String generated = "";
for(int i = 0; i < rangeEnd.toString().length(); i++){
generated += rand.nextInt(10);
}
BigDecimal inputRangeStart = new BigDecimal("0").setScale(scale, RoundingMode.FLOOR);
BigDecimal inputRangeEnd = new BigDecimal(String.format("%0" + (rangeEnd.toString().length()) + "d", 0).replace('0', '9')).setScale(scale, RoundingMode.FLOOR);
BigDecimal outputRangeStart = new BigDecimal(rangeStart).setScale(scale, RoundingMode.FLOOR);
BigDecimal outputRangeEnd = new BigDecimal(rangeEnd).add(new BigDecimal("1")).setScale(scale, RoundingMode.FLOOR); //Adds one to the output range to correct rounding
//Calculates: (generated - inputRangeStart) / (inputRangeEnd - inputRangeStart) * (outputRangeEnd - outputRangeStart) + outputRangeStart
BigDecimal bd1 = new BigDecimal(new BigInteger(generated)).setScale(scale, RoundingMode.FLOOR).subtract(inputRangeStart);
BigDecimal bd2 = inputRangeEnd.subtract(inputRangeStart);
BigDecimal bd3 = bd1.divide(bd2, RoundingMode.FLOOR);
BigDecimal bd4 = outputRangeEnd.subtract(outputRangeStart);
BigDecimal bd5 = bd3.multiply(bd4);
BigDecimal bd6 = bd5.add(outputRangeStart);
BigInteger returnInteger = bd6.setScale(0, RoundingMode.FLOOR).toBigInteger();
returnInteger = (returnInteger.compareTo(rangeEnd) > 0 ? rangeEnd : returnInteger); //Converts number to the end of output range if it's over it. This is to correct rounding.
return returnInteger;
}
Как это работает?
Сначала он генерирует строку со случайными числами той же длины, что и максимальный диапазон. Например: с заданным диапазоном 10-1000 он будет генерировать некоторое число от 0000 до 9999 в виде строки.
Затем он создает BigDecimals для представления максимально возможного значения (9999 в предыдущем примере) и минимального значения (0) и преобразует параметр диапазона BigIntegers в BigDecimals . Также на этом шаге к заданному максимальному значению диапазона добавляется 1, чтобы исправить ошибки округления на следующем шаге.
Затем с помощью этой формулы сгенерированное случайное число сопоставляется с заданным диапазоном:
(generated - inputRangeStart) / (inputRangeEnd - inputRangeStart) * (outputRangeEnd - outputRangeStart) + outputRangeStart
После этого он выполнит последнюю проверку, соответствует ли отображенное число заданному диапазону, и установит его на максимум заданного диапазона, если это не так. Это делается для того, чтобы исправить ошибки округления.
Почему бы не создать случайный BigInteger, а затем создать из него BigDecimal? В BigDecimal есть конструктор: public BigDecimal(BigInteger unscaledVal, int scale) это кажется уместным здесь, нет? Дайте ему случайный BigInteger и случайный масштаб int, и вы получите случайный BigDecimal. Нет?
Вот как я это делаю в классе Generic_BigInteger, доступном через: Веб-страница общего исходного кода Энди Тернера
/**
* 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;
}
Просто используйте модульное сокращение
new BigInteger(n.bitLength(), new SecureRandom()).mod(n)
Скомпилируйте этот код F# в DLL, и вы также можете ссылаться на него в своих программах на 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
Если мы хотим сгенерировать случайные 70 цифр большого числа, мы можем сгенерировать массив байтов [70] и заполнить его случайными числами от 0 до 9 и добавить 48, чтобы сделать символы цифр и преобразовать символы цифр в большие числа
public BigInteger RandomBigInteger(int digits_len) {
Random rnd = new Random();
byte[]num = new byte[digits_len];
if(digits_len>1){//first digit must not be 0 because 0555 will be 555
num[0]=(byte)((((int)(rnd.nextFloat()*10))%9)+1+48);//([*10 means] rnd 0-9),([%9 means] 0-8 , [+1 means] 1-9) ,([+48 means] 0->48,1->49)
for(int i=1;i<num.length;i++){ num[i]=(byte)((((int)(rnd.nextFloat()*10))%10)+48); }//([*10 means] rnd 0-9),([%10 means] 0-9 because rnd may be 1.000*10=10) ,([+48 means] 0->48,1->49)
}else{//digits_len = 1 , it can be 0-9
num[0]=(byte)((((int)(rnd.nextFloat()*10))%10)+48);//([*10 means] rnd 0-9),([%10 means] 0-9 because rnd may be 1.000*10=10) ,([+48 means] 0->48,1->49)
}
return new BigInteger(new String(num,StandardCharsets.ISO_8859_1),10);//convert the digit chars to biginteger
}
BigInteger num = RandomBigInteger(5);//num = 12345