What is a good, fast PRNG (non-cryptographically s

Question

I'm looking for a fast PRNG so that I can quickly create (semi)unique IDs for objects. The uniqueness is more of a management problem and ID duplication is only a problem in extremely rare circumstances.

It must be as fast as possible, as performance is critical, and non-sequential (if the IDs are sequential, it makes it more likely that an error on the management side can occur). Also, I'd like to avoid lower numbers, but this can easily be mitigated by just retrying until a sufficiently high number has been retrieved.

Edit I should also add that I require the IDs to be 32bit, thus GUIDs don't work and needs to be platform independent (currently being implemented on PC, but also needs to work on Nintendo DS, PSP, PS3, Wii, Xbox and other platforms). Also, it may be called thousands of times per second, hence, input based random number generation isn't feasible.

Thanks

Answer 1

See: http://www.number.com.pt/index.html

Answer 2

Fishman and Moore wrote a paper about Linear Congruential PRNGs (A(x) = A(x-1)|m). This posting on Stackoverflow discusses this algorithm. If your platforms can all support a 64 bit accumulator for intermediate results (64 bit long long variables should be supported on all modern C compilers) then this is simple and fast, with a period of 2^30 with M = 2^31-1. The posting linked above has some good values of A from Fishman and Moore's paper.

Answer 3

If you really need just the non-sequential part, what's wrong with X[i] = (X[i-1] + a) mod b ? If a and b are co-primes, this will repeat with period b. That makes b=2^32 an easy choice, while a can be any prime > 2. Performance would be measured in MHz, not KHz.

Avoiding lower numbers is also simple: use a sequence X[i] = offset + (X[i-1] - offset + a) mod b ?

Answer 4

GUIDs? Many environments have support for generating these.

Answer 5

The best algorithm for your PRNG is whatever library your programming language already provides. It will have a well tested algorithm, and will probably be smart about using existing sources of randomness in your computer like /dev/random.

If you want "low numbers", don't just retry until you get one; that will take forever. Simply take the random number and mod it by your ceiling. Ie:

random() % 1000000

returns a random number between 0 and 999,999.

Answer 6

This might work:

Sum of current time since epoch, thread id and a sequential number.