Re: [gentoo-user] Re: OT: Mapping random numbers (PRNG)

[Matti Nykyri]

On Jun 28, 2014, at 0:13, Matti Nykyri <matti.nykyri@×××.fi> wrote:

>> On Jun 27, 2014, at 0:00, Kai Krakow <hurikhan77@×××××.com> wrote:
>>
>> Matti Nykyri <Matti.Nykyri@×××.fi> schrieb:
>>
>>> If you are looking a mathematically perfect solution there is a simple
>>> one even if your list is not in the power of 2! Take 6 bits at a time of
>>> the random data. If the result is 62 or 63 you will discard the data and
>>> get the next 6 bits. This selectively modifies the random data but keeps
>>> the probabilities in correct balance. Now the probability for index of
>>> 0-61 is 1/62 because the probability to get 62-63 out of 64 if 0.
>>
>> Why not do just something like this?
>>
>> index = 0;
>> while (true) {
>> index = (index + get_6bit_random()) % 62;
>> output << char_array[index];
>> }
>>
>> Done, no bits wasted. Should have perfect distribution also. We also don't
>> have to throw away random data just to stay within unaligned boundaries. The
>> unalignment is being taken over into the next loop so the "error" corrects
>> itself over time (it becomes distributed over the whole set).
>
> Distribution will not be perfect. The same original problem persists. Probability for index 0 to 1 will be 2/64 and for 2 to 61 it will be 1/64. Now the addition changes this so that index 0 to 1 reflects to previous character and not the original index.
>
> The distribution of like 10GB of data should be quite even but not on a small scale. The next char will depend on previous char. It is 100% more likely that the next char is the same or one index above the previous char then any of the other ones in the series. So it is likely that you will have long sets of same character.
>
> Random means that for next char the probability is always even, 1/62. And like mentioned in Dilbert it is impossible to say that something is random but possible to say that it isn't.
>
> If wasting 6bit of data seems large, do this:
>
> index = get_6bit_random();
> while (index > 61) {
> index <<= 1;
> index |= get_1bit_random();
> index &= 0x3F;
> }
> return index;
>
> It will waste 1 bit at a time until result is less than 62. This will slightly change probabilities though :/

Sorry this example is really flawed :( If next6bit is over 61 there are only two possible values for it: 62 or 63 -> that is 0x3E and 0x3F. So you see that only one bit changes. But that bit is random! So least significant bit is random and does not need to be discarded :)

index = get_6bit_random();
while (index > 61) {
    index <<= 5;
    index |= get_5bit_random();
    index &= 0x3F;
}
return index;