deancoo wrote:
You see, the key that's generated has a large range, but is very disjointed.
There are about 2.6M elements in a range as large as aprox. 4.7B. The key
generator is super simple and super fast, so I don't want to change it. The
only drawback, of course, is how disjointed the keys are, requiring a large
container to hold them. When I said that the key maintains its uniqueness,
what I meant was that even when the key generator produces a number in
excess of 2^32, the resultant number stays unique compared to all other
generated keys. So really, is it so bad to use this overflowed data type?
Remember, I said finite set of data, and I've verified each possible key.
If I understand you correctly, you are saying that the key generator
generates keys that have a dynamic range of zero to 4.7 billion.
If this is correct you need a 33 bit unsigned integer to store the
keys without discarding any bits of key data.
ln(4.7x10^9)/ln(2) = 32.130013610776536155133366190146
or
2^32.130013610776536155133366190146 == 4.7 x 10^9
But since the number of keys generated is small you think you can
"risk it" and use the "overflowed data type".
The obvious problem is that unless your key generator prevents it
somehow there is a finite probability that multiple valid keys
will map to the same "overflowed data" value.
The only way your key generator could prevent that is if there
were key ranges that were illegal for some reason. As an example
if your key generator only produced even number keys that would
reduce the randomness of the key generation by 1 bit so you could
simply store key/2 in a 32 bit unsigned variable.
If your key generation algorithm really requires 33 bits of storage
it would be foolish to try to store it in 32 bits. You would be laying
the groundwork for a bug that only surfaces once in a while. You can
calculate the probabilities based on the number of keys generated.
I hate trying to debug problems that only happen once in a while,
I would much rather debug a repeatable bug. Just my 2 cents.
knock 2 bits of randomness off of the key generation.
In the example provided although the key could require 33 bits