🔒 Locked

Random Number

Started by maya18222 Apr 23, 2009 at 7:48 AM 17 replies 2.2k views

Original Post

Apr 23, 2009 at 7:48 AM

Hi, I need a random number between 0 and max_int (32bit) which i'll be using for IDs, but rand() only seems to return 16bit ints on my platform, (Visual Studio). SO im only get upto ~32k, an i need more than 32k ids. Ive come up with this solution. Any thoughts?


	//RAND_MAX
	srand(time(NULL));
	const int NumParticles = 20000;
	
	struct Particle
	{
		unsigned int ID;
		float x,y;
	};

	int Copies = 0;
	for(int Iterations = 0; Iterations < 50; ++Iterations){
		Particle* Particles = new Particle [NumParticles];

		for(int i = 0; i < NumParticles; ++i){
			unsigned int Total = 0;
			short int* Byte1 = (short int*)&Total
			short int* Byte3 = Byte1++;

			(*Byte1) = rand();
			(*Byte3) = rand();

			for(int k = 0; k < NumParticles; ++k){
				if(Particles[k].ID == Total)
					Copies++;
			}

			Particles.ID = Total;
		}

		unsigned int Lowest = std::numeric_limits<unsigned int>::max();
		unsigned int Highest = std::numeric_limits<unsigned int>::min();

		for(int i = 0; i < NumParticles; ++i){
			if(Particles.ID < Lowest)
				Lowest = Particles.ID;
			if(Particles.ID > Highest)
				Highest = Particles.ID;
		}

		cout << "Highest : " << Highest << " " << "Lowest : " << Lowest << " " << "Copies : " << Copies << endl;
		cout << endl << endl;
	}

Im also wondering how i can get unique IDs. When testing this method, i found that it was very rare that i did indeed get copies, but alas, they still occurred.

Hodgman

Mod

5,991

Hodgman

Apr 23, 2009 at 8:10 AM

Assuming rand returns only 16 bits, your code should be fine. If you don't want to muck about with pointers though, you can do this:

var = (rand()<<16)+rand();

If you want unique IDs, you're better off not using a random number...

static int next_id = 0;int id = next_id++;

Otherwise if you want random unique IDs, look up GUIDs.

nobodynews

156

nobodynews

Apr 23, 2009 at 8:19 AM

Why do the IDs need to be random? If they just need to be unique, simply use a counter and hand out IDs in number order.

Otherwise you could just check for duplicate IDs. If you detect one, get another random ID. Repeat until you get a non-duplicate ID. You will need a way to find already used IDs. If you don't care about the memory usage (32k integers isn't that much, but if you needed billions then this won't work) you could just store the existing IDs in some sort of container. I think std::set would work well.

There are probably other solutions as well, but I hope this was helpful.

SiCrane

Mod

473

SiCrane

Apr 23, 2009 at 8:20 AM

One small detail: MSVC's rand() actually returns a number from 0 to 0x7fff, which means you aren't getting 16 bits of randomness; you're only getting 15.

maya18222

Author

maya18222

Apr 23, 2009 at 8:38 AM

Thanks guys;

The ids need to be random as im using them as seeds. Checking for unique ids is out of the question as thosuands of particles are being created and dieing every second. I cant use a counter as that would produce a noticeable sequence in their behaviour. I'll try std::set, and see how much of a performance hit it would be.

Quote:
One small detail: MSVC's rand() actually returns a number from 0 to 0x7fff, which means you aren't getting 16 bits of randomness; you're only getting 15.

But that last bit is just the signed bit right? so it means that my value will always be:

0 rand() rand() rand() rand() rand() rand() rand() - rand() rand() rand() rand() rand() rand() rand() rand()

0 rand() rand() rand() rand() rand() rand() rand() - rand() rand() rand() rand() rand() rand() rand() rand()

so that means im going to loose the 32768 bit

32768 16384 8192 4096, 2048 1024 512 256 - 128 64 32 16, 8 4 2 1

so im going to need to randomise that from 0 - 1 too then.

Im not concerned about the very first signed bit. Actually come to think of it, i dont think its going to matter. Loosing that subsection should have an affect on the amount of IDs i need

Hodgman

Mod

5,991

Hodgman

Apr 23, 2009 at 8:45 AM

