How to get integer between two values from stream of bits?

Question

I have a project which uses php's mt_rand() to generate different random integers but I have recently gained access to a stream of real random bits. I am having trouble figuring out how to create a function similar to mt_rand(), where I can get a random integer between two values, from my stream of bits. How can I achieve this?

To clarify; are you saying you want to take a stream of random bits, and use them to generate a stream of random integers between `min` and `max`? — Oliver Charlesworth, Jun 05 '12 at 12:05
Is it a stream of just 0s and 1s, or is it a stream of numbers? — jprofitt, Jun 05 '12 at 12:12
Oli, I just want to create one random integer at a time, between a specified minimum and maximum value, using a stream of bits (using as few or as many of those bits as necessary). Basically I want to replicate the function of mt_rand() while using my random bits instead of the psudorandom algorithm mt_rand() uses. jprofitt, its a stream of 0s and 1s. — Tesla, Jun 05 '12 at 12:13
clarify; using this stream of bits as a random seed somehow? — , Jun 05 '12 at 12:36
@vlzvl nope, not as a random seed. The bits are already random, so I basically just want to convert the bits into an integer between a min and max, using as many bits from the stream as necessary. — Tesla, Jun 05 '12 at 13:09
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., Feb 14 '23 at 23:15

Ja͢ck · Answer 1 · 2012-06-06T15:29:20.723

1

I would just read PHP_INT_SIZE * 8 bits and squash the resulting number in the range you need:

function squash($nr, $min, $max)
{
    return $min + $nr % ($max - $min);
}

Another way:

function squash($nr, $min, $max)
{
    return $min + round($nr / PHP_INT_MAX * ($max - $min));
}

This just occurred to me, why not just use your random stream and push it into mt_srand():

function squash($nr, $min, $max)
{
    mt_srand($nr);
    return mt_rand($min, $max);
}

edited Jun 06 '12 at 15:29

answered Jun 05 '12 at 12:47

Ja͢ck

170,779
38
263
309

This looks right, it would get a number in the correct range, I'm just thinking if this affects the randomness in anyway, I dont think it does, which is good. I might run a quick test to confirm. – Tesla Jun 05 '12 at 13:11
@user1437296 that's what I'm wondering about too; I hope someone else can prove me wrong :) – Ja͢ck Jun 05 '12 at 13:15
thinking about it, it would affect the randomness. Say for a simplified example, we want an integer between 0 and 99, and we only read 7 bits. So we can get a value between 0 and 127. Squashing this, the numbers 1-28 can come up from two different random numbers, whereas 0-99 can only come up from 1 random number. – Tesla Jun 06 '12 at 06:07
@user1437296 well, my answer states that `PHP_INT_SIZE * 8` bits must be read. – Ja͢ck Jun 06 '12 at 06:15
it would be the same result. For example if the bits read will produce an integer between 0 and 4,294,967,295, and we tried to squash that to an integer between 0 and 999,999,999, there will be 4 numbers that squash to some numbers, and 5 that squash to others. This affects the chance of getting a certain integer. – Tesla Jun 06 '12 at 06:41
@user1437296 I see, this would happen with bigger ranges .. the `mod` starts to favour certain numbers ;-) updated the answer to add another way without roll-over – Ja͢ck Jun 06 '12 at 06:51
not sure I understand the new way, it doesnt seem to produce a number between `min` and `max` – Tesla Jun 06 '12 at 14:40
@user1437296 well it should; unless `$nr > PHP_INT_MAX` .. perhaps you should read `PHP_INT_SIZE * 8 - 1` bits instead :) – Ja͢ck Jun 06 '12 at 14:44
I misread and thought you put `PHP_INT_SIZE` instead of `PHP_INT_MAX`. So yes it does produce numbers in the correct range, but the rounding would still result in some numbers being favoured over others. – Tesla Jun 06 '12 at 15:18
@user1437296 But how would that be much different from a standard RNG when the range is small? In any case, just had a funny idea .. updated the answer with another solution. – Ja͢ck Jun 06 '12 at 15:29

Tesla · Accepted Answer · 2012-08-08T03:16:28.383

I have come up with a method but not sure if its the most efficient way in terms of bits used (code is untested, just demonstrating theory):

function RandomInteger($min, $max)
{
    $range = ($max - $min) + 1;
    $bitsNeeded = ceil( log($range, 2) );
    $number = ReadBitsAndConvertToInteger($bitsNeeded);
    if ($number < $range)
        return $number + $min;
    else if ($number > $range)
        return RandomInteger($min, $max);
}

As you can see, there will be a chance the function is repeated, which means more bits will be used, thats why I'm not sure if its the most efficent way, in terms of bits used, to do it.

Pr(repeat) = (2^bitsNeeded - range) / (2^bitsNeeded)

Therefore, 0 < Pr(repeat) < 0.5

So in the worst case that the chance of having to repeat is almost 0.5, it starts to get quite unlikely that it would need to be repeated more than 10 or so times, with the average being just under 2 times. Obviously at lower chances of having to repeat , these numbers get lower.

You should use `if ($number < range)` and return `$number + $min`, since `$number` can be 0 (legitimately!). Apart from that, if your true random source is uniformly distributed, this is the one option that actually produces a uniform distribution in the range from `$min` to `$max` (inclusive). You can use a method using fewer bits on average, but as far as I can see, all those introduce a bias, i.e. some numbers in your range are more probable to occur than others. — Daniel Fischer, Aug 04 '12 at 19:49
@DanielFischer, thanks for pointing out the small mistake with regard to $number, I have edited my answer accordingly. — Tesla, Aug 08 '12 at 03:17

How to get integer between two values from stream of bits?

2 Answers2

Linked