0 (含む) から n (含まない) の範囲で任意に大きなランダムな整数を生成する必要があります。最初は n を掛けて n を掛けようと考えていましたが、n が 2 53nextDoubleよりも大きくなると、結果は一様に分布しなくなります。
BigInteger次のコンストラクタが利用可能です。
public BigInteger(int numBits, Random rnd)
0 から (2 numBits - 1)までの範囲に均一に分散された、ランダムに生成された BigInteger を構築します。
n が 2 の累乗でない場合、これを使用して 0 から n の範囲のランダムな値を取得するにはどうすればよいでしょうか?
ループを使用します。
BigInteger randomNumber;
do {
randomNumber = new BigInteger(upperLimit.bitLength(), randomSource);
} while (randomNumber.compareTo(upperLimit) >= 0);
平均すると、これには2回未満の反復が必要であり、選択は均一になります。
編集： 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で1回未満、つまり、ホストマシンが次の1秒で自発的に発火する確率よりもはるかに低い）。一方、操作は計算コストがかかるため、インスタンスが非常に遅い場合を除い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) + 1nより大きい場合はそれを破棄することです。考えられる最悪の場合（たとえば、[0、2 n + 1の範囲の数値）では、平均して、作成した値の半分未満を破棄します。
ランダムな BigInteger を構築してから、そこから BigDecimal を構築してみませんか? BigDecimal にはコンストラクターがありpublic BigDecimal(BigInteger unscaledVal, int scale)ます。ここでは関連しているようです。ランダムな BigInteger とランダムなスケール int を与えると、ランダムな BigDecimal が得られます。いいえ ？
まだこの質問をしていて、正の整数範囲内で任意に大きなランダムなBigIntegersを生成する方法を探している人のために、これが私が思いついたものです。この乱数発生器は、範囲に収まるまで多数の数値を試行せずに機能します。代わりに、指定された範囲に適合する乱数を直接生成します。
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 の間の数値がStringとして生成されます。
次に、可能な最大値 (前の例では 9999) と最小値 (0) を表すBigDecimalsを作成し、範囲パラメーターBigIntegersをBigDecimalsに変換します。また、このステップでは、次のステップで丸め誤差を修正するために、指定された範囲の最大値に 1 が追加されます。
次に、この式を使用して、生成された乱数が指定された範囲にマップされます。
(generated - inputRangeStart) / (inputRangeEnd - inputRangeStart) * (outputRangeEnd - outputRangeStart) + outputRangeStart
その後、マップされた数値が指定された範囲に適合するかどうかの最後のチェックを行い、適合しない場合は指定された範囲の最大値に設定します。これは、丸め誤差を修正するために行われます。
以下から入手できる Generic_BigInteger というクラスでそれを行う方法は次のとおりです。 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;
}
この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