typedef unsigned int uint32;uint32 r15 = rand();//fill first 15 bitsuint32 r30 = (rand()<<15) | r15;//fill next 15 bitsuint32 r32 = (rand()<<30) | r30;//fill last 2 bits

maya18222

Author

maya18222

Apr 23, 2009 at 8:50 AM

Thanks

alvaro

1,980

alvaro

Apr 23, 2009 at 9:44 AM

Quote:
Original post by maya18222
The ids need to be random as im using them as seeds. Checking for unique ids is out of the question as thosuands of particles are being created and dieing every second. I cant use a counter as that would produce a noticeable sequence in their behaviour.

Why do you think consecutive seeds won't produce different enough behaviors? If you are seeding a decent pseudo-random number generator, it's probably OK to start with similar numbers. If you do observe similar behavior, let's discuss better options for the pseudo-random number generator you are using for your particles.

maya18222

Author

maya18222

Apr 23, 2009 at 11:50 AM

Becuase the system sends particles through a number of nodes in order. like so

scale
direction
etc
etc

And the particles get passed through these nodes each frame. So if the direction node just gives a random direction, it will be different every frame. I dont want that, i want it random, but the same random direction for that particle each frame, unless the node itself is reseeded.

I do this by using the partiles ID to get some random direction. As if the ID is some random number, i can just get a direction from this, by mapping the id units from -1 to 1. So as long as the id stays the same, its random direction will too. If the Ids are consecutive, the directions will be too, and it wont look random when viewing all the particles.

If you know a better way, that would be great.

nobodynews

156

nobodynews

Apr 23, 2009 at 12:04 PM

Sure. Just manipulate the ID the same way rand manipulates the seed. "hash" the IDs. For 16bit IDs consider something like this (modify for more bits as needed):

class Particle{  unsigned int ID;public:  Particle(unsigned int ID) : ID(ID) {}  float direction()  {    // hash the ID, convert to the range -1 to 1    return ((ID * 214013L + 2531011L) >> 16) & 0x7fff) / 32768.0f - 1.0f;  }};

maya18222

Author

maya18222

Apr 23, 2009 at 1:06 PM

hmm, that code didnt work for me, it just up in sequence by 3. Am i doing something wrong?

