simple PRNG?

[copx]

Can anyone point me to a simple, fast RRNG function to generate random ints
within a specified range? It is important that each value within the range
has the same probability (uniform distribution).
I do not want to use the unreliable rand() function, but I do not want to
bloat my code with something as complex as MT either. I am just looking for
a short code snippet that I can copy without worrying about licensing.
The function should work on limited platforms (no floating-point math
please, one that works even on platforms where int is only 16 bit would be
perfect).
I did search this group and the web but I could not find anything which
meets the requirements.

[Morris Dovey]

Re: simple PRNG?

copx wrote:

>
Can anyone point me to a simple, fast RRNG function to generate random ints
within a specified range? It is important that each value within the range
has the same probability (uniform distribution).
I do not want to use the unreliable rand() function, but I do not want to
bloat my code with something as complex as MT either. I am just looking for
a short code snippet that I can copy without worrying about licensing.
The function should work on limited platforms (no floating-point math
please, one that works even on platforms where int is only 16 bit would be
perfect).
I did search this group and the web but I could not find anything which
meets the requirements.

How simple, how fast, and how short do you require?

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA

http://www.iedu.com/DeSoto/

[copx]

Re: simple PRNG?


"Morris Dovey" <mrdovey@iedu.c omschrieb im Newsbeitrag
news:47E35B17.E 2826A1@iedu.com ...

copx wrote:

>>
>Can anyone point me to a simple, fast RRNG function to generate random
>ints
>within a specified range? It is important that each value within the
>range
>has the same probability (uniform distribution).
>I do not want to use the unreliable rand() function, but I do not want to
>bloat my code with something as complex as MT either. I am just looking
>for
>a short code snippet that I can copy without worrying about licensing.
>The function should work on limited platforms (no floating-point math
>please, one that works even on platforms where int is only 16 bit would
>be
>perfect).
>I did search this group and the web but I could not find anything which
>meets the requirements.

>
How simple, how fast, and how short do you require?

Not more than a page of code would be nice (with "simple" I meant little
code, not necessary easy to understand code). Fast means that the algorithm
should be able to generate hundreds of random numbers per second on a 80386
level machine at least. Of course, 10,000 numbers per second on a 8086 are
even better! ;)

[Richard Heathfield]

Re: simple PRNG?

copx said:

>
"Richard Heathfield" <rjh@see.sig.in validschrieb im Newsbeitrag
news:MOGdndOyAc om_37anZ2dnUVZ8 gydnZ2d@bt.com. ..

<snip>

>But seriously, this is the kind of thing you either do yourself, or pay
>someone to do for you.

>
Paying someone for about 20 lines of code?

How do you know it's only 20 lines of code? And what makes you think that
short==simple? Just because an algorithm doesn't take much code to
express, that doesn't mean it is trivial to think it up and implement it
correctly. E=mc^2 is simple enough to express, but it took quite a lot of
mathematics to establish that it was correct.

<snip>

I did not expect that someone would write such a thing from
scratch for me, just that someone might knew where to find it.

Fair enough - but you might get better results by asking in an algorithms
group.

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Walter Roberson]

Re: simple PRNG?

In article <fs00ia$nrl$1@a ioe.org>, jacob navia <jacob@nospam.o rgwrote:

>The lcc-win compiler system uses this:

/*
* Compute x[n + 1] = (7^5 * x[n]) mod (2^31 - 1).
* From "Random number generators: good ones are hard to find",
* Park and Miller, Communications of the ACM, vol. 31, no. 10,
* October 1988, p. 1195.
*/

The original poster requested,

>>I am just looking for
>>a short code snippet that I can copy without worrying about licensing.

The lcc-win32 page says,

http://www.cs.virginia.edu/~lcc-win32/

License:

This software is not freeware, it is copyrighted by Jacob Navia. It's
free for non-commercial use, if you use it professionally you have to
have to buy a licence.


By posting that routine in response to the original poster's question,
are you releasing that routine from your license? If not, then
it does not meet the original poster's requirements.

It is presently March 2008, which is less than 20 years since
the October 1988 publication date of the cited article. Do you
certify that there is no patent upon the algorithm, and are you
prepared to indemnify the original poster if it turns out that
there is a remaining patent upon it?
--
"The study of error is not only in the highest degree
prophylatic, but it serves as a stimulating introduction to the
study of truth." -- Walter Lipmann

