##### Differences

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

 cs-312:randombigintegers [2015/01/31 11:26]cs312ta cs-312:randombigintegers [2015/01/31 11:59] (current)cs312ta Both sides previous 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 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 3: Line 3: 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) { - BigInteger result; + BigInteger result ​= 0; - ​while (result >= N) { + ​do { - int length = BigInteger.Log(N,​ 2)+1; + int length = (int)Math.Ceiling(BigInteger.Log(N,​ 2)); - int numBytes = (int)Math.ceil(length / 32.0); + int numBytes = (int)Math.Ceiling(length / 8.0); byte[] data = new byte[numBytes];​ byte[] data = new byte[numBytes];​ - ​random.NextBytes(data);​ + ​rand.NextBytes(data);​ result = new BigInteger(data);​ result = new BigInteger(data);​ - } + } while (result >= N || result <= 0); return result; return result; } } Line 35: 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. +