Distinct Random number generator

[n***@yahoo.co.in]

Can anyone please tell me how to generate random numbers in verilog
between 0 to 3 or any range such that the number generated earlier do
not repeat.

[Stephen Williams]

Post by n***@yahoo.co.in
Can anyone please tell me how to generate random numbers in verilog
between 0 to 3 or any range such that the number generated earlier do
not repeat.

Do you know about $random?

- --
Steve Williams "The woods are lovely, dark and deep.
steve at icarus.com But I have promises to keep,
http://www.icarus.com and lines to code before I sleep,
http://www.picturel.com And lines to code before I sleep."

[Enchanter]

It is easy to generate value in range such as 0-9. You can try ran_a =
$random() % 10. But it is hard to keep it not repeat. Systemverilog do
it well with constraint random feature.

Post by n***@yahoo.co.in
Can anyone please tell me how to generate random numbers in verilog
between 0 to 3 or any range such that the number generated earlier do
not repeat.

[Stephen Williams]

Post by Enchanter
It is easy to generate value in range such as 0-9. You can try ran_a =
$random() % 10. But it is hard to keep it not repeat. Systemverilog do
it well with constraint random feature.

That's silly. If $random is random, then so is $random % N. There
are caveats WRT the randomness of all 32 bits of the output from
$random, but for modeling purposes it's distributed well enough
that if you think $random%10 isn't random, then $random isn't either.

I wonder what aspect of SystemVerilog you believe makes better
random numbers from 0-9?

Or am I somehow misunderstanding the original request?

- --
Steve Williams "The woods are lovely, dark and deep.
steve at icarus.com But I have promises to keep,
http://www.icarus.com and lines to code before I sleep,
http://www.picturel.com And lines to code before I sleep."

[Chris F Clark]

Post by n***@yahoo.co.in
Can anyone please tell me how to generate random numbers in verilog
between 0 to 3 or any range such that the number generated earlier do
not repeat.
It is easy to generate value in range such as 0-9. You can try ran_a =
$random() % 10. But it is hard to keep it not repeat. Systemverilog do
it well with constraint random feature.
That's silly. If $random is random, then so is $random % N. There
are caveats WRT the randomness of all 32 bits of the output from
$random, but for modeling purposes it's distributed well enough
that if you think $random%10 isn't random, then $random isn't either.
I wonder what aspect of SystemVerilog you believe makes better
random numbers from 0-9?
Or am I somehow misunderstanding the original request?

Yes, I think you are missing the fact that the requester asked for a
list that didn't repeat. I would assume that the requestor wanted a
permutation and not just a list of random numbers in the range.

One inefficient way to get a permutation is to simply generate a list
and remove any duplicated numbers (ones you generated previously).
For small ranges of integers, i.e. 0..3, that can easily be done. If
you want a range of reals (floating point numbers), it is harder since
they are dense and there are lots of numbers between 0 and 3. On the
other hand, that also makes it unlikely that even just a simple list
of random numbers over the range will have any repeats.

So, the question is which problem the person wants solved--a
perumtation of integers or a list reals in the range 0..3 with no
duplicates. And, if the person needs a list of reals with no
duplicates, why isn't just a list of reals that might (but probably
doesn't) have duplicates isn't good enough?

There is also one last interpretation, which is the person wants a
random list that doesn't cycle (a true random list and not a
psuedo-random one). In that case, they need something completely
different than $random.

Hope this helps,
-Chris

*****************************************************************************
Chris Clark Internet : ***@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : [phone]
Berlin, MA 01503 USA fax : [phone] (24 hours)
------------------------------------------------------------------------------

[s***@cadence.com]

Post by Stephen Williams
Or am I somehow misunderstanding the original request?

I believe you are misunderstanding the original request. The OP does
not actually want random numbers. They want to avoid any repeats until
they have seen all the possible values, which is not really random. So
if you are generating numbers in the range 0:3, and you have gotten the
sequence 1,3,2 so far, the next number MUST be 0, to avoid repeating
any ot the earlier numbers. A true random number generator would still
have an equal probability of generating each of the numbers.

