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

[Kai Krakow]

Matti Nykyri <matti.nykyri@×××.fi> schrieb:

> On Jun 29, 2014, at 0:28, Kai Krakow <hurikhan77@×××××.com> wrote:
>>
>> Matti Nykyri <matti.nykyri@×××.fi> schrieb:
>>
>>>> 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.
>>
>> I cannot follow your reasoning here - but I'd like to learn. Actually, I
>> ran this multiple times and never saw long sets of the same character,
>> even no short sets of the same character. The 0 or 1 is always rolled
>> over into the next random addition. I would only get sets of the same
>> character if rand() returned zero multiple times after each other - which
>> wouldn't be really random. ;-)
>
> In your example that isn't true. You will get the same character if 6bit
> random number is 0 or if it is 62! This is what makes the flaw!
>
> You will also get the next character if random number is 1 or 63.
>
> That is why the possibility for 0 and 1 (after modulo 62) is twice as
> large compared to all other values (2-61).

Ah, now I get it.

> By definition random means that the probability for every value should be
> the same. So if you have 62 options and even distribution of probability
> the probability for each of them is 1/62.

Still, the increased probability for single elements should hit different 
elements each time. So for large sets it will distribute - however, I now 
get why it's not completely random by definition.

>> In my tests I counted how ofter new_index > index and new_index < index,
>> and it had a clear bias for the first. So I added swapping of the
>> selected index with offset=0 in the set. Now the characters will be
>> swapped and start to distribute that flaw. The distribution, however,
>> didn't change.
>
> Try counting how of often new_index = index and new_index = (index + 1) %
> 62 and new_index = (index + 2) % 62. With your algorithm the last one
> should be significantly less then the first two in large sample.

I will try that. It looks like a good approach.

-- 
Replies to list only preferred.