Home / Questions / 63801
Accepted
V0LT3RR4
Asked: 2020-04-19 19:23:23 +0800 CST 2020-04-19 19:23:23 +0800 CST

Generate random BigInteger of size exactly K

  • 772

Hello, I would not know how to generate BigInteger of constant nlength . KI found this algorithm here: 

BigInteger r;  
Random rnd = new Random(System.currentTimeMillis());  

do {  
    r = new BigInteger(n.bitLength(), rnd);  
} while (r.compareTo(n) >= 0);

This successfully generates random numbers in a range, but it's not what I'm looking for, what I'm looking for is for example: 

Input   
n = 3  
k = 5  

Output  
12345  
54321  
67854
java

2 Answers

  1. Best Answer

    I suppose that the "constant length K" actually refers to the fact that, written the number in decimal base, the number of digits is K.

    (Never confuse a number -a mathematical entity- with its representation; for example: 251 0xFB 2.51E2 CCLIthey are different representations -in decimal, hexadecimal, scientific and Roman notation- but the number is one and the same in all four cases; they are not four numbers, it is only one written in different ways)

    In this case, if for example K=5 you have to generate in the range 10000 to 99999, that is, between 10^(K-1) and 10^K-1

    The most efficient way to generate random BigIntegers is by directly generating the bits , but that doesn't directly fit a decimal range. (although it can be done, generating uniform values ​​in the range 0 - 2^j-1 for some j such that 2^j >= 10^(k+1) and checking if it falls within our range, if not we retry)

    Another easy option is to directly generate the number as a string and then convert it to BigInteger

    public static BigInteger randBi(int digitosDecimales) {
    Random rand = new Random();
    StringBuilder s = new StringBuilder();
    for( int i = 0; i < digitosDecimales; i++ ) {
        int ir = i == 0 ? rand.nextInt(9) + 1 : rand.nextInt(10);
        s.append((char) ('0' + ir));
    }
    return new BigInteger(s.toString());
}

    Or, something more elegant (I don't know if more efficient) using BigInteger arithmetic:

    public static BigInteger randBi2(int digitosDecimales) {
    Random rand = new Random();
    BigInteger bi=BigInteger.ZERO;
    for( int i = 0; i < digitosDecimales; i++ ) {
        int ir = i == 0 ? rand.nextInt(9) + 1 : rand.nextInt(10);
        bi = bi.multiply(BigInteger.TEN).add(BigInteger.valueOf(ir));
    }
    return bi;
}

    Both can be optimized a bit, if you are going to use them repeatedly: the Random object should be instantiated only once, for example. And in the second implementation, we could pre-set the ten BigInteger 0-9 into an array.

    • 5

  2. You can build a string representation of the random values ​​using the `BigInteger(String val)' constructor:

    import java.math.BigInteger;
import java.security.SecureRandom;

public class BigInt {

    SecureRandom sr = new SecureRandom();

    public static void main(String[] args) {
        int n=4;
        int k=80;
        BigInt bi = new BigInt();
        for (int i = 0;i<n;i++){
            System.out.println(bi.random(k));
        }
    }

    public BigInteger random(int k){
        byte[] ba = new byte[k];
        ba[0] = (byte) (sr.nextInt(9)+49);
        for (int d = 1;d<k;d++){
            ba[d] = (byte) (sr.nextInt(10)+48); 
        }
        return new BigInteger(new String(ba));
    }
}
    • 1