**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.

Recursive Solution

// returns a evenly distributed random BigInteger from 1 to N.
BigInteger randomBigInteger(BigInteger N) {
  if (N < Int32.MaxValue) {
    return rand.Next((int)N);
  } else {
    return rand.Next() + (randomBigInteger(N >> 31) << 31);
  }
}

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.1422310896.txt.gz · Last modified: 2015/01/26 15:21 by ringger
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