	for(int h = 0; h < 100; ++h){			unsigned int ID = h;			ID = ID * 214013L + 2531011L;			ID = ID >> 16;			ID = ID & 0x7fff;			cout << ID;		}

AshleysBrain

Apr 23, 2009 at 3:25 PM

Look up the Mersenne Twister algorithm for a faster, 32 bit random number algorithm.

nobodynews

156

nobodynews

Apr 23, 2009 at 3:57 PM

No, that generator just sucks, apparently. I looked around and stole this one called the Park Miller:

#include <iostream>long hashID(long ID){    const long PARK_MILLER_A = 16807L;    const long PARK_MILLER_M = 2147483647L;    const long PARK_MILLER_Q = 127773L;    const long PARK_MILLER_R = 2836L;    long hi = ID / PARK_MILLER_Q;    long lo = ID % PARK_MILLER_Q;    long test = PARK_MILLER_A * lo - PARK_MILLER_R * hi;    ID = (test > 0) ? test : test + PARK_MILLER_M;    return ID;}int main(){    unsigned int number_of_occurances = 0;    std::cout << "Enter the number of IDs to generate: ";    std::cin >> number_of_occurances;    for(unsigned int i = 0; i < number_of_occurances; ++i)    {        long result = hashID(i);        std::cout << result << "\n";    }}

XTAL256

110

XTAL256

Apr 23, 2009 at 6:09 PM

Quote:
Original post by maya18222
...So if the direction node just gives a random direction, it will be different every frame. I dont want that, i want it random, but the same random direction for that particle each frame, unless the node itself is reseeded.

So you are setting the rand() seed for each particle based on it's id then using that value to determine the direction, is that what you are saying? If so then why don't you just store the direction, scale, etc in each particle. When each particle is created you set the variables to some random value and then don't change those values. That way you don't even need an ID for each particle, you can just loop through each one and get it's values directly.
Check out NeHe's particle tutorial.

Wandering Relic

Apr 23, 2009 at 9:25 PM

Quote:
Original post by AshleysBrain
Look up the Mersenne Twister algorithm for a faster, 32 bit random number algorithm.

Mersenne Twister isn't bad, but there are better generators out there, especially if you need something with a lower memory foot print. Do a search for multiply and carry PRNGs. They have randomness comparable to MT. Here's my implementation of one without any of the usual convenience functions for computing random values within a specific domain, or floating point numbers, etc. As you can see, it's pretty fast (no divisions/mods like MT), and pretty much no overhead memory-wise compared to MT as you can have hundreds or thousands of these PRNGs all over the place if you need it.

class Random{public:            Random( );            Random( UInt32 seed1, UInt32 seed2 );            void Seed( ); // seed with values from the system timer            void Seed( UInt32 seed1, UInt32 seed2 );            UInt32 Next( );        private:            UInt32 NextZ( );    UInt32 NextW( );             UInt32 z_;    UInt32 w_;};            inline Random::Random( ) {    Seed( );}    inline Random::Random( UInt32 seed1, UInt32 seed2 ) {: z_( seed1 ),w_( seed2 ) {}inline void Random::Seed( UInt32 seed1, UInt32 seed2 )    z_ = seed1;    w_ = seed2;}inline UInt32 Random::NextZ( ) {    return ((z_ = 36969 * (z_ & 65535) + (z_ >> 16)) << 16);}    inline UInt32 Random::NextW( ) {    return ((w_ = 18000 * (w_ & 65535) + (w_ >> 16)) & 65535);}inline UInt32 Random::Next( ) {    return NextZ( ) + NextW( );}

XTAL256

110

XTAL256

Apr 23, 2009 at 11:03 PM

I really don't think the OP needs anything but the standard 16-bit rand() function. Even if they had more than 2^16 particles i doubt you would notice a pattern in the particles. If you have 2^32 particles then by the Pidgin Hole principle at most every particle would have the same direction as one other. But since the values are random then this could happen anyway.

@nobodynews: those constants in the algorithm you posted should probably be static.

kaisellgren

Apr 24, 2009 at 1:06 AM

None of these are random number generators... just pseudorandom sequence generators.

Have a look at assembly System.Security.Cryptography at a class called something like Random Number Generator Provider or so.

This, of course, if you want *Random* numbers.

iMalc

182

iMalc

Apr 24, 2009 at 3:55 AM

Quote:
Original post by kaisellgren
None of these are random number generators... just pseudorandom sequence generators.

Have a look at assembly System.Security.Cryptography at a class called something like Random Number Generator Provider or so.

This, of course, if you want *Random* numbers.

It's for a particle shower! - no human is going to be able to tell the difference between a mersenne twister (or a LCG for that matter) and anything "better".

You may also notice that the original poster does not appear to be using .NET, though the Window's cryptography API is just as available through native code.

maya18222

Author

maya18222

Apr 24, 2009 at 5:48 AM

Quote:
Original post by XTAL256
Quote:
Original post by maya18222
...So if the direction node just gives a random direction, it will be different every frame. I dont want that, i want it random, but the same random direction for that particle each frame, unless the node itself is reseeded.

So you are setting the rand() seed for each particle based on it's id then using that value to determine the direction, is that what you are saying? If so then why don't you just store the direction, scale, etc in each particle. When each particle is created you set the variables to some random value and then don't change those values. That way you don't even need an ID for each particle, you can just loop through each one and get it's values directly.
Check out NeHe's particle tutorial.

I cant just store them on creation. They are being changed multiple times in the system, depending on certain tests. For example i may have something like this :-

Birth
Scale
Rand Direction
if(expression)
.....do Rand Direction
.....else do Scale

So each time it gets to the 'do Rand Direction' or 'do Scale', it needs to produce the same random number each time for that one particular particle. As you can imagine, i DONT want it random each frame, it needs to just get a random number for that particle, but the same random number for that ID.

This is not for in game, so it doesnt need to be in game optimised.

Quote:
I really don't think the OP needs anything but the standard 16-bit rand() function. Even if they had more than 2^16 particles i doubt you would notice a pattern in the particles. If you have 2^32 particles then by the Pidgin Hole principle at most every particle would have the same direction as one other. But since the values are random then this could happen anyway

Having the 32bit ID is so that each particle has a unique ID. That is if i ever get that many particles :P . I managed to get 100k running at a descent frame rate, which i why i wanted to prepare for more than the 65k limit of 16bit

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.