Re: [oc] Again! modulo arithmetic hardware

["Jim Dempsey" <tapedisk@ameritech.net>]

----- Original Message -----
From: "Marko Mlinar" <markom@opencores.org>
To: <cores@opencores.org>
Sent: Monday, March 11, 2002 1:29 AM
Subject: Re: [oc] Again! modulo arithmetic hardware


> just some thoughts about these simple solutions:
>
> > 1) Generate a larger binary random number [0:255] (8 bits).
> > take any 4 bits of this number to produce a random number
> > between 0:15. Discard any number above 9 (i.e. regenerate
> > another random number). Only when you discard will you
> > need to regenerate. To reduce regeneration somewhat you could
> > perhaps take the low 4 bits for your first pick. If that fails
> > take the high 4 bits. If that fails then regenerate new random
> > number.
> this may take forever to find a random number...
> maybe you can search for near-random number, if none
> of nibbles are ok, then take a number of 0..7
>

You are generating random numbers not finding random numbers.
The problem as I understood it was the user had a time constraint
in producing a sequence of random numbers in the range of 0:9.
The user could not afford the time to calculate MOD(RND(), 10)
or some thing like that. My understanding was the time for the MOD
function was too long.

> > 2) Generate a random number of 9 bits (or larger) in width. Use a
> > logic core that inputs of 9 bits and outputs the count of bits
> > set.
> I am not an expert in random math, but I would say this new distribution
> is not random anymore.
>
It is as random as the original distribution.

The above is to be performed in logic but let's examine this as a C program
Assume you have a means of obtaining an random number getRandomNumber()
Assume you have a means of returning the remainder of a division, a mod
function.

Example 1 - slow way

    // generate 1024 random digits in range of 0:9
    for(i=0; i<1024; ++1)
        output(mod(getRandomNumber(), 10));

Example 2 - faster way

    i = 0;
    while(1)
    {
        unsigned char twoNibles = getRandomNumber();
        if((value = (twoNibles & 0x0F) <= 9)
        {
            output(value);
            if(++i >= 1024)
                break;
        }
        if((value = ((twoNibles >> 4) & 0x0F) <= 9)
        {
            output(value);
            if(++i >= 1024)
                break;
        }
    }

Jim


--
To unsubscribe from cores mailing list please visit http://www.opencores.org/mailinglists.shtml