468,457 Members | 1,555 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,457 developers. It's quick & easy.

simple PRNG?

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.


Mar 21 '08 #1
55 5874
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/
Mar 21 '08 #2

"Morris Dovey" <mr*****@iedu.comschrieb im Newsbeitrag
news:47**************@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! ;)

Mar 21 '08 #3
copx said:
>
"Richard Heathfield" <rj*@see.sig.invalidschrieb im Newsbeitrag
news:MO******************************@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
Mar 21 '08 #4
In article <fs**********@aioe.org>, jacob navia <ja***@nospam.orgwrote:
>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
Mar 21 '08 #5
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.
Mar 21 '08 #6
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_...tial_generator

They have several drawbacks, but they are very simple to program.
Mar 21 '08 #7
Walter Roberson wrote:
In article <fs**********@aioe.org>, jacob navia <ja***@nospam.orgwrote:
>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
Mar 21 '08 #8
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
Mar 21 '08 #9
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
Mar 21 '08 #10
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
Mar 21 '08 #11
In article <fs**********@canopus.cc.umanitoba.ca>,
Walter Roberson <ro******@ibd.nrc-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
Mar 21 '08 #12
In article <fs**********@aioe.org>, jacob navia <ja***@nospam.orgwrote:
>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
Mar 21 '08 #13
Richard Tobin wrote:
In article <fs**********@aioe.org>, jacob navia <ja***@nospam.orgwrote:
>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
Mar 21 '08 #14
In article <fs**********@pc-news.cogsci.ed.ac.uk>,
Richard Tobin <ri*****@cogsci.ed.ac.ukwrote:
>A short code fragment implementing a published algorithm is not
copyrightable 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
Mar 21 '08 #15
In article <fs**********@aioe.org>, jacob navia <ja***@nospam.orgwrote:
>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",random()&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
Mar 21 '08 #16
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
Mar 21 '08 #17
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
Mar 21 '08 #18

"copx" <co**@gazeta.plschrieb 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).

