Re: Help: Randomizing a List of Numbers

From: Bill Emerson (no_at_one.home)
Date: 07/23/04 

Date: 23 Jul 2004 20:47:35 GMT

In sci.crypt, Tim Smith wrote:
> On 2004-07-22, Bill Emerson <no@one.home> wrote:
>> How do I get the output of /dev/random into rn()? I really don't know how
>> to write that function. Rand() won't do here.
>
> Here's an implementation of rn(A,B) that takes two unsigned longs, A and B,
> and returns an unsigned long in [A,B], for machines where unsigned long is
> a 32 bit number. It uses /dev/urandom, but you can, of course, change it
> to /dev/random. It reads 128*32 bits at a time from /dev/urandom, so as
> to avoid the overhead of reading it each time you need a random number.
> You'll have to stick in something for the two fatal error cases (can't open
> /dev/urandom, and read fails).

[.....]

How does this look, Tim? Getting close?

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

/* timsshuffle.c Tim Smith <reply_in_group@mouse-potato.com> GPL */

main ()

{

        unsigned long rn(unsigned long A, unsigned long B)
        {
            static unsigned long bits[128];
            static int avail = 0;

            if ( avail == 0 )
            {
                int got;
                int fd = open( "/dev/random", O_RDONLY );
                if ( fd < 0 )
                {

                 printf("FATAL ERROR--No input from /dev/random--EXITING");
                 exit (1);

                /* be nice to just put it to sleep for a bit here, right? */

                }
                got = read( fd, bits, sizeof bits );
                close( fd );
                if ( got != sizeof bits )
                {
                    printf("FATAL ERROR--EXITING");
                    exit (1);

                }
                        avail = sizeof bits / sizeof bits[0];
          }

           return (unsigned long)(A + (B-A+1) * (bits[--avail] / 4294967296.0));
          }

    void shuffle( int N, int A[] )
    {
        for ( int i = N-1; i > 0; --i )
        {
            int k = rn(i);
            int tmp = A[i];
            A[i] = A[k];
            A[k] = tmp;
        }
    }
}

I'll have a list of 4000 'random' bytes [from a utility called otp that
uses rand()] to shuffle.

How do I get it into array A[]? Would that be standard in?

$ timsshuffle < list > outputfile # ??

Sorry for being such a clueless newb here. Your help is really
appreciated.

I find this much more interesting than the academic exercises in
K&R. Learning C while putting together something useful is a much
better for me, even if I am only understanding part of what I am
doing at any given time :-)

Bill