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.

[jacob navia]

Walter Roberson wrote:

In article <fs**********@a ioe.org>, jacob navia <ja***@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

[Richard Tobin]

In article <fs**********@c anopus.cc.umani toba.ca>,
Walter Roberson <ro******@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]

In article <fs**********@a ioe.org>, jacob navia <ja***@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]

Richard Tobin wrote:

In article <fs**********@a ioe.org>, jacob navia <ja***@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]

In article <fs**********@p c-news.cogsci.ed. ac.uk>,
Richard Tobin <ri*****@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

[Walter Roberson]

In article <fs**********@a ioe.org>, jacob navia <ja***@nospam.o rgwrote:

>Richard Heathfield wrote:

>jacob navia said:

>>Richard Heathfield wrote:
jacob navia said:

>>>>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

>This program:
---------------------------------------------------------------
/*
* Pseudo-random number generator. The result is uniform on
* [0, 2^31 - 1].
*/

>#include <stdio.h>
int main(void)
{
for (int i=0; i<10;i++) {
printf("%d\n",r andom()&0xffff) ;
}
}

>-----------------------------------------------------------------------
produces the following output:
16807
15089
44249
3114
46978
56008

On a system where int was 16 bit, random()&0xffff
risks exceeding INT_MAX, so printing the result with a %d format
could result in negative numbers, such as would occur for
the results 44249 46978 56008. An unsigned output format
should be used instead.
--
"Prevention is the daughter of intelligence."
-- Sir Walter Raleigh

[jacob navia]

Walter Roberson wrote:
[snip]

On a system where int was 16 bit, random()&0xffff
risks exceeding INT_MAX, so printing the result with a %d format
could result in negative numbers, such as would occur for
the results 44249 46978 56008. An unsigned output format
should be used instead.

Granted, but this doesn't mean that the algorithm will
always print the same number as Heathfield supposed.

I should have written "%u" of course.
--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32

[jacob navia]

Walter Roberson wrote:
[snip legalese]

OK. Mr Roberson you know FAR more legal stuff than I do.

The only thing that I can answer is:

DISCLAIMER:
-----------

The code published by me in this group is released into
the public domain. Anyone can use it for any purpose
whatsoever.

No liabilities can be construed against me. Use at your
own risk.

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32

[copx]

"copx" <co**@gazeta.pl schrieb im Newsbeitrag
news:fr******** *@inews.gazeta. pl...

Can anyone point me to a simple, fast RRNG function to generate random
ints within a specified range?

To answer my own question:

I cooked this up based on C FAQ entries. I use the portable "minimal
standard" algorithm, and the recommended method to get numbers within a
certain range based (the float free variant):

------- code start ----
#include <stdio.h>
#include <time.h>

static long int seed = 1;
/*
* generate int between lb and ub (inclusive)
*/
int mrand(int lb, int ub)
{
long int hi = seed / 44488;
long int lo = seed % 44488;

seed = 48271 * lo - 3399 * hi;

if (seed <= 0) seed += 2147483647;

return lb + (seed / (2147483646 / (ub + 1 - lb) + 1));
}
/*
* test distribution
*/
void test_it(void)
{
int lim = 11000;
int oc[11] = {0,0,0,0,0,0,0, 0,0,0,0};
int i;

while (lim-- 0) ++oc[mrand(0, 10)];

for (i = 0; i < 11; i++) printf("%d: %d\n", i, oc[i]);
}
int main(void)
{

seed = time(NULL);

test_it();

return 0;
}

--------- code ends here ------

Feel free to point out any problems.

It seems to work, at least on my system. Notice that I have also tested the
algorithm with billions of random numbers, the distribution stays uniform
(or at least close enough to be called "non-biased" - I do not know how to
test for real uniformity - but this is only for a game so it's definitely
good enough).

[Walter Roberson]

In article <fs**********@a ioe.org>, jacob navia <ja***@nospam.o rgwrote:

>unsigned long random(void)
{
register long x, hi, lo, t;

/*
* 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.
*/
x = _randseed;
hi = x / 127773;
lo = x % 127773;
t = 16807 * lo - 2836 * hi;
if (t <= 0)
t += 0x7fffffff;
_randseed = t;
return (t);
}

It would be safer (or at least clearer) if most of your constants
were suffixed with L to avoid their being interpreted (if only
mentally) as overflowing the range of UINT_MAX on 16 bit systems.
--
"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