Generation of Unique Numbers
Author
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
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
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
Author
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
Spree
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:
CJM
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
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
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
What about semi-sequential?
Generated numbers:
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 unsigned int dvalue = 0x10000000; value += dvalue; if ( value < dvalue ) //number wrapped { ++value; //offset by one }}Generated numbers:
0x100000000x200000000x30000000...0xF00000000x100000010x200000010x30000001...0xF00000010x100000020x200000020x30000002...0xF0000002Exactly 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< unsigned int , 8 > d_table = { //12345678 0x10000000 , 0x00001000 , 0x00100000 , 0x00000010 , 0x01000000 , 0x00010000 , 0x00000100 , 0x00000001 }; const boost::array< unsigned int , 8 > mask_table = { 0xFFFFFFFF , 0x0000FFFF , 0x00FFFFFF , 0x000000FF , 0x0FFFFFFF , 0x000FFFFF , 0x00000FFF , 0x0000000F }; while ( mask ) { for ( int i = 0 ; i < 8 ; ++i ) { unsigned int d = d_table;<br> <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> mask = mask_table;<br><br> <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> original_masked_value = value & mask;<br> value += d;<br> <span class="cpp-keyword">if</span> ( value & mask &gt; (original_masked_value) ) <span class="cpp-keyword">break</span>;<br> <br> }<br> }<br>}<br></pre></div><!–ENDSCRIPT–><br><br>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:<br><br>0x12345678 –> 0x84637251<br><br>(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:<br><br><!–STARTSCRIPT–><!–source lang="cpp"–><div class="source"><pre> <span class="cpp-keyword">const</span> boost::array&lt; <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> , <span class="cpp-number">8</span> &gt; d_table = {<br> <span class="cpp-comment">//12345678</span><br> 0x10000000 ,<br> 0x01000000 ,<br> 0x00100000 ,<br> 0x00010000 ,<br> 0x00001000 ,<br> 0x00000100 ,<br> 0x00000010 ,<br> 0x00000001 };<br> <span class="cpp-keyword">const</span> boost::array&lt; <span class="cpp-keyword">unsigned</span> <span class="cpp-keyword">int</span> , <span class="cpp-number">8</span> &gt; mask_table = {<br> 0xFFFFFFFF ,<br> 0x0FFFFFFF ,<br> 0x00FFFFFF ,<br> 0x000FFFFF ,<br> 0x0000FFFF ,<br> 0x00000FFF ,<br> 0x000000FF ,<br> 0x0000000F };<br></pre></div><!–ENDSCRIPT–> for i from 1 to n: r = F(i)where F(x) is the AES function, the MD5 function, the SHA-1 function, etc.
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).
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
