simple PRNG?
copx
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
How simple, how fast, and how short do you require?
--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto/
copx
"Morris Dovey" <mrd...@iedu.com> schrieb im Newsbeitrag
news:47E35B17...@iedu.com...
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
/* PRNG requirements:
* simple
* fast
* uniform distribution within specified range
* mustn't call rand()
* no licensing issues
* works on limited platforms (no floating-point)
* works on platforms with 16-bit ints
* no more than one page of code
*/
/* prng() - returns a random number in the specified range 0 to 0 */
int prng(void)
{
return 0;
}
Requirements specifications can be a bitch to write, can't they? But
seriously, this is the kind of thing you either do yourself, or pay
someone to do for you. Yes, someone here might know of a free solution
that meets all your requirements, but you'd be silly to count on 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
copx
"Richard Heathfield" <r...@see.sig.invalid> schrieb im Newsbeitrag
news:MOGdndOyAcom_37a...@bt.com...
[snip]
> /* PRNG requirements:
> * simple
> * fast
> * uniform distribution within specified range
> * mustn't call rand()
> * no licensing issues
> * works on limited platforms (no floating-point)
> * works on platforms with 16-bit ints
> * no more than one page of code
> */
>
> /* prng() - returns a random number in the specified range 0 to 0 */
> int prng(void)
> {
> return 0;
> }
>
> Requirements specifications can be a bitch to write, can't they?
Muhuhuha, you are so funny!
Constructive contributions have become too boring, eh?
> 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?
> Yes, someone here might know of a free solution
> that meets all your requirements, but you'd be silly to count on it.
There are many free PRNGs available on the web, including high quality ones
who live up to all kinds of requirements (like MT), so I think it is
perfectly reasonable to assume that one of them might meet my requirements.
I did not expect that someone would write such a thing from scratch for me,
just that someone might knew where to find it.
copx
Morris Dovey
Ok. Priorities are 16-bit, small, fast, uniform distribution,
free, and random (in that order):
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.
Richard Heathfield
>
> "Richard Heathfield" <r...@see.sig.invalid> schrieb im Newsbeitrag
> news:MOGdndOyAcom_37a...@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.
jacob navia
> "Richard Heathfield" <r...@see.sig.invalid> schrieb im Newsbeitrag
[snip nonsense answer]
>
> Muhuhuha, you are so funny!
> Constructive contributions have become too boring, eh?
>
The prefered sport of "regulars" here is to laugh at
people. Do not bother. Not everybody is like that.
>> 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?
>
>> Yes, someone here might know of a free solution
>> that meets all your requirements, but you'd be silly to count on it.
>
> There are many free PRNGs available on the web, including high quality ones
> who live up to all kinds of requirements (like MT), so I think it is
> perfectly reasonable to assume that one of them might meet my requirements.
> I did not expect that someone would write such a thing from scratch for me,
> just that someone might knew where to find it.
>
> copx
>
>
The lcc-win compiler system uses this:
/*
* Pseudo-random number generator. The result is uniform on
* [0, 2^31 - 1].
*/
static unsigned long _randseed = 1;
unsigned long EXPORT 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);
}
void EXPORT srandom(unsigned long seed)
{
_randseed=seed;
}
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
--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32
Walter Roberson
>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
Richard Heathfield
<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. Time
to break out your debugger, perhaps.
Put your own house in order before complaining about other people.
MisterE
> 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.
Richard Bos
> "Richard Heathfield" <r...@see.sig.invalid> schrieb im Newsbeitrag
> > Yes, someone here might know of a free solution
> > that meets all your requirements, but you'd be silly to count on it.
>
> There are many free PRNGs available on the web, including high quality ones
> who live up to all kinds of requirements (like MT), so I think it is
> perfectly reasonable to assume that one of them might meet my requirements.
And you've looked at those before you came here? If not, why not? If so,
why, if they're so good, ask us instead?
> I did not expect that someone would write such a thing from scratch for me,
> just that someone might knew where to find it.
You could probably do worse than searching this newsgroup for posts by
George Marsaglia.
Richard
Noob
> Can anyone point me to a simple, fast RRNG function
Did you mean PRNG?
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
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 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
Richard Heathfield
<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
> 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.
Ian Collins
> 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?
>
--
Ian Collins.
Richard Heathfield
Quite so.
Richard Tobin
Walter Roberson <robe...@ibd.nrc-cnrc.gc.ca> wrote:
>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
jacob navia
> 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.
>
This program:
---------------------------------------------------------------
/*
* Pseudo-random number generator. The result is uniform on
* [0, 2^31 - 1].
*/
static unsigned long _randseed = 1;
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);
}
void srandom(unsigned long seed)
{
_randseed=seed;
}
#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
36568
2558
12099
1101
(1)
I am of course unable to write a fully compliant C99 compiler as you
say, but I can still read a list of numbers.
Your assertion that the random number generator produces always the
same result is FALSE.
(2) I can't tell you if the properties of those numbers are the same as
the 32 bit numbers. I *know* that this algorithm has been ported to a
16 bit DSP, but I can't tell you its equivalent in standard C.
(3) For a very good discussion about the history of this algorithm,
random numbers, and related topics see
http://www.firstpr.com.au/dsp/rand31/
Richard Tobin
>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
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...
Walter Roberson
>Walter Roberson wrote:
>> 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?
>1) I have no license for this, it is not my algorithm as stated
> in the comment. How could I license that?
Your -expression- of the algorithm is copyrighted, and you
routinely license your -copyright- to others, usually requiring
a fee for commercial usage . The original poster requested a PNRG
that was license free. Are you offering your copyrighted code
for this routine as being license free? That is, are you offering
to let the original poster (and everyone else) copy that
routine (which is presently copyrighted by you) without restriction,
including for commercial use?
The original paper by Steve Park and Keith Miller contains code
in Pascal, and code in FORTRAN, but no code in C, so the code
you posted was not -copied- from the paper but rather written
by you (or copied by you from someone else), so the -copyright-
on the code is not resident in the paper you cited.
(Note: in mentioning that you require a fee for commercial usage,
I am in no way criticising you for chosing to charge licensing fees;
I've made my living for many years from organizations that charge
software licensing fees, and I do not subscribe to the notion
that "Software demands to be free!". The point of my mentioning your
commercial fees is solely with respect to the original poster's
requirement about *not* having to worry about licensing (and thus
potentially fees) for use of the desired PNRG.)
>3) You can't patent an algorithm, as far as I know.
In the paper you cited, in the About the Authors section,
Steve Park and Keith Miller are both listed as being at College
of William and Mary, in Williamsburg Virginia USA -- and in
the USA, you certainly *can* patent algorithms. See for example,
http://www.bitlaw.com/software-patent/history.html#1990s
But even before that, we can see successful algorithm patents
such as the LZW patent filed in June 1983,
http://patft.uspto.gov/netacgi/nph-Parser?patentnumber=4558302
--
"And that's the way it is." -- Walter Cronkite
Walter Roberson
Richard Tobin <ric...@cogsci.ed.ac.uk> wrote:
>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
Walter Roberson
>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
jacob navia
[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
[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.
copx
"copx" <co...@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
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
>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.
Richard Heathfield
> Richard Heathfield wrote:
>> 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.
>>
>
> This program:
<snip>
> printf("%d\n",random()&0xffff);
That's not mod, which is what you suggested earlier. It's bitwise-AND. mod
2^16-1 gives the result I told you about before. But let's take your
modification and run with it. Doing so produces 32767 on my system, every
time.
> produces the following output:
> 16807
> 15089
> 44249
> 3114
> 46978
> 56008
> 36568
> 2558
> 12099
> 1101
Interesting. I get different results.
> (1)
> I am of course unable to write a fully compliant C99 compiler as you
> say,
I didn't say you can't. I said you haven't. Whether you can or not remains
to be seen.
> but I can still read a list of numbers.
So can I. I ran your function 33554432 times, so I'd expect approximately
512 results (give or take) for each possible value in the range 0 to
65535. What I actually get is 33554432 lots of 32767, and *nothing else*.
Now, the possibility remains that my driver has a bug. I've looked at it
very carefully, and I can't find such a bug. (Of course, that might be
because I didn't use a debugger.)
Here, then, is my driver. Feel free to point out the bug.
#include <stdio.h>
#define FREQ_EXPECTED 512
#define ARRAY_SIZE 65536UL
int main(void)
{
unsigned long frequency[ARRAY_SIZE] = {0};
unsigned long counter = 0;
srandom(0);
for(counter = 0; counter < ARRAY_SIZE * FREQ_EXPECTED; counter++)
{
++frequency[random() & 0xFFFF];
}
for(counter = 0; counter < ARRAY_SIZE; counter++)
{
if(frequency[counter] != 0)
{
printf("%lu,%lu\n", counter, frequency[counter]);
}
}
return 0;
}
Output:
65535,33554432
>
> Your assertion that the random number generator produces always the
> same result is FALSE.
Not from where I'm sitting - not for your first suggestion (modulo), or
indeed for your second (bitwise-AND).
<snip>
Eric Sosman
> Can anyone point me to a simple, fast RRNG function to generate random ints
> I do not want to use the unreliable rand() function, but I do not want to
> 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
eso...@ieee-dot-org.invalid
Eric Sosman
>
> /*
> * 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
eso...@ieee-dot-org.invalid
Walter Roberson
jacob navia <ja...@nospam.org> wrote:
>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".
Walter Roberson
>/*
> * 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
> 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
[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.
Eric Sosman
> [...]
> 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."
Morris Dovey
I decided to give socialized programming a shot. <g>
--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto/
jacob navia
(!!!!!!!!!!!!!!!)
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.
Richard Heathfield
> 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.
So what? I set it to zero in mine. I see nothing in the documentation you
provided to suggest that srandom should not be called with a 0 argument.
> Seed must be bigger than zero obviously
It's not all that obvious, really. Since I wanted repeatable results whilst
testing, 0 was the obvious value to choose. If you think it "obvious" that
srandom should not be passed 0, I suggest that you make it refuse to
accept 0.
> And please do not say that you "did not know that"
I certainly didn't choose the value 0 to expose a bug, if that's what you
mean. I had no idea that choosing that value would so dramatically break
your code.
Now that you have told me that you meant bitwise-AND rather than mod, and
that I shouldn't pass 0 to srandom, I have conducted a third test, and the
numbers look reasonable. I suggest you amend your documentation so that it
explains the limitations of your srandom function.
> 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.
Morris Dovey
>
> 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?
CBFalconer
>
> 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
David Tiktin
[code sample snipped]
> 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).
I'm all for good enough ;-), but just for fun you might want to run
the output of your PRNG through the Diehard test suite.
http://en.wikipedia.org/wiki/Diehard_tests
It will give you a pretty good reading on how close "good enough" is
to good. There are some free implementations running around. Also,
the author of the Diehard tests, George Marsaglia, has published a
several free, fast PRNGs that pass the Dieheard tests. You might
want to take a look at those.
Dave
--
D.a.v.i.d T.i.k.t.i.n
t.i.k.t.i.n [at] a.d.v.a.n.c.e.d.r.e.l.a.y [dot] c.o.m
Bartc
"Richard Heathfield" <r...@see.sig.invalid> wrote in message
news:kaudnd9EptY...@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
Richard Heathfield
<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.
jacob navia
> "Richard Heathfield" <r...@see.sig.invalid> wrote in message
> news:kaudnd9EptY...@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
> 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???
Eric Sosman
> 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?
Richard Heathfield
> 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 Tobin
Walter Roberson <robe...@ibd.nrc-cnrc.gc.ca> wrote:
>>A short code fragment implementing a published algorithm is not
>>copyrightable anyway.
>Copyright
>law is about the "original expression of an idea", not about the
>idea itself.
Yes, and for a sufficiently simple algorithm there is no creative
expression. If there's basically one natural way to implement an
algorithm, you can't copyright it. See for example the arguments in
the USL vs BSDI case.
>>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.
That's absurd. Anyone taking a usenet article that made no mention
of patents as a definitive statement that there are none would be
out of their mind.
Furthermore, Jacob obviously believed there was no encumbrance,
since he used it in his own code.
In any case, the algorithm in question is a linear congruential
random number generator and the modulus it uses was first suggested
in 1969, see
http://www.research.ibm.com/journal/sj/082/ibmsj0802D.pdf
-- Richard
--
:wq
Ben Pfaff
> 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
user923005
> "copx" <c...@gazeta.pl> schrieb im Newsbeitragnews:frvita$jj$1...@inews.gazeta.pl...
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
jacob navia
You are lyi^h^h^hmisrepresenting the truth!
1) I did initialize the seed to ONE.
2) I never called with zero.
santosh
Of course, I figured out the bug even before the code was posted. All it
took me was a few scribbles on an evenlope. :-)
Eric Sosman
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?
CBFalconer
>
... snip ...
>
> That's absurd. Anyone taking a usenet article that made no mention
> of patents as a definitive statement that there are none would be
> out of their mind.
>
> Furthermore, Jacob obviously believed there was no encumbrance,
> since he used it in his own code.
>
> In any case, the algorithm in question is a linear congruential
> random number generator and the modulus it uses was first suggested
> in 1969, see
>
> http://www.research.ibm.com/journal/sj/082/ibmsj0802D.pdf
And there has been an available thorough discussion of linear
congruential generators at least since the first issuance of
TAOCP. Somewhere around 1970 or so.
George Marsaglia
"copx" <co...@gazeta.pl> wrote in message news:frvita$jj$1...@inews.gazeta.pl...
> Can anyone point me to a simple, fast RRNG function to generate random
> range has the same probability (uniform distribution).
> 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).
> 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 ------------------------
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.
The inline sK returns x+y. The congruential x=69069*x+123
is chosen because the multiplier is easy to remember and
produces a good lattice in studying "random numbers fall
mainly in the planes", the Marsaglia effect. (123 can be any odd integer).
The xorshift y^=y<<13, y^=y>>17, y^=y<<5,
uses shifts 13,17,5 from the 648 available in the article Xorshift RNGs,
http://www.jstatsoft.org/v08/i14/paper
Here, sK stands for simple KISS, one of a class I call KISS RNGs,
based on the principle: Keep It Simple, Stupid.
sK should provide around 200 million random integers per second,
period about 2^64 and pass all the tests in Diehard,
http://i.cs.hku.hk/~diehard/
Other KISS versions combine three simple methods to produce 32-bit integer
sequences with periods 2^125, 2^993, 2^5147, 2^12153 or 2^31311,
or a dKISS version produces double precision, IEEE754 standard,
uniform [0,1) reals using only + /- float operations,
period exceeding 2^1748.
Send requests if interested.
George Marsaglia
Anand Hariharan
> 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
copx
"George Marsaglia" <g...@stat.fsu.edu> schrieb im Newsbeitrag
news:rtGdnf5giO88inja...@comcast.com...
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)
{
...
}
copx
"Anand Hariharan" <znvygb.nana...@tznvy.pbz> schrieb im Newsbeitrag
news:IogFj.24095$dT....@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.
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.
Antoninus Twink
> 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?
Why does a playground bully make fun of the loner with glasses?
> And then presenting a program that has UB!
>
> I think he was trying to mimic Heathfield with his other
> example mocking the OP.
Seeing who can be the most unhelpful and unpleasant to newbies does seem
to be a game played all too frequently in clc...
George Marsaglia
OK, Easter breakfast assignment, but with a proc
to generate a random integer from 0 to n-1:
#include <stdio.h>
static unsigned long x=123456789, y=362436069, nn=0, h=0;
#define sK ( x=69609*x+123,y^=(y<<13), y^=(y>>17),y^=(y<<5), x+y )
/* proc rn(n) to generate random integer from 0 to n-1,
must have n>1, use only integer arithmetic
*/
int rn(int n)
{int j,k=1;
if(nn!=n) {nn=n; h=32; while(k<nn){k+=k; h--;} }
for(;;) { j=(sK>>h); if (j<n) return j;}
}
/* sample main( ), ten choices with n=100 and n=10000 */
int main( )
{int i,n;
n=100;
for(i=0;i<10;i++) printf("%d\n",rn(n));
n=10000;
for(i=0;i<10;i++) printf("%d\n",rn(n));
}
gm
copx
[snip]
> OK, Easter breakfast assignment, but with a proc
> to generate a random integer from 0 to n-1:
Thanks!
Noob
> [snip PRNG code and insightful comments]
It's great to have you post to this group again.
Regards.
Chris Torek
George Marsaglia <g...@stat.fsu.edu> wrote:
>/* 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 )
>Use of sK in any expression will produce a random 32-bit integer,
>(unsigned), so that, for example, u=sK*2.328306437e-10 will
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 (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: gmail (figure it out) http://web.torek.net/torek/index.html
Thad Smith
> In article <rtGdnf5giO88inja...@comcast.com>
> George Marsaglia <g...@stat.fsu.edu> wrote:
>> /* 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
pete
>
> Can anyone point me to a simple,
> fast RRNG function to generate random ints
> within a specified range?
I use 2 different 32 bit prng's.
1 The fast one
2 The good one
Both of them are used here:
http://www.mindspring.com/~pfilandr/C/q_sort/q_sort.c
This is the fast one:
#define LU_RAND_SEED 123456789LU
#define LU_RAND(S) ((S) * 69069 + 362437 & 0XFFFFFFFFLU)
It is used in the qrsort function.
This is the good one:
#define SEED_RAND 123456789
#define SEED_0 0
#define SEED_1 SEED_RAND
#define SEED_2 362436069
#define SEED_3 521288629
#define SEED_4 88675123
#define SEED_5 886756453
#define SEEDS {SEED_0, SEED_1, SEED_2, \
SEED_3, SEED_4, SEED_5}
#define LUS_RAND(S) \
(S[0] = S[1] ^ S[1] >> 7, \
S[1] = S[2], \
S[2] = S[3], \
S[3] = S[4], \
S[4] = S[5], \
S[5] = (S[5] ^ S[5] << 6 \
^ S[0] ^ S[0] << 13) & 0xffffffff, \
S[5] * (S[2] + S[2] + 1) & 0xffffffff)
It is used in the main function.
There's also the example described in the standard:
static unsigned long int next = 1;
int rand(void) // RAND_MAX assumed to be 32767
{
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}
void srand(unsigned int seed)
{
next = seed;
}
--
pete
pete
>
> In article <fs057r$7rd$1...@aioe.org>,
> jacob navia <ja...@nospam.org> wrote:
>
> >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
CBFalconer
>
... 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.
pete
>
> 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?
Because, ...
> register is still a reserved word. All it is guaranteed
> to do is prevent taking the address. Although it seems totally
> ridiculous here.
... I can't imagine that there ever might be
a situation where I would want to prevent taking the address.
--
pete
Walter Roberson
pete <pfi...@mindspring.com> wrote:
>CBFalconer wrote:
>> register is still a reserved word. All it is guaranteed
>> to do is prevent taking the address. Although it seems totally
>> ridiculous here.
>... I can't imagine that there ever might be
>a situation where I would want to prevent taking the address.
It becomes an optimization hint to a compiler: if there are
pointers in the code, the optimizer can know that none of them
point to the object declared as 'register', which fact might
allow it to use tighter code in some cases.
--
"Eightly percent of the people in the world are fools and the
rest of us are in danger of contamination." -- Walter Matthau
Keith Thompson
> In article <47EDA1...@mindspring.com>,
> pete <pfi...@mindspring.com> wrote:
>>CBFalconer wrote:
>
>>> register is still a reserved word. All it is guaranteed
>>> to do is prevent taking the address. Although it seems totally
>>> ridiculous here.
>
>>... I can't imagine that there ever might be
>>a situation where I would want to prevent taking the address.
>
> It becomes an optimization hint to a compiler: if there are
> pointers in the code, the optimizer can know that none of them
> point to the object declared as 'register', which fact might
> allow it to use tighter code in some cases.
On the other hand, since "register" can only be applied an object
declared inside a function, an optimizing compiler probably already
knows that the object's address is never taken.
On the other other hand, the code in question was published in 1988;
at the time, "register" might well have been useful as an optimization
hint.
--
Keith Thompson (The_Other_Keith) <ks...@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
pete
>
> In article <47EDA1...@mindspring.com>,
> pete <pfi...@mindspring.com> wrote:
> >CBFalconer wrote:
>
> >> register is still a reserved word. All it is guaranteed
> >> to do is prevent taking the address. Although it seems totally
> >> ridiculous here.
>
> >... I can't imagine that there ever might be
> >a situation where I would want to prevent taking the address.
>
> It becomes an optimization hint to a compiler: if there are
> pointers in the code, the optimizer can know that none of them
> point to the object declared as 'register', which fact might
> allow it to use tighter code in some cases.
Is that something that you've done for that reason,
or is that an example of something that you can imagine
that I can't?
--
pete
Richard Tobin
Walter Roberson <robe...@ibd.nrc-cnrc.gc.ca> wrote:
>It becomes an optimization hint to a compiler: if there are
>pointers in the code, the optimizer can know that none of them
>point to the object declared as 'register'
I would have thought most compilers would be able to tell whether
the address of a variable is taken, so that this hint doesn't
provide any information they don't already have.
-- Richard
--
:wq
Richard
> In article <47EDA1...@mindspring.com>,
> pete <pfi...@mindspring.com> wrote:
>>CBFalconer wrote:
>
>>> register is still a reserved word. All it is guaranteed
>>> to do is prevent taking the address. Although it seems totally
>>> ridiculous here.
>
>>... I can't imagine that there ever might be
>>a situation where I would want to prevent taking the address.
>
> It becomes an optimization hint to a compiler: if there are
> pointers in the code, the optimizer can know that none of them
> point to the object declared as 'register', which fact might
> allow it to use tighter code in some cases.
Sounds strange.