Mar 21 '08 #19
In article <fs**********@aioe.org>, jacob navia <ja***@nospam.orgwrote:
>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
Mar 21 '08 #20
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
es*****@ieee-dot-org.invalid
Mar 21 '08 #21
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
es*****@ieee-dot-org.invalid
Mar 21 '08 #22
In article <47*********************@news.orange.fr>,
jacob navia <ja***@nospam.orgwrote:
>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
Mar 21 '08 #23
In article <fs**********@inews.gazeta.pl>, copx <co**@gazeta.plwrote:
>/*
* 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
Mar 21 '08 #24
"copx" <co**@gazeta.plwrites:
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.
Mar 21 '08 #25
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
Mar 21 '08 #26
Morris Dovey wrote:
[...]
unsigned simple_fast_uniform_free_16(void)
{ 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."

--
Er*********@sun.com

Mar 21 '08 #27
Eric Sosman wrote:
>
Morris Dovey wrote:
[...]
unsigned simple_fast_uniform_free_16(void)
{ 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/
Mar 21 '08 #28
Eric Sosman wrote:
Morris Dovey wrote:
>[...]
unsigned simple_fast_uniform_free_16(void)
{ 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
Mar 21 '08 #29
jacob navia wrote:
>
Eric Sosman wrote:
Morris Dovey wrote:
[...]
unsigned simple_fast_uniform_free_16(void)
{ 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.sources.wanted, n'est ce pas?

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto/
Mar 21 '08 #30
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).
Reconsider MT. I find the code object module occupies
approximately 512 bytes. For most applications this is trivial.
It is available (as cokusmt) within the hashlib code on my page.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
--
Posted via a free Usenet account from http://www.teranews.com

Mar 21 '08 #31

"Richard Heathfield" <rj*@see.sig.invalidwrote in message
news:ka*********************@bt.com...
jacob navia said:
[random number code]
>Word games, more word games, bad faith, apparently innocent
remarks full of hate... etc.

When I play word games, it's with a serious purpose. I don't criticise
your
articles in bad faith. And I certainly don't hate you. So I'm afraid
you're completely wrong again.
You were reporting a bug and it's customary to provide enough info to
replicate the bug.

I also copied the code and spent some time trying to replicate the
behaviour, admittedly before reading the rest of the thread.

Unless the low 16 bits were always 1, how could truncating to the first 16
bits make them always 1? (I read mod 2^16-1, although sloppily written, as
taking the low word)

I think you were being a little mischievous in not mentioning the seed value
of zero earlier.

A version of this code I've seen elsewhere explicitly states, "Can't be
initialised with 0..." and chooses a different value. This is the real
problem with the code.

--
Bart

Mar 21 '08 #32
Bartc said:

<snip>
I think you were being a little mischievous in not mentioning the seed
value of zero earlier.
If I'd deliberately omitted that information, I'd agree. But it hadn't
occurred to me that it was even relevant - as I have already explained.

--
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
Mar 21 '08 #33
Bartc wrote:
"Richard Heathfield" <rj*@see.sig.invalidwrote in message
news:ka*********************@bt.com...
>jacob navia said:

[random number code]
>>Word games, more word games, bad faith, apparently innocent
remarks full of hate... etc.
When I play word games, it's with a serious purpose. I don't criticise
your
articles in bad faith. And I certainly don't hate you. So I'm afraid
you're completely wrong again.

You were reporting a bug and it's customary to provide enough info to
replicate the bug.
Exactly
I also copied the code and spent some time trying to replicate the
behaviour, admittedly before reading the rest of the thread.

Unless the low 16 bits were always 1, how could truncating to the first 16
bits make them always 1? (I read mod 2^16-1, although sloppily written, as
taking the low word)

I think you were being a little mischievous in not mentioning the seed value
of zero earlier.
This is the point.

1) He answers a perfectly valid question about a random number generator
with just a sarcastic answer where he laughs at the OP.
2) Trying to erase that bad impression, I hurry to post the code I use
for random numbers
3) He says that my code "Will produce always zero"
4) I compile (again) my code. It works. I send here my full
example. The initialized value is ONE.
5) He insists. And later he sends his code and "He doesn't realize
that he shouldn't initialize it to zero". He doesn't say that
in my example code it is initialized to ONE. He ignores that
6) It is this *hypocrisy* that I find disgusting.
A version of this code I've seen elsewhere explicitly states, "Can't be
initialised with 0..." and chooses a different value. This is the real
problem with the code.
I tried to help the OP. He could have pointed out "You should say that
zero is not a valid value". That would have been fair. But he isn't.

He is just a *pedant*!

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32
Mar 21 '08 #34
Richard Heathfield wrote:
Bartc said:

<snip>
>I think you were being a little mischievous in not mentioning the seed
value of zero earlier.

If I'd deliberately omitted that information, I'd agree. But it hadn't
occurred to me that it was even relevant - as I have already explained.
Incredible!

You have READ this code and you did NOT find the bug?

But two days ago you said that you find bugs without even
reading the source!

That it is enough to READ the code (no debugger needed)
to find out the bugs?

And NOW with the FULL SOURCE code you aren't able
to find a simple BUG like that in a program less than 20 lines???

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32
Mar 21 '08 #35
jacob navia wrote:
Richard Heathfield wrote:
>Bartc said:

<snip>
>>I think you were being a little mischievous in not mentioning the seed
value of zero earlier.

If I'd deliberately omitted that information, I'd agree. But it hadn't
occurred to me that it was even relevant - as I have already explained.

Incredible!

You have READ this code and you did NOT find the bug?

But two days ago you said that you find bugs without even
reading the source!

That it is enough to READ the code (no debugger needed)
to find out the bugs?

And NOW with the FULL SOURCE code you aren't able
to find a simple BUG like that in a program less than 20 lines???
Let's note that the bug was right there in your source
for all to see. I saw it as soon as I read your post. How
much debugger time did you spend failing to find it?

--
Er*********@sun.com
Mar 21 '08 #36
jacob navia said:
Richard Heathfield wrote:
>Bartc said:

<snip>
>>I think you were being a little mischievous in not mentioning the seed
value of zero earlier.

If I'd deliberately omitted that information, I'd agree. But it hadn't
occurred to me that it was even relevant - as I have already explained.

Incredible!

You have READ this code and you did NOT find the bug?
Right.
But two days ago you said that you find bugs without even
reading the source!
Go back and read it again. What I said was that I *have* found bugs without
even reading the source *on occasion*. I *also* said that usually this
cannot be done. Your continual attempts to set up strawmen (i.e. to extend
your opponents' positions beyond what they have actually claimed) do you
no credit whatsoever.

That it is enough to READ the code (no debugger needed)
to find out the bugs?
That is often the case, yes.
And NOW with the FULL SOURCE code you aren't able
to find a simple BUG like that in a program less than 20 lines???
Your code, your bug, your problem. Had I been sufficiently motivated to
find the bug myself, I would have spent some time looking for it. Since I
didn't look for it, I didn't find it.

--
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
Mar 21 '08 #37
"copx" <co**@gazeta.plwrites:
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).
Here is a portable PRNG:
http://www.stanford.edu/~blp/writings/clc/random.html
I don't know whether it is fast enough for you, but it is fairly
fast.
--
"To get the best out of this book, I strongly recommend that you read it."
--Richard Heathfield
Mar 21 '08 #38
On Mar 21, 5:26*am, "copx" <c...@gazeta.plwrote:
"copx" <c...@gazeta.plschrieb im Newsbeitragnews: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).
If you want to test your PRNG for uniformity, use the standard NIST
tests for that.
http://csrc.nist.gov/groups/ST/toolkit/rng/index.html
Mar 21 '08 #39
Eric Sosman wrote:
jacob navia wrote:
>Richard Heathfield wrote:
>>Bartc said:

<snip>

I think you were being a little mischievous in not mentioning the seed
value of zero earlier.

If I'd deliberately omitted that information, I'd agree. But it
hadn't occurred to me that it was even relevant - as I have already
explained.

Incredible!

You have READ this code and you did NOT find the bug?

But two days ago you said that you find bugs without even
reading the source!

That it is enough to READ the code (no debugger needed)
to find out the bugs?

And NOW with the FULL SOURCE code you aren't able
to find a simple BUG like that in a program less than 20 lines???

Let's note that the bug was right there in your source
for all to see. I saw it as soon as I read your post. How
much debugger time did you spend failing to find it?
You are lyi^h^h^hmisrepresenting the truth!
1) I did initialize the seed to ONE.
2) I never called with zero.

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32
Mar 21 '08 #40
Eric Sosman wrote:
jacob navia wrote:
>Richard Heathfield wrote:
>>Bartc said:

<snip>

I think you were being a little mischievous in not mentioning the
seed value of zero earlier.

If I'd deliberately omitted that information, I'd agree. But it
hadn't occurred to me that it was even relevant - as I have already
explained.

Incredible!

You have READ this code and you did NOT find the bug?

But two days ago you said that you find bugs without even
reading the source!

That it is enough to READ the code (no debugger needed)
to find out the bugs?

And NOW with the FULL SOURCE code you aren't able
to find a simple BUG like that in a program less than 20 lines???

Let's note that the bug was right there in your source
for all to see. I saw it as soon as I read your post. How
much debugger time did you spend failing to find it?
Of course, I figured out the bug even before the code was posted. All it
took me was a few scribbles on an evenlope. :-)

Mar 21 '08 #41
jacob navia wrote:
Eric Sosman wrote:
>jacob navia wrote:
>>Richard Heathfield wrote:
Bartc said:

<snip>

I think you were being a little mischievous in not mentioning the seed
value of zero earlier.

If I'd deliberately omitted that information, I'd agree. But it
hadn't occurred to me that it was even relevant - as I have already
explained.
Incredible!

You have READ this code and you did NOT find the bug?

But two days ago you said that you find bugs without even
reading the source!

That it is enough to READ the code (no debugger needed)
to find out the bugs?

And NOW with the FULL SOURCE code you aren't able
to find a simple BUG like that in a program less than 20 lines???

Let's note that the bug was right there in your source
for all to see. I saw it as soon as I read your post. How
much debugger time did you spend failing to find it?

You are lyi^h^h^hmisrepresenting the truth!
1) I did initialize the seed to ONE.
2) I never called with zero.
You have misunderstood me (again). To illustrate,
would you say the following code is or is not buggy?

/* Return the larger of two int arguments. */
int grog(int x, int y) {
return x < y ? x : y;
}

