How to generate random numbers that doesnot repeat

D

Deepu

Guest
Hi All,

How can i generate random numbers from 0 to 1000 and make sure the
number doesnot repeat.

I tried with:

random_number = ($random % (1000));

random_number = ($urandom % (1000));

Thanks!
 
Deepu wrote:

How can i generate random numbers from 0 to 1000 and make sure the
number doesnot repeat.
Click to expand...
One option is to use a maximal length LFSR (1024) and discard the values
above 1000. You'll also have to map one of the discarded values to 0.

Of course, your sequence will be the same each time, with a different
start point if you use a "random" seed.

Regards,

--
Mark McDougall, Engineer
Virtual Logic Pty Ltd, <http://www.vl.com.au>
21-25 King St, Rockdale, 2216
Ph: +612-9599-3255 Fax: +612-9599-3266
 
You can invert the output of the LFSR to get the all 0's case.

JTW

"Mark McDougall" <markm@vl.com.au> wrote in message
news:47e1b3b5$1@dnews.tpgi.com.au...
Deepu wrote:

How can i generate random numbers from 0 to 1000 and make sure the
number doesnot repeat.

One option is to use a maximal length LFSR (1024) and discard the values
above 1000. You'll also have to map one of the discarded values to 0.

Of course, your sequence will be the same each time, with a different
start point if you use a "random" seed.

Regards,

--
Mark McDougall, Engineer
Virtual Logic Pty Ltd, <http://www.vl.com.au
21-25 King St, Rockdale, 2216
Ph: +612-9599-3255 Fax: +612-9599-3266
Click to expand...
 
On Mar 19, 8:32 pm, Deepu <pradeep...@gmail.com> wrote:
Hi All,

How can i generate random numbers from 0 to 1000 and make sure the
number doesnot repeat.
Click to expand...
The obvious approach would be to create a 1001-element array
containing the values 0 to 1000, and then shuffle it into a random
order. Then read out the values one at a time.
 
The obvious approach would be to create a 1001-element array
containing the values 0 to 1000, and then shuffle it into a random
order.  Then read out the values one at a time.
Click to expand...
Can you give some ideas on how shuffling can be done.

Thanks
 
jtw wrote:

You can invert the output of the LFSR to get the all 0's case.
Click to expand...
Good thinking 99! ;)

Regards,

--
Mark McDougall, Engineer
Virtual Logic Pty Ltd, <http://www.vl.com.au>
21-25 King St, Rockdale, 2216
Ph: +612-9599-3255 Fax: +612-9599-3266
 
On Wed, 19 Mar 2008 19:28:18 -0700 (PDT), Deepu <pradeep.bg@gmail.com>
wrote:

The obvious approach would be to create a 1001-element array
containing the values 0 to 1000, and then shuffle it into a random
order.  Then read out the values one at a time.

Can you give some ideas on how shuffling can be done.
Click to expand...
For each element in the array, randomly pick one of the locations
at location or later in the array. Swap element with the
randomly-chosen element. Then move on to the next .

parameter MAX = 1000;
integer i,j,k;
integer seed = 42; // for randomization
integer shuffled[0:MAX];

// prepare non-shuffled array
for (i=0; i<=MAX; i=i+1) shuffled = i;
// shuffle it
for (i=0; i<MAX; i=i+1) begin
// Pick one of the remaining elements...
j = $dist_uniform(seed, i, MAX);
// Swap, unless we picked 'i' - no point in swapping with self
if (i != j) begin
k = shuffled;
shuffled = shuffled[j];
shuffled[j] = k;
end
end

For extra credit:
(1) why is the first loop test "i<=MAX" and the
second is "i<MAX" ? Is that right?
(2) does the "if (i!=j)" test yield any benefit?
(3) are you happy that the distribution of shuffling
meets your needs?

Note that SystemVerilog offers a ".shuffle()" method on
any array, and also cyclic-random variables using "randc".
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
 
Another obvious option would be to have a bool/bit array that records
that a number has been used. Then, "while" over the ($random %1000)
call until you hit an unused value.

I have used this simple technique many times.

-Mike Mintz
 
jtw wrote:

You can invert the output of the LFSR to get the all 0's case.
Click to expand...
Any LFSR solution is going to generate (2**n)-1 different
combinations, so you will always be missing 1 case if you need exactly
2**n, unless you generate an extra bits worth of values and throw
almost half away. Now, you can position that 1 missing value anyway
in the range 0..2**n, by using a comparator, but you will always miss
1 value.

Thus, if your number of array elements is small (e.g. 0..1024), it can
be effective to follow Steve Sharp's advice and use an array. If you
fill an array with the consecutive numbers and remove from the array
the numbers which have been used (i.e. selecting an array element
makes it impossible to get that number again), you can be certain, you
have implemented the correct semantics. Please excuse the errors in
the following Verilog; I don't write Verilog on a daily basis at the
moment.

