Jump to content
  • Advertisement
Sign in to follow this  
SpreeTree

Generation of Unique Numbers

This topic is 4753 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Im looking for a quick way to generate a large set of 32bit unique numbers (sequential or non-sequential, it isn't important) with a low (but not impossible) chance of them being absolutly unique. The examples I have found so far have been through the use of random number generation, which I am trying to avoid, as when the code is executed, my random num generator may, or may not have been, seeded. Is anyone aware of any methods that don't use random number generation, maybe through the use of the time/date/tick count etc. probably with a heavy dose of shifting? Any help would be appreciated Spree

Share this post


Link to post
Share on other sites
Advertisement
If you can't guarantee the code will have an initialization section ran (seeding for a PRNG or whatever else for any other system), I'm fairly certain it isn't possible.
If you can expand the size of your unique ID and you're doing it only for windows, you could use CoCreateGuid in ole32.dll

Share this post


Link to post
Share on other sites
Technically, they can be sequential, this will not break anything. But it would be much more efficent if they were not, and so I am more inclined to look for non-sequential numbers.

Spree

Share this post


Link to post
Share on other sites
Hmmm,

Write a PRNG class that seeds itself automatically on creation, or seeds itself into a static. That way whenever you use it, you'll get PRNGs that are valid.

Or, assuming that you need generation between sessions, go sequential where you have something like:

class IDGen
{
public:
IDGen();
~IDGen();

int Generate();

static int refCount=0;
static int currentID=0; //overwritten in constructor
};

IDGen::IDGen()
{
if (refCount<=0)
{
//load a file with your last generated number
fopen(filename, etc, etc.);

//currentID = last generated number
currentID=NumFromFile();

refCount=1;
}else
{
refCount++;
}
}

IDGen::~IDGen()
{
refCount--;

if (refCount<=0)
{
//save a file with your last generated number + 1
}
}

int IDGen::Generate()
{
return currentID;
currentID++;
}




CJM

Share this post


Link to post
Share on other sites
Hey,

Or do the same as above with a PRNG, like the linear congruential one which goes through all of the 32 bit unsigned numbers.

CJM

Share this post


Link to post
Share on other sites
What about semi-sequential?

unsigned int gen_num( void )
{
static unsigned int value = 0;
const unsigned int dvalue = 0x10000000;

value += dvalue;
if ( value &lt; dvalue ) //number wrapped
{
++value;
//offset by one
}
}


Generated numbers:

0x10000000
0x20000000
0x30000000
...
0xF0000000
0x10000001
0x20000001
0x30000001
...
0xF0000001
0x10000002
0x20000002
0x30000002
...
0xF0000002


Exactly what would preform better with non-sequential values? What I'm looking for is, is there a specific pattern that's in need of avoidance?

One could expand on this shown pattern further, farther tumbling the numbers:

unsigned int gen_num( void )
{
static unsigned int value = 0;
const boost::array&lt; unsigned int , 8 &gt; d_table = {
//12345678
0x10000000 ,
0x00001000 ,
0x00100000 ,
0x00000010 ,
0x01000000 ,
0x00010000 ,
0x00000100 ,
0x00000001 };
const boost::array&lt; unsigned int , 8 &gt; mask_table = {
0xFFFFFFFF ,
0x0000FFFF ,
0x00FFFFFF ,
0x000000FF ,
0x0FFFFFFF ,
0x000FFFFF ,
0x00000FFF ,
0x0000000F };

while ( mask )
{
for ( int i = 0 ; i &lt; 8 ; ++i )
{
unsigned int d = d_table[ i ];
unsigned int mask = mask_table[ i ];

unsigned int original_masked_value = value & mask;
value += d;
if ( value & mask &gt; (original_masked_value) ) break;

}
}
}


Note: this is in effect just scrambling the digits of a sequential number in a fixed pattern. It's really a convoluted way of convering a number like so:

0x12345678 --> 0x84637251

(that is, on the 0x12345678th run of gen_num, it will return 0x84637251. Depending on your situation 0x87654321 may be better suited. For that you'd simply change the tables:

    const boost::array&lt; unsigned int , 8 &gt; d_table = {
//12345678
0x10000000 ,
0x01000000 ,
0x00100000 ,
0x00010000 ,
0x00001000 ,
0x00000100 ,
0x00000010 ,
0x00000001 };
const boost::array&lt; unsigned int , 8 &gt; mask_table = {
0xFFFFFFFF ,
0x0FFFFFFF ,
0x00FFFFFF ,
0x000FFFFF ,
0x0000FFFF ,
0x00000FFF ,
0x000000FF ,
0x0000000F };

Share this post


Link to post
Share on other sites

for i from 1 to n:
r = F(i)


where F(x) is the AES function, the MD5 function, the SHA-1 function, etc.

Share this post


Link to post
Share on other sites
Actually, theres a really simple way. I just toyed with the code myself and it works great if you want weird patterns (as opposed to extreme pseudorandomness).

static int seq_run = 0;
int seq()
{
return ((seq_run++) ^ 0x55555555);
}
void seq_seed( int i )
{
seq_run = i;
}


If you change the 0x55555555 to something else, you get a different pattern.
For instance, if you do 0xffffffff, you get a sequence starting with 4.2 billion and counting backwards.

Over the full range of numbers, you'll get every number just once. For some gaming, these type of generators may work for some stuff, but like I said, they're all very patternistic.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!