simple PRNG?

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

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.

Mar 21 '08 #6

Noob

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

Richard Tobin

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

Richard Tobin

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

"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

Ben Bacarisse

"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

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

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

Morris Dovey

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

CBFalconer

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

Bartc

"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

Ben Pfaff

"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

user923005

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

santosh

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