In SystemVerilog, I believe you can use the randc property to guarantee
a full cycle through all possible values before repeating. There may
also be ways to put constraints on the random number generation to
avoid repetitions.

One way to implement something like this is to recognize that you are
not generating a random number. Instead, you are taking the numbers in
the range and generating them in a random order. So you could start
with an array containing the numbers in the range, and apply a
shuffling algorithm of some kind. For example, swap randomly chosen
elements a lot of times. Then read out the array in order to get your
numbers.

An alternate approach would be to keep track of which numbers you have
generated with an array of flags, and keep generating numbers until you
get one that you have not generated yet. This would get very slow for
the last few numbers in a large range. There are probably better
algorithms, but this is what comes to mind on quick thought.

[Chris F Clark]

Post by s***@cadence.com
One way to implement something like this is to recognize that you are
not generating a random number. Instead, you are taking the numbers in
the range and generating them in a random order. So you could start
with an array containing the numbers in the range, and apply a
shuffling algorithm of some kind. For example, swap randomly chosen
elements a lot of times. Then read out the array in order to get your
numbers.
An alternate approach would be to keep track of which numbers you have
generated with an array of flags, and keep generating numbers until you
get one that you have not generated yet. This would get very slow for
the last few numbers in a large range. There are probably better
algorithms, but this is what comes to mind on quick thought.

Steve, you can combine your two approaches to get a relatively quick
and throughly random permutation generator. Start with an array of
values. Pick a random element of the array, swap that with the last
element. Decrease your problem size by 1 (you have solved the problem
for the last element and you now have the same problem for n-1
elements). The only isue with this approach is that your random
number generator is probably not completely uniformly distributed
after taking it mod n. It is close, but not perfect. Note that this
approach has the advantage of not slowing down as the problem
progresses, which makes it better than using flags. The flag approach
is good enough though for small ranges.

-Chris

[n***@yahoo.co.in]

Do you think $dist_uniform(seed,start,end) will serve my purpose.

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Post by Enchanter
It is easy to generate value in range such as 0-9. You can try ran_a =
$random() % 10. But it is hard to keep it not repeat. Systemverilog do
it well with constraint random feature.

That's silly. If $random is random, then so is $random % N. There
are caveats WRT the randomness of all 32 bits of the output from
$random, but for modeling purposes it's distributed well enough
that if you think $random%10 isn't random, then $random isn't either.
I wonder what aspect of SystemVerilog you believe makes better
random numbers from 0-9?
Or am I somehow misunderstanding the original request?
- --
Steve Williams "The woods are lovely, dark and deep.
steve at icarus.com But I have promises to keep,
http://www.icarus.com and lines to code before I sleep,
http://www.picturel.com And lines to code before I sleep."
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)
Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org
iD8DBQFE6yd6rPt1Sc2b3ikRAuJgAJwP/uXPzYAsca66K9qoggih3fN59gCfaOVp
Km3ifCdsBf2l8CinEfTbFD4=
=9Vcm
-----END PGP SIGNATURE-----

[s***@cadence.com]

Post by n***@yahoo.co.in
Do you think $dist_uniform(seed,start,end) will serve my purpose.

It will give you a random number in that range, if that is what you
want. It will not avoid repeating a number, since the numbers are
supposed to be random.

BTW, if you follow the suggestion of using $random % 4, this will not
actually give you values in the range 0:3. $random is officially
defined to return an integer, which is signed. And a negative signed
number will produce a negative modulo result. So you would get values
in the range -3:3 instead. You would need to force the number to be
treated as unsigned before the modulo. One easy way would be to use
{$random} % 4.

[b***@hotmail.com]

Maximal LFSR with N bits would produce unrepeating string of
2^(N)-1 pseudo-random numbers.

Actually simple random number generators usualy use LFSR.

Linear feedback shift register (LFSR) on Wikipedia:
http://en.wikipedia.org/wiki/Linear_feedback_shift_register

Post by s***@cadence.com

Post by n***@yahoo.co.in
Do you think $dist_uniform(seed,start,end) will serve my purpose.