int array[0..1024];
int maxleft;

initial begin
// fill up the array to get things initialized
for (maxleft = 0; maxlex <= 1024; maxleft = maxleft + 1) do begin
array[maxleft] = maxleft;
end;
end;

task takeone(result)
output result;
int result;
begin
int index;
// pick a random element out of the array
// the mod operator reduces the result of rand function
// to be in the range 0..maxleft-1
index = rand() % maxleft;
// return it
// note that the contents of the slot may not be the same as the index
result = array[index];
// use up 1 entry in the array
maxleft = maxleft - 1;
// move the last element into the spot vacated by the element returned
array[index] = array[maxleft];
end
 
On Thu, 20 Mar 2008 05:39:55 -0700 (PDT), "mmintz@gmail.com"
<mmintz@gmail.com> wrote:

Another obvious option would be to have a bool/bit array that records
that a number has been used. Then, "while" over the ($random %1000)
call until you hit an unused value.

I have used this simple technique many times.
Click to expand...
I find it's a great mental model of what you're trying to do
in many situations where you want constrained-random but are
obliged to implement it by hand.

However, isn't its runtime cost O(N^2) ? The pick-and-swap
technique is only O(N), I think. If you need just a few
numbers taken from a list - fewer than, say, about half of
the list's size - and must not have duplicates, then
repeated picking until you find a virgin value is OK. But
it gets pretty slow as you approach the last few values
in the list, and your hit rate drops toward 1/N.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
 
Jonathan Bromley wrote:

in the array, randomly pick one of the locations
at location or later in the array. Swap element with the
randomly-chosen element. Then move on to the next .
Click to expand...

Thanks for the succinct example.
I wrapped an initial block around the outer loop
and added a #1; at the top of the inner loop
to view sequential waveforms.

-- Mike Treseler
 
Jonathan Bromley wrote:

(snip)
I find it's a great mental model of what you're trying to do
in many situations where you want constrained-random but are
obliged to implement it by hand.

However, isn't its runtime cost O(N^2) ? The pick-and-swap
technique is only O(N), I think.
Click to expand...
Is it O(N)? I might guess O(N log N). Note that you have
to do it enough times such that the results are sufficiently
random for the given system. (Probably more for commercial
gambling equipment than for home computer games.)

If you need just a few
numbers taken from a list - fewer than, say, about half of
the list's size - and must not have duplicates, then
repeated picking until you find a virgin value is OK. But
it gets pretty slow as you approach the last few values
in the list, and your hit rate drops toward 1/N.
Click to expand...
If you reduce the list and the range of random numbers as
the list gets smaller, then it avoids that problem, though
the list packing is also O(N**2).

Another software method is to pair up each element with
a random number and then sort the pairs based on the
random number. Easier in software than hardware, though,
and O(sort algorithm).

-- glen
 
On Thu, 20 Mar 2008 18:22:31 +0000, Jonathan Bromley
<jonathan.bromley@MYCOMPANY.com> wrote:

On Thu, 20 Mar 2008 05:39:55 -0700 (PDT), "mmintz@gmail.com"
mmintz@gmail.com> wrote:

Another obvious option would be to have a bool/bit array that records
that a number has been used. Then, "while" over the ($random %1000)
call until you hit an unused value.

However, isn't its runtime cost O(N^2) ?
Click to expand...
To answer my own question: No. The math is a little messy
but it appears to be closer to O( N log(N) ), which of course
is much less expensive than O(N^2). Sorry.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
 
On Mar 20, 5:30 pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
Jonathan Bromley wrote:

However, isn't its runtime cost O(N^2) ?
Click to expand...
I didn't propose it as a solution because it would get slow as you
exhausted the numbers. It is clearly worse than the O(N) for the
shuffling technique. However, it is not as bad as N-squared, or as I
originally expected. The number of tries does not rise linearly with
the number of values produced. It only gets bad toward the end. It
is roughly proportional to

N + N/2 + N/3 + N/4 + N/5 + ... + N/N

or

N*(1 + 1/2 + 1/3 + 1/4 + 1/5 + ... + 1/N)

A little research indicates that summation is approximately ln(N). So
we are only talking O(N log N) after all.



 The pick-and-swap
technique is only O(N), I think.

Is it O(N)?  I might guess O(N log N).  Note that you have
to do it enough times such that the results are sufficiently
random for the given system.  (Probably more for commercial
gambling equipment than for home computer games.)
Click to expand...
If the RNG is truly random, then one swap for each position (i.e. a
random choice for the item to go at that position) is sufficient.
Mechanical card shuffling gets done repeatedly because one shuffle
cannot move each card to a completely random position in the deck.
For example, in a riffle shuffle, the top card will end up very near
the top, and the bottom card will end up very near the bottom.

This algorithm is O(N).
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top