To my way of thinking, this is buggy code. It's perfectly
legal, strictly-conforming C, but it's buggy anyhow. Why
is it buggy? Because it does something different than what
it's advertised to do, that's why. What it does is well-
defined, all above-board, completely kosher -- but it doesn't
fulfill the contract.

Here's one possible fix:

/* Return the smaller of two int arguments. */
int grog(int x, int y) {
return x < y ? x : y;
}

You will notice that not one character of the compilable code
has changed, that the revised function does exactly the same
thing the original did -- except this version is no longer
bug-ridden. Why not? Because it now fulfills its contract.

So, back to your code. It begins
/*
* Pseudo-random number generator. The result is uniform on
* [0, 2^31 - 1].
*/
.... and does not actually behave as described. It will never
return zero. It will only return 2^31 - 1 if seeded with zero
or with 2^31 - 1, in which cases it will return nothing else
but 2^31 - 1 forevermore, a distinctly non-uniform distribution.
In short, your function is buggy because it does not live up
to its stated contract; it is buggy for the same reason as the
first version of grog(). And the fix is similar (and has been
pointed out to you before this, too).

Did you find the debugger helpful in solving this problem?

--
Er*********@sun.com
Mar 21 '08 #42
On Fri, 21 Mar 2008 07:00:09 +0100, 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).
Most Unices (at least those that have BSD in their lineage) include a
quartet of functions viz., initstate, setstate, random and srandom that
generate random numbers of *much* higher quality than rand and srand.

