simple PRNG?

[Walter Roberson]

Re: simple PRNG?

In article <fs057r$7rd$1@a ioe.org>, jacob navia <jacob@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]

Re: simple PRNG?

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]

Re: simple PRNG?

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]

Re: simple PRNG?


"copx" <copx@gazeta.pl schrieb im Newsbeitrag
news:frvita$jj$ 1@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]

Re: simple PRNG?

In article <fs057r$7rd$1@a ioe.org>, jacob navia <jacob@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

[Eric Sosman]

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.

MT isn't all that large, but if you seek things even
shorter you might want to search for Park & Miller's "Minimal
Standard Random Number Generator." Also, George Marsaglia
posted a few of his generators to this group a few years ago,
before the ignorant yahoos drove him away. You should be
able to find them in the archives.

--
Eric Sosman
esosman@ieee-dot-org.invalid

[Eric Sosman]

Re: simple PRNG?

jacob navia wrote:

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

ITYM (0, 2^31 - 1) or [1, 2^31 - 2].

--
Eric Sosman
esosman@ieee-dot-org.invalid

[Walter Roberson]

Re: simple PRNG?

In article <47e3a935$0$900 $ba4acef3@news. orange.fr>,
jacob navia <jacob@nospam.o rgwrote:

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

Fair enough; I asked you to clarify the license terms of the
code and you did.


For clarity: did you intend your release into the public domain to
apply only to this one routine, or to apply to -all- of your code that
you post in comp.lang.c? If you intend it to apply to -all- of your
code that you post, then it would be better from a legal standpoint to
have the release into the public domain accompany each block of code
that you so release. Under the Berne Convention on Copyright, original
expressions of ideas are automatically copyrighted by their author
(except perhaps "works for hire") unless copyright is specifically
released, so for any of your code that you published, the legal
presumption would be that it is copyrighted unless the copyright
release was "right there".
--
"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]

Re: simple PRNG?

In article <fs09ht$ctq$1@i news.gazeta.pl> , copx <copx@gazeta.pl wrote:

>/*
* 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));
>}

Caution: you are mixing int arithmetic with long arithmetic.
ub + 1 could overflow INT_MAX, and ub + 1 - lb could
certainly overflow INT_MAX.

Also, as I indicated in response to Jacob's code: it would
be safer (or at least clearer) to suffix your constants with
L when you are working with long arithmetic, to avoid
problems (or at least mental confusion) with constants that
exceed INT_MAX.
--
"Style is instinctive and few achieve it in a notable degree. Its
development is not hastened by instruction. It comes or it doesn't.
It will take care of itself." -- Walter J. Phillips

[Ben Bacarisse]

Re: simple PRNG?

"copx" <copx@gazeta.pl writes:

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

Probably the best bit-size independent algorithm is

Robert M. Ziff, "Four-tap shift-register-sequence random-number
generators," Computers in Physics 12(4), Jul/Aug 1998, pp 385-392.

It is very simple if you can spare the space for the state (min is
about 9700 previous numbers). It can be implemented slightly faster
if you can spare the space for 16384 of them (the next power of 2).

The algorithm is just

R[n] = R[n-A] ^ R[n-B] ^ R[n-C] ^ R[n-D]

with "good" choices of A, B, C and D being 471, 1586, 6988 and 9689.
It is fast and has a huge period. The advantage over arithmetic PRNGs
is that it is in essence parallel: each number is result is combining
N bits from N random bit streams (N being the width of each R) so it
works just as well with N=1 (requiring about 9700 bits of state) or
N=64 with each R being a 64-bit int.

Implementation probably no more than 20 lines. GPL version exists in
the GSL library.

--
Ben.

[jacob navia]

Re: simple PRNG?

Richard Heathfield wrote:

[snip drivel]

Here, then, is my driver. Feel free to point out the bug.
>

[snip]

>
srandom(0);

There

I never set the seed to zero in my code.

Seed must be bigger than zero obviously
And please do not say that you "did not know that"
since I did not use srandom() at all in the example
I sent.

The whole content of Heathfield's messages is this:

Word games, more word games, bad faith, apparently innocent
remarks full of hate... etc.

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

[Eric Sosman]

Re: simple PRNG?

Morris Dovey wrote:

[...]
unsigned simple_fast_uni form_free_16(vo id)
{ static unsigned x;
return x = 0x0FFFFu & ++x;
}
>
is restricted to 16-bit integer values, meets speed requirement
for 8086, and distribution is perfectly uniform. It's free and
there is no licensing to worry about.

Undefined behavior is, I guess, a kind of "randomness ."

--
Eric.Sosman@sun .com

[Morris Dovey]

Re: simple PRNG?

Eric Sosman wrote:

>
Morris Dovey wrote:

[...]
unsigned simple_fast_uni form_free_16(vo id)
{ static unsigned x;
return x = 0x0FFFFu & ++x;
}

is restricted to 16-bit integer values, meets speed requirement
for 8086, and distribution is perfectly uniform. It's free and
there is no licensing to worry about.

>
Undefined behavior is, I guess, a kind of "randomness ."

I decided to give socialized programming a shot. <g>

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA

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

[jacob navia]

Re: simple PRNG?

Eric Sosman wrote:

Morris Dovey wrote:

>[...]
> unsigned simple_fast_uni form_free_16(vo id)
> { static unsigned x;
> return x = 0x0FFFFu & ++x;
> }
>>
>is restricted to 16-bit integer values, meets speed requirement
>for 8086, and distribution is perfectly uniform. It's free and
>there is no licensing to worry about.

>
Undefined behavior is, I guess, a kind of "randomness ."
>

(!!!!!!!!!!!!!! !)

Why this nasty habit of laughing at people that
ask questions here?

And then presenting a program that has UB!

I think he was trying to mimic Heathfield with his other
example mocking the OP.


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

[Morris Dovey]

Re: simple PRNG?

jacob navia wrote:

>
Eric Sosman wrote:

Morris Dovey wrote:

[...]
unsigned simple_fast_uni form_free_16(vo id)
{ static unsigned x;
return x = 0x0FFFFu & ++x;
}
>
is restricted to 16-bit integer values, meets speed requirement
for 8086, and distribution is perfectly uniform. It's free and
there is no licensing to worry about.

Undefined behavior is, I guess, a kind of "randomness ."

>
(!!!!!!!!!!!!!! !)
>
Why this nasty habit of laughing at people that
ask questions here?
>
And then presenting a program that has UB!
>
I think he was trying to mimic Heathfield with his other
example mocking the OP.

I doubt it, I wasn't, and yes I did. :-)

It would have been more appropriate to have re-directed the OP to
news:alt.source s.wanted, n'est ce pas?

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA

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