It will give you a random number in that range, if that is what you
want. It will not avoid repeating a number, since the numbers are
supposed to be random.
BTW, if you follow the suggestion of using $random % 4, this will not
actually give you values in the range 0:3. $random is officially
defined to return an integer, which is signed. And a negative signed
number will produce a negative modulo result. So you would get values
in the range -3:3 instead. You would need to force the number to be
treated as unsigned before the modulo. One easy way would be to use
{$random} % 4.

[Jonathan Bromley]

Post by b***@hotmail.com
Maximal LFSR with N bits would produce unrepeating string of
2^(N)-1 pseudo-random numbers.

Well, pseudo-random *bits* actually... and you can use them
to create (( (2^N)-1 ) / N) random NUMBERS each N bits wide.
If you use successive samples of an LFSR's shift register
in the hope of getting random numbers, you'll be disappointed:
they will be very highly correlated, for obvious reasons.

More to the point, though: an LFSR produces the *same*
string for every cycle of the
generator. I suspect that the original poster wants the
cyclic-randomization behaviour of SystemVerilog's "randc"
that has been discussed elsewhere in this thread. For the
record, you can get the same sort of behaviour in 'e' using
the idiom
keep scrambled_list.is_a_permutation(ordered_list);
--
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
***@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.

[b***@hotmail.com]

Post by Jonathan Bromley

Post by b***@hotmail.com
Maximal LFSR with N bits would produce unrepeating string of
2^(N)-1 pseudo-random numbers.

Well, pseudo-random *bits* actually... and you can use them
to create (( (2^N)-1 ) / N) random NUMBERS each N bits wide.
If you use successive samples of an LFSR's shift register
they will be very highly correlated, for obvious reasons.

I'm curious: does System Verilog stipulate the quality of the random
number generator used as a base of randc and others or is it left
to tool implementations? (libc implementation of particular OS)

That would be my frst question if statistical properties of
the generated random sequences were of the concern.

[John_H]

Does this request ask for a new list of random numbers that isn't the same
as the list you ran through simulation the last time?

Post by n***@yahoo.co.in
Can anyone please tell me how to generate random numbers in verilog
between 0 to 3 or any range such that the number generated earlier do
not repeat.

[John_H]

If you can generate a unique "seed" value every time you run your
simulation (such as using a script to write the operating system's
realtime to a file and reading the value in that file into a Verilog
variable, then you can use $random(seed)%4 to get the random integers
from 0-3. When the seed value changes, so does the list. For the same
seed value, the list doesn't change, run after run.

Another thought might be to write a new seed (newseed=$random(seed)) to
the seed file, replacing the value that was there last time or appending
to the end of the file such that you have a list of all seeds run to
date, just reading the new seed from the end of the file each time.

Post by John_H
Does this request ask for a new list of random numbers that isn't the same
as the list you ran through simulation the last time?

Post by n***@yahoo.co.in
Can anyone please tell me how to generate random numbers in verilog
between 0 to 3 or any range such that the number generated earlier do
not repeat.

[Alex]

You can do it with Verilog:

1. Create the model of array using verilog memory and populate it with
the numbers.
2. Shuffle the contents of array
3. Read array in sequential order and re-shuffle it after every 4-th
read.



reg [1:0] mem [0:3];
integer i;
initial for (i=0; i<4; i=i+1) mem[i] = i;

//----------------------------------------------------
function integer rn;
input d1, d2;
integer d1, d2;
begin
rn = d1 + {$random} % (d2-d1+1);
end
endfunction

//----------------------------------------------------
task swap;
input n1, n2;
integer n1, n2;
reg [3:0] tmp_reg;
begin
tmp_reg = mem[n1];
mem[n1] = mem[n2];
mem[n2] = tmp_reg;
end
endtask

//----------------------------------------------------
task shuffle;
for (i=0; i<4; i=i+1) swap(i,rn(i,3));
endtask

.....

Also, there is a way to wrap such "randc" generator as parametric
verilog module.

Regards,
-Alex

Post by n***@yahoo.co.in
Can anyone please tell me how to generate random numbers in verilog
between 0 to 3 or any range such that the number generated earlier do
not repeat.