IIRC, gcc also provides these (if certain preprocessor flags are enabled),
so it must be available on a wide variety of platforms.

Not sure about the 16 bit requirement though. Should you research and
find out, please let me / the group know.
--
ROT-13 email address to reply
Mar 22 '08 #43

"George Marsaglia" <ge*@stat.fsu.eduschrieb im Newsbeitrag
news:rt******************************@comcast.com. ..
>
"copx" <co**@gazeta.plwrote in message
news:fr*********@inews.gazeta.pl...
>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.

/* initialize with any 32-bit seed x and any 32-bit y not 0 */

static unsigned long x=2282008, y=362436069;

#define sK ( x=69069*x+123, y^=y<<13, y^=y>>17, y^=y<<5, x+y )
/* example main() should generate 10^9 integers in ~5 seconds,
with final j=1105441147. Try it.
*/

#include <stdio.h>
int main()
{unsigned long i,j;
for(i=0;i<1000000000;i++) j=sK;
printf("%U\n",j);
}

------------------- C code ends ------------------------
Looks good! I would like to use that, but..
Use of sK in any expression will produce a random 32-bit integer,
(unsigned), so that, for example, u=sK*2.328306437e-10 will
produce a uniform real u in the interval [0,1),
while I=sK*f will produce an integer I from 0 to n-1
if f=n*2.328306437e-10.

If float operations must be avoided, and you want a random integer
from 0 to n-1, you can mask off bits after invoking sK, so that enough
remain to provide your integer, rejecting those outside the range.
For example, a random integer k in 0<=k<12345 needs 14 bits,
so generate
k=(sK>>18);
and keep those for which k<12345.
I have to admit, that I do not really understand this. (just a hobby coder
here, almost no experience with bit level data manipulation)

Could you show me how can I use sK (without any floating point math) to
create a function like the one I posted, I mean:

/*
* generate int between lb and ub (inclusive)
*/
int mrand(int lb, int ub)
{
....
}

Mar 23 '08 #44

"Anand Hariharan" <zn********************@tznvy.pbzschrieb im Newsbeitrag
news:Io****************@bignews1.bellsouth.net...
On Fri, 21 Mar 2008 07:00:09 +0100, 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).

Most Unices (at least those that have BSD in their lineage) include a
quartet of functions viz., initstate, setstate, random and srandom that
generate random numbers of *much* higher quality than rand and srand.
[snip]

I want the code to be as compiler/platform independent as possible. So I
prefer to bundle a PRNG with the source whose characteristics are the same
on all platforms.

Mar 23 '08 #45
George Marsaglia wrote:
[snip PRNG code and insightful comments]
It's great to have you post to this group again.