[MisterE]

Re: simple PRNG?

Not more than a page of code would be nice (with "simple" I meant little
code, not necessary easy to understand code). Fast means that the
algorithm should be able to generate hundreds of random numbers per second
on a 80386 level machine at least. Of course, 10,000 numbers per second on
a 8086 are even better! ;)

Why one page of code? MT and ciphers like AES could easily make 10,000
numbers per second even on 386.

[Noob]

Re: simple PRNG?

copx wrote:

Can anyone point me to a simple, fast RRNG function

Did you mean PRNG?

to generate random ints within a specified range?
It is important that each value within the range
has the same probability (uniform distribution).
I do not want to use the unreliable rand() function, but I do not want to
bloat my code with something as complex as MT either. I am just looking for
a short code snippet that I can copy without worrying about licensing.
The function should work on limited platforms (no floating-point math
please, one that works even on platforms where int is only 16 bit would be
perfect).
I did search this group and the web but I could not find anything which
meets the requirements.

Did you look into linear congruential generators?

http://en.wikipedia.org/wiki/Linear_congruential_generator

They have several drawbacks, but they are very simple to program.

[jacob navia]

Re: simple PRNG?

Walter Roberson wrote:

In article <fs00ia$nrl$1@a ioe.org>, jacob navia <jacob@nospam.o rgwrote:
>

>The lcc-win compiler system uses this:

>

> /*
> * Compute x[n + 1] = (7^5 * x[n]) mod (2^31 - 1).
> * From "Random number generators: good ones are hard to find",
> * Park and Miller, Communications of the ACM, vol. 31, no. 10,
> * October 1988, p. 1195.
> */

>
The original poster requested,
>

>>I am just looking for
>>a short code snippet that I can copy without worrying about licensing.

>
The lcc-win32 page says,

http://www.cs.virginia.edu/~lcc-win32/

>
License:
>
This software is not freeware, it is copyrighted by Jacob Navia. It's
free for non-commercial use, if you use it professionally you have to
have to buy a licence.
>
>
By posting that routine in response to the original poster's question,
are you releasing that routine from your license? If not, then
it does not meet the original poster's requirements.
>
It is presently March 2008, which is less than 20 years since
the October 1988 publication date of the cited article. Do you
certify that there is no patent upon the algorithm, and are you
prepared to indemnify the original poster if it turns out that
there is a remaining patent upon it?

1) I have no license for this, it is not my algorithm as stated
in the comment. How could I license that?
2) Your only objective is here to try to denigrate my work. Go
ahead.
3) You can't patent an algorithm, as far as I know. So, your
suggestion is moot.

It would be better for everybody if all people around that need
to laugh at others, take advantage of people asking valid
questions here to scorn them would just disappear.

This is of course not going to happen, and you will go on posting
this kind of useless posts, with the only objective of confusing
people.




--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique

http://www.cs.virginia.edu/~lcc-win32

[jacob navia]

Re: simple PRNG?

Richard Heathfield wrote:

jacob navia said:
>
<snip>
>

>The lcc-win compiler system uses this:

>
Let us not forget that the lcc-win compiler system does not conform to
ISO/IEC 9899:1999, which you have said this very morning is "standard C".
So you're advocating a non-conforming compiler system.
>
<snip>
>

>This needs 32 bit maths as you see. I think it could be ported to 16
>bits by making the result mod 2^16 -1

>
Yes, it can. Unfortunately, this gives the result 32767 on every call.

I said "ported". Not just copied



--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique

http://www.cs.virginia.edu/~lcc-win32

[Richard Heathfield]

Re: simple PRNG?

jacob navia said:

<snip>

It would be better for everybody if all people around that need
to laugh at others, take advantage of people asking valid
questions here to scorn them would just disappear.

How about people who hurl insults and swear at those who disagree with
them?

>
This is of course not going to happen, and you will go on posting
this kind of useless posts, with the only objective of confusing
people.

You think your suggestion of modifying code to return 32767 on every call
was *useful*?

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Richard Heathfield]

Re: simple PRNG?

jacob navia said:

Richard Heathfield wrote:

>jacob navia said:
>>

