simple PRNG?

[copx]

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

[snip]

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

 

[Antoninus Twink]

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

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

static unsigned long x=2282008, y=362436069;

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


/* example main() should generate 10^9 integers in ~5 seconds,
with final j=1105441147. Try it.
*/

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

------------------- C code ends ------------------------

Looks good! I would like to use that, but..

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

If float operations must be avoided, and you want a random integer
from 0 to n-1, you can mask off bits after invoking sK, so that enough
remain to provide your integer, rejecting those outside the range.
For example, a random integer k in 0<=k<12345 needs 14 bits,
so generate
k=(sK>>18);
and keep those for which k<12345.

I have to admit, that I do not really understand this. (just a hobby coder
here, almost no experience with bit level data manipulation)

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

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

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:

[snip]

Thanks!

 

[Noob]

[snip PRNG code and insightful comments]

It's great to have you post to this group again.

Regards.

 

[Chris Torek]

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

static unsigned long x=2282008, y=362436069;

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

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

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

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

[% I am not sure whether extra retained bits in x and/or y are a
problem. If they are, add more masks with 0xffffffffUL. Again,
the generated code should be the same wherever the masks are a
no-op, as on any machine with 32-bit "unsigned long". Alternatively,
one could use "uint32_t" on C99 systems, but masking is completely
portable, even to C89-only systems.]

 

[Thad Smith]

/* 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 \

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

 

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

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.

 

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

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.

 

[Walter Roberson]

CBFalconer wrote:

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

 

[Keith Thompson]

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.

 

[pete]

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?

 

[Richard Tobin]

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

 

[Richard]

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.