Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
cs-312:randombigintegers [2015/01/31 11:26]
cs312ta
cs-312:randombigintegers [2015/01/31 11:59] (current)
cs312ta
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>​ <​pre>​random_number %= N;</​pre>​
 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 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 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);​ +
-+
-</code> +
-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.1422728790.txt.gz · Last modified: 2015/01/31 11:26 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