Regards.
Mar 25 '08 #46
In article <rt******************************@comcast.com>
George Marsaglia <ge*@stat.fsu.eduwrote:
>/* initialize with any 32-bit seed x and any 32-bit y not 0 */

static unsigned long x=2282008, y=362436069;

#define sK ( x=69069*x+123, y^=y<<13, y^=y>>17, y^=y<<5, x+y )
[snippage]
>Use of sK in any expression will produce a random 32-bit integer,
(unsigned), so that, for example, u=sK*2.328306437e-10 will
produce a uniform real u in the interval [0,1) ...
If "unsigned long" is 64 bits (and it is on a number of systems),
this will produce a 64-bit result instead of a 32-bit result. I
think[%] -- but have not attempted to prove -- that it is OK simply
to reduce the result here mod 2^32 with:

#define sK \
((x=69069*x+123, y^=y<<13, y^=y>>17, y^=y<<5, x+y) & 0xffffffffUL)

The mask (against 0xffffffffUL) should be optimized out by any good
compiler in which "unsigned long" is already 32 bits. It is
necessary if you expect the result to be limited to no more than
32 bits, though.

[% I am not sure whether extra retained bits in x and/or y are a
problem. If they are, add more masks with 0xffffffffUL. Again,
the generated code should be the same wherever the masks are a
no-op, as on any machine with 32-bit "unsigned long". Alternatively,
one could use "uint32_t" on C99 systems, but masking is completely
portable, even to C89-only systems.]
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (4039.22'N, 11150.29'W) +1 801 277 2603
email: gmail (figure it out) http://web.torek.net/torek/index.html
Mar 26 '08 #47
Chris Torek wrote:
In article <rt******************************@comcast.com>
George Marsaglia <ge*@stat.fsu.eduwrote:
>/* initialize with any 32-bit seed x and any 32-bit y not 0 */

static unsigned long x=2282008, y=362436069;

#define sK ( x=69069*x+123, y^=y<<13, y^=y>>17, y^=y<<5, x+y )
[snippage]
>Use of sK in any expression will produce a random 32-bit integer,
(unsigned), so that, for example, u=sK*2.328306437e-10 will
produce a uniform real u in the interval [0,1) ...

If "unsigned long" is 64 bits (and it is on a number of systems),
this will produce a 64-bit result instead of a 32-bit result. I
think[%] -- but have not attempted to prove -- that it is OK simply
to reduce the result here mod 2^32 with:

#define sK \
((x=69069*x+123, y^=y<<13, y^=y>>17, y^=y<<5, x+y) & 0xffffffffUL)
The calculation of x should be OK, but y^=y>>17 would yield a different
value. Try

#define sK \
(x=69069*x+123, y=(y^y<<13) & 0xffffffffUL, y^=y>>17, \
y^=y<<5, (x+y) & 0xffffffffUL)
[% I am not sure whether extra retained bits in x and/or y are a
problem. If they are, add more masks with 0xffffffffUL. Again,
the generated code should be the same wherever the masks are a
no-op, as on any machine with 32-bit "unsigned long". Alternatively,
one could use "uint32_t" on C99 systems, but masking is completely
portable, even to C89-only systems.]
Also, since uint32_t is not guaranteed to exist the masked approach is more
general.

--
Thad
Mar 26 '08 #48
Walter Roberson wrote:
>
In article <fs**********@aioe.org>,
jacob navia <ja***@nospam.orgwrote:
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.
Why are there any signed type objects at all
in that function definition?

register long unsigned fixes everything.

But I wouldn't publish purportedly portable code
with the keyword "register" in it, either.

--
pete
Mar 28 '08 #49
pete wrote:
>
.... snip ...
>
Why are there any signed type objects at all
in that function definition?

register long unsigned fixes everything.

But I wouldn't publish purportedly portable code
with the keyword "register" in it, either.
Why not? register is still a reserved word. All it is guaranteed
to do is prevent taking the address. Although it seems totally
ridiculous here.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

--
Posted via a free Usenet account from http://www.teranews.com

Mar 29 '08 #50

This discussion thread is closed

Replies have been disabled for this discussion.

By using this site, you agree to our Privacy Policy and Terms of Use.