Как сгенерировать случайное значение BigInteger в Java?
Я должен генерировать произвольно большие случайные целые числа в диапазоне 0 (включительно) к (эксклюзивному) n. Моя начальная буква думала, должен был звонить nextDouble и умножьтесь n, но после того как n добирается, чтобы быть больше, чем 253, результаты больше не были бы равномерно распределены.
BigInteger имеет следующего конструктора в наличии:
public BigInteger(int numBits, Random rnd)
Создает случайным образом сгенерированный BigInteger, равномерно распределенный по диапазону 0 к (2numBits - 1), включительно.
Как это может использоваться для получения случайного значения в диапазоне 0 - n, где n не является питанием 2?
5 ответов
Сомневаюсь, что это будет «нишевой проблемой» гораздо дольше: -) Надеемся, что поставщики инструментов изучат необходимые усовершенствования.
-121--2420348- Нельзя использовать <% =% > внутри runat = «server» тэгов, которым является < head > тэгов.
Можно либо изменить его на <% #% > и DataBind в коде позади, либо создать тег ссылки runat = «server» , присвоить ему id и присвоить атрибут из кода позади.
Смотрите этот ответ , который переходит к подробностям.
-121--4998086-Используйте цикл:
BigInteger randomNumber;
do {
randomNumber = new BigInteger(upperLimit.bitLength(), randomSource);
} while (randomNumber.compareTo(upperLimit) >= 0);
в среднем это потребует менее двух итераций, и выбор будет равномерным.
Изменить: Если ваш RNG дорого, вы можете ограничить число итераций следующих путей:
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 не является исключительно медленным.
Самый простой подход (довольно долгий путь) - использовать указанный конструктор для генерации случайного числа с нужным количеством бит ( floor (log2 n) + 1 ), а затем бросить это прочь, если оно больше n. В худшем случае (например, число в диапазоне [0, 2 n + 1) вы выбрасываете в среднем чуть меньше половины созданных вами значений.
Следующий метод использует конструктор BigInteger (int numBits, Random rnd) и отклоняет результат, если он больше указанного п.
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 раза. .
Почему бы не построить случайное BigInteger, а затем построить из него BigDecimal?
В BigDecimal есть конструктор: public BigDecimal (BigInteger unscaledVal, int scale) , который здесь кажется уместным, нет ? Дайте ему случайное значение BigInteger и случайный масштаб int, и вы получите случайное значение BigDecimal. Нет?
Скомпилируйте этот код 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