Distinct Random number generator - verilog

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

nikhil_err@yahoo.co.in wrote:
> 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."
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)
Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org

iD8DBQFE6xc8rPt1Sc2b3ikRAnReAKDs61loLGuWb1gbSZicl1Xio5WCWwCg6ayb
lJAfR7yhDO9nTlkwogUdOxs=
=wtrA
-----END PGP SIGNATURE-----

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.


nikhil_err@yahoo.co.in wrote:
> 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.

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

Enchanter wrote:
> 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-----

nikhil_err@yahoo.co.in wrote:
> 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.

Enchanter wrote:
> 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.

Stephen Williams <spamtrap@icarus.com> writes:
> 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 : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

Stephen Williams wrote:
>
> 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.

sharp@cadence.com writes:

> 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

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?

<nikhil_err@yahoo.co.in> wrote in message
news:1156248866.151336.248690@m79g2000cwm.googlegroups.com...
> 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 think $dist_uniform(seed,start,end) will serve my purpose.
Stephen Williams wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Enchanter wrote:
> > 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-----

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.


John_H wrote:
> 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?
>
> <nikhil_err@yahoo.co.in> wrote in message
> news:1156248866.151336.248690@m79g2000cwm.googlegroups.com...
>> 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.