Nice programing

Java에서 임의의 BigInteger 값을 생성하는 방법은 무엇입니까?

nicepro 2020. 11. 28. 12:26
반응형

Java에서 임의의 BigInteger 값을 생성하는 방법은 무엇입니까?


0 (포함)에서 n (배타적)까지의 범위에서 임의로 큰 임의의 정수를 생성해야합니다. 내 초기 생각은 nextDoublen 을 호출 하고 곱하는 것이었지만 n이 2 53 보다 커지면 결과가 더 이상 균일하게 분포되지 않습니다.

BigInteger 다음 생성자를 사용할 수 있습니다.

public BigInteger(int numBits, Random rnd)

0에서 (2 numBits -1) 범위에 걸쳐 균일하게 분포 된 무작위로 생성 된 BigInteger를 생성 합니다.

0-n 범위에서 임의의 값을 얻는 데 어떻게 사용할 수 있습니까? 여기서 n은 2의 거듭 제곱이 아닙니다.


루프 사용 :

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인스턴스가 예외적으로 느리지 않는 한이 버전은 이전 버전보다 느릴 수 있습니다.


다음 메서드는 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, 2 n + 1 범위의 숫자 )는 평균적으로 생성 한 값의 절반 이하를 버릴 것입니다.


무작위 BigInteger를 생성 한 다음 그로부터 BigDecimal을 빌드하지 않는 이유는 무엇입니까? BigDecimal에 생성자가 있습니다. public BigDecimal(BigInteger unscaledVal, int scale)여기에 관련이있는 것 같습니다. 임의의 BigInteger와 임의의 scale int를 지정하면 임의의 BigDecimal이 생깁니다. 아니 ?


다음은 Generic_BigInteger라는 클래스에서 수행하는 방법입니다. Andy Turner의 일반 소스 코드 웹 페이지

/**
 * 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)

Compile this F# code into a DLL and you can also reference it in your C# / VB.NET programs

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

참고URL : https://stackoverflow.com/questions/2290057/how-to-generate-a-random-biginteger-value-in-java

반응형