##### Differences

This shows you the differences between two versions of the page.

 cs-312:randombigintegers [2015/01/24 12:02]cs312ta created cs-312:randombigintegers [2015/01/31 11:59] (current)cs312ta 2015/01/31 11:59 cs312ta 2015/01/31 11:56 cs312ta 2015/01/31 11:47 cs312ta 2015/01/31 11:46 cs312ta 2015/01/31 11:26 cs312ta 2015/01/26 15:21 ringger 2015/01/24 12:02 cs312ta created Next revision Previous revision 2015/01/31 11:59 cs312ta 2015/01/31 11:56 cs312ta 2015/01/31 11:47 cs312ta 2015/01/31 11:46 cs312ta 2015/01/31 11:26 cs312ta 2015/01/26 15:21 ringger 2015/01/24 12:02 cs312ta created Line 1: Line 1: + = 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. ​ 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 == + == Best Solution == <​code>​ <​code>​ + static Random rand = new Random(); + // returns a evenly distributed random BigInteger from 1 to N. // returns a evenly distributed random BigInteger from 1 to N. BigInteger randomBigInteger(BigInteger N) { BigInteger randomBigInteger(BigInteger N) { - ​if (N < Int32.MaxValue) ​{ + ​BigInteger result = 0; - ​return rand.Next((int)N); + do { - } else { + ​int length = (int)Math.Ceiling(BigInteger.Log(N,​ 2)); - ​return ​rand.Next() + (randomBigInteger(N >> 31) << 31); + 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; } } ​ Line 29: Line 37: <​pre>​random_number %= N;​ <​pre>​random_number %= N;​ This however can create uneven distributions if N and the largest value of random_number are similar ((http://​jsfiddle.net/​trevordixon/​ZvquF/​5/​)) This however can create uneven distributions if N and the largest value of random_number are similar ((http://​jsfiddle.net/​trevordixon/​ZvquF/​5/​)) - + == Interactive Visualization / Example in C# == - == Alternative Approach ​#2 - retry until number is less than N == + We have made a program that has both methods of generating BigIntegers ​and draws the distribution of the randomly generated numbers. In the program you can select "​mod"​ to see BigIntegers generated by simply modding, and then by selecting "​repeat"​ you will see the distribution when the random ​code is repeated until a number in the desired range is obtained. It also shows you the time required to generate all the numbers so you can get a sense for the difference in performance. - Put your code to generate the random BigInteger in a loop and continue ​generating ​random ​BigIntegers ​until the random ​BigInteger ​is less than N. + {{:​cs-312:​randombigintegers.zip|RandomBigIntegers Project}} - <​code>​ + [http://wiki.cs.byu.edu/​_media/​cs-312/​randombigintegers.zip Download RandomBigIntegers C# Project] - 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. +