simple PRNG?

C

copx

Can anyone point me to a simple, fast RRNG function to generate random ints
within a specified range? It is important that each value within the range
has the same probability (uniform distribution).
I do not want to use the unreliable rand() function, but I do not want to
bloat my code with something as complex as MT either. I am just looking for
a short code snippet that I can copy without worrying about licensing.
The function should work on limited platforms (no floating-point math
please, one that works even on platforms where int is only 16 bit would be
perfect).
I did search this group and the web but I could not find anything which
meets the requirements.
 
M

Morris Dovey

copx said:
Can anyone point me to a simple, fast RRNG function to generate random ints
within a specified range? It is important that each value within the range
has the same probability (uniform distribution).
I do not want to use the unreliable rand() function, but I do not want to
bloat my code with something as complex as MT either. I am just looking for
a short code snippet that I can copy without worrying about licensing.
The function should work on limited platforms (no floating-point math
please, one that works even on platforms where int is only 16 bit would be
perfect).
I did search this group and the web but I could not find anything which
meets the requirements.

How simple, how fast, and how short do you require?
 
C

copx

Morris Dovey said:
How simple, how fast, and how short do you require?

Not more than a page of code would be nice (with "simple" I meant little
code, not necessary easy to understand code). Fast means that the algorithm
should be able to generate hundreds of random numbers per second on a 80386
level machine at least. Of course, 10,000 numbers per second on a 8086 are
even better! ;)
 
R

Richard Heathfield

copx said:
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! ;)

/* 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.
 
C

copx

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

Morris Dovey

copx said:
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! ;)

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

Richard Heathfield

copx said:
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.

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

jacob navia

copx said:
"Richard Heathfield" <[email protected]> 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.

Paying someone for about 20 lines of code?


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
 
W

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,

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

Richard Heathfield

jacob navia said:

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.

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

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

Richard Bos

copx said:
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
 
N

Noob

copx said:
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_congruential_generator

They have several drawbacks, but they are very simple to program.
 
J

jacob navia

Walter said:
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,

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

jacob navia

Richard said:
jacob navia said:



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.



Yes, it can. Unfortunately, this gives the result 32767 on every call.

I said "ported". Not just copied
 
R

Richard Heathfield

jacob navia said:

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*?
 
R

Richard Tobin

Walter Roberson said:
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top