3

I have a source of random bits that I would like to massage into integers of various sizes, roughly correlating with the size of popular dice (1-4, 1-6, etc.)

The code I am writing is PHP, so a response in that language is ideal. However, an algorithmic generic response would be totally fine as well.

I would prefer an answer more sophisticated than simply seeding PHP's random() function with chunks of my random data.

Winfield Trail
  • 5,535
  • 2
  • 27
  • 43
  • Do you have an indefinite number of random bits at your disposal? – Oliver Charlesworth May 24 '11 at 23:27
  • 2
    And why is using your random data as a seed not acceptable? – Oliver Charlesworth May 24 '11 at 23:28
  • I would hazard a guess that starting with something (even in psuedocode), and then asking if it is valid or not, would probably be a more effective approach. :) – Jared Farrish May 24 '11 at 23:31
  • @Oli, in order: Yes, I have for most intents and purposes an unlimited amount of randomness. Enough to last forever. Second, because I am given to understand that seeding the PHP RNG will yield a number that is made by mashing my high-quality randomness up with crappy randomness from the system time and other deterministic factors. – Winfield Trail May 24 '11 at 23:32
  • If your initial seed is truly random, then the resulting sequence from the RNG will be truly random. (Basically, if `y = f(x)` and `x` is random, then `y` must also be random.) However, that's not to say that future values cannot be predicted from past values... – Oliver Charlesworth May 24 '11 at 23:36
  • If you want random numbers and do not want to waste bits see my answer to this question: http://stackoverflow.com/questions/6046918/how-to-generate-a-random-integer-in-the-range-0-n-from-a-stream-of-random-bits – soid May 10 '12 at 14:51
  • Does this answer your question? [How to generate a random integer in the range \[0,n\] from a stream of random bits without wasting bits?](https://stackoverflow.com/questions/6046918/how-to-generate-a-random-integer-in-the-range-0-n-from-a-stream-of-random-bits) – Peter O. Apr 04 '22 at 14:43

1 Answers1

4

If you have an arbitrary number of bits available, you might choose to use a rejection method, along the lines of Java's Random.nextInt(int). The pseudocode taken from there is:

public int nextInt(int n) {
     if (n<=0)
         new IllegalArgumentException("n must be positive");

     if ((n & -n) == n)  // i.e., n is a power of 2
         return (int)((n * (long)next(31)) >> 31);

     int bits, val;
     do {
         bits = next(31);
         val = bits % n;
     } while(bits - val + (n-1) < 0);
     return val;
 }

next() is a function that returns a specified number of random bits, concatenated into an int. You could replace this with your random bit source.

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
  • Hm, this could potentially work. I could even spool the rejected bits onto the back of the randomness "stack" to conserve if need be. – Winfield Trail May 24 '11 at 23:36
  • Will accept your answer if experimentation validates your suggestion. :) – Winfield Trail May 25 '11 at 02:12
  • Although this seems to be the common algorithm it will not give exactly random numbers. The error increases as n approaches the maximum integer. – soid May 10 '12 at 14:58
  • @soid: What do you mean by "exactly random", and why do you believe the error will increase? – Oliver Charlesworth May 10 '12 at 14:58
  • If I understand this correctly the % (modulo) operator will give the remainder after dividing bits by n. Since bits is not exactly divisible by n, at least for some values of n, there is more chance of generating some values than others because there is a part at the top where bits cannot generate a complete range of n. This error is very small when the number of times n can divide into bits is large. So for small values of n you would not notice it. I am not sure I have explained that very well. – soid May 10 '12 at 15:18
  • 1
    @soid: This is why it's in a while loop that performs rejection. This ensures a uniform distribution. – Oliver Charlesworth May 10 '12 at 15:19
  • Ah, got it now, you are right. They take the part off the bottom rather than the top of the range that bits can have. Thanks. – soid May 10 '12 at 15:29
  • I agree it is true random, but I still do not understand the algorithm. What happens at the top end of n? Does it retry a ridiculous number of times in the loop when it is near the top? – soid May 10 '12 at 15:38
  • @soid: The worst case is n=2^30+1, which gives a rejection ratio of 0.5. – Oliver Charlesworth May 10 '12 at 15:43