<snip>

>>

>>This needs 32 bit maths as you see. I think it could be ported to 16
>>bits by making the result mod 2^16 -1

>>
>Yes, it can. Unfortunately, this gives the result 32767 on every call.

>
I said "ported". Not just copied

Show us.

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Richard Tobin]

Re: simple PRNG?

In article <fs0230$1iv$1@c anopus.cc.umani toba.ca>,
Walter Roberson <roberson@ibd.n rc-cnrc.gc.cawrote :

>By posting that routine in response to the original poster's question,
>are you releasing that routine from your license?

Of course he is. Why else would he post it to Usenet?

A short code fragment implementing a published algorithm is not
copyrightable anyway.

>It is presently March 2008, which is less than 20 years since
>the October 1988 publication date of the cited article. Do you
>certify that there is no patent upon the algorithm, and are you
>prepared to indemnify the original poster if it turns out that
>there is a remaining patent upon it?

Of course he isn't.

Do you have any reason to suppose that the algorithm is patented? Do
you even think it's possible to patent such an algorithm in most of
the world? Presumably you would never post any code at all, because
it might be patented somewhere.

In short, your post is mean-minded FUD, a most unworthy response
to someone who is trying to help.

-- Richard
--
:wq

[Richard Tobin]

Re: simple PRNG?

In article <fs00ia$nrl$1@a ioe.org>, jacob navia <jacob@nospam.o rgwrote:

>This needs 32 bit maths as you see. I think it could be ported to 16
>bits by making the result mod 2^16 -1

Did you mean mod 2^16, i.e. using the bottom 16 bits.

-- Richard
--
:wq

[jacob navia]

Re: simple PRNG?

Richard Tobin wrote:

In article <fs00ia$nrl$1@a ioe.org>, jacob navia <jacob@nospam.o rgwrote:
>

>This needs 32 bit maths as you see. I think it could be ported to 16
>bits by making the result mod 2^16 -1

>
Did you mean mod 2^16, i.e. using the bottom 16 bits.
>
-- Richard

Yes, but I do not know if the results satisfy the required
properties of a good random number generator. The 32 bit
sequence has a long cycle number, but the 16 bit mod of that
sequence could have completely different properties, I do not know.

I know that the algorithm was ported to a 16 bit dsp, and most 16 bit
machines provide a 32 bit result of two 16 bit number multiply...



--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique

http://www.cs.virginia.edu/~lcc-win32

[Walter Roberson]

Re: simple PRNG?

In article <fs04f8$3j3$1@p c-news.cogsci.ed. ac.uk>,
Richard Tobin <richard@cogsci .ed.ac.ukwrote:

>A short code fragment implementing a published algorithm is not
>copyrightabl e anyway.

That is completely incorrect from a legal standpoint. Copyright
law is about the "original expression of an idea", not about the
idea itself. For example in books and movies, basic plots get
reused over and over again, but each of them is copyrightable
because each of them is a different -expression- of the idea.

>>It is presently March 2008, which is less than 20 years since
>>the October 1988 publication date of the cited article. Do you
>>certify that there is no patent upon the algorithm, and are you
>>prepared to indemnify the original poster if it turns out that
>>there is a remaining patent upon it?

>Do you have any reason to suppose that the algorithm is patented?

The authors of the publication were in the USA at the time
of publication, so the possibility of a patent on the algorithm
is real. Any offering of specific code that does not *know*
whether the underlying algorithm is patented or not (or at
least specifically consider the point) risks being interpreted
as a definitive statement about the legal status of the algorithm.

>Do
>you even think it's possible to patent such an algorithm in most of
>the world?

Oh yes, definitely; all you have to do is wrap it within the phrasing
of being part of a "computer system" (or equivilent) and that
often gives enough physicallity to qualify for a patent.

>In short, your post is mean-minded FUD, a most unworthy response
>to someone who is trying to help.

The matter of whether the PNRG was license free or not was
a critical part of the original poster's request. Any referral
to specific code that fails to consider whether the code is
license free or not fails to address this critical part of the
original request.
--
"I buy more from my grocer than he buys from me, and I bet it's
the same with you and your grocer. That means we have a trade
deficit with our grocers. Does our perpetual grocer trade deficit
portend doom?" -- Walter Williams