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

[Matti Nykyri]

On Fri, Jun 06, 2014 at 08:39:28PM +0200, meino.cramer@×××.de wrote:
> Canek Peláez Valdés <caneko@×××××.com> [14-06-06 17:36]:
> > On Thu, Jun 5, 2014 at 9:56 PM,  <meino.cramer@×××.de> wrote:
> > > Hi,
> > >
> > > I am experimenting with the C code of the ISAAC pseudo random number generator
> > > (http://burtleburtle.net/bob/rand/isaacafa.html).
> > >
> > > Currently the implementation creates (on my embedded linux) 32 bit
> > > hexadecimal output.
> >
> > So it's a 32 bit integer.
> >
> > > From this I want to create random numbers in the range of [a-Za-z0-9]
> > > *without violating randomness* and (if possible) without throwing
> > > away bits of the output.
> >
> > You mean *characters* int the range [A-Za-z0-9]?
> >
> > > How can I do this mathemtically (in concern of the quality of output)
> > > correct?
> >
> > The easiest thing to do would be:
> >
> > -------------------------------------------------------------------------------
> > #include <time.h>
> > #include <stdio.h>
> > #include <stdlib.h>
> >
> > #define N (26+26+10)
> >
> > static char S[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
> > 'K', 'L', 'M',
> >                     'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W',
> > 'X', 'Y', 'Z',
> >                     'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
> > 'k', 'l', 'm',
> >                     'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w',
> > 'x', 'y', 'z',
> >                     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
> >
> > int
> > next_character()
> > {
> >         // Use the correct call for ISAAC instead of rand()
> >         unsigned int idx = rand() % N;
> >         return S[idx];
> > }
> >
> > int
> > main(int argc, char* argv[])
> > {
> >         // Use the correct call for initializing the ISAAC seed
> >         srand((unsigned int)time(NULL));
> >         for (int i = 0; i < 20; i++) // --std=c99
> >                 printf("%c\n", next_character());
> >         return 0;
> > }
> > -------------------------------------------------------------------------------
> >
> > If the ISAAC RNG has a good distribution, then the next_character()
> > function will give a good distribution among the set [A-Za-z0-9].
> >
> > Unless I missunderstood what you meant with "create random numbers in
> > the range of [a-Za-z0-9]".
> >
> > Regards.
> > --
> > Canek Peláez Valdés
> > Profesor de asignatura, Facultad de Ciencias
> > Universidad Nacional Autónoma de México
> >
>
> Hi,
>
> Thank you very much for the input! :)
>
> I have a question about the algorithm:
> Suppose rand() has an equal distribution of numbers and furthermore
> one has a count of 2^32 random numbers listed in numerical sort
> order.
> In this list each number would appear (nearly) with the same count: 1
>
> To get an better imagination of that...suppose the rand() would only
> return numbers in the range of 1...12 and the alphabet has only 8
> characters (as 2^32 is not devideable by 62)
>
> rand():
> 1 2 3 4 5 6 7 8 9 10 11 12
>
> rand()%N : rand()%7
> 1 2 3 4 5 6 7 0 1  2  3  4
>
> or in other words: An even distribution of numbers of rand()
> would result in a unevenly distributed sequence of characters...or?
> This would break the quality of ISAACs output.
>
> I am sure I did something wrong here...but where is the logic trap?
>

This is the thing I explained in my message.

-- 
-Matti