**This is an old revision of the document!**


Random Big Integers

C# does not provide a way to create a random BigInteger, so we have to create our own way by combining multiple random 32 bit integers.

Best Solution

static Random rand = new Random();

// returns a evenly distributed random BigInteger from 1 to N.
BigInteger randomBigInteger(BigInteger N) {
  BigInteger result = 0;
  do {
    int length = (int)Math.Ceiling(BigInteger.Log(N, 2));
    int numBytes = (int)Math.Ceiling(length / 8.0);
    byte[] data = new byte[numBytes];
    rand.NextBytes(data);
    result = new BigInteger(data);
  } while (result >= N || result < 0);
  return result;
}

Old Approach

The first step is to determine the length of the max value you want (in bits). This can be done using the following code. 1)

length = BigInteger.Log(N, 2)+1

Then we allocate a new big integer to hold the random number and generate enough random 32 bit integers to create a random number of at least length bits. We use the bit left bit shift operator to move over the random bits from the last iteration.

BigInteger random_number = 0;
for (int i = 0; i < length/31 + 1; i++)
    random_number = (random_number << 31) + rand.Next();

This likely creates a number much larger than N. For example if N is 40 bits, the loop would run 2 times and we would get a random 62 bit integer. So we need to shrink the integer so it's no bigger than N.

This is the easiest way, simply mod the random number by N as follows.

random_number %= N;

This however can create uneven distributions if N and the largest value of random_number are similar 2)

Alternative Approach #2 - retry until number is less than N

Put your code to generate the random BigInteger in a loop and continue generating random BigIntegers until the random BigInteger is less than N.

BigInteger random_number = CreateRandomBigInteger(N);
while (N > random_number) {
    random_number = CreateRandomBigInteger(N);
}

This will ensure that your random number distribution is even but could take a very long time with this code if N is a 33 bit integer.

cs-312/randombigintegers.1422730039.txt.gz · Last modified: 2015/01/31 11:47 by cs312ta
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0