1

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

Grant Peters
  • 7,691
  • 3
  • 45
  • 57

9 Answers9

4

GUIDs? Many environments have support for generating these.

DanDan
  • 10,462
  • 8
  • 53
  • 69
0

I'm not sure I got you right, but if you're on a Linux box, you can read from /dev/urandom to get a stream of high quality random numbers. These numbers can be used to produce any length string you need. Keep in mind that for this solution to work, the machine should receive input from the user (keyboard/mouse).

Moshe
  • 2,638
  • 2
  • 28
  • 32
0

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.

Nelson
  • 27,541
  • 5
  • 35
  • 31
  • 1
    But these a generally way to slow, plus I don't need it to be a high quality random, just random enough. Also, I'm working in c++, in which the only standard algorithm is 'rand()' which is broken on many platforms and can be very slow. – Grant Peters Aug 12 '09 at 14:11
  • 4
    "The best algorithm for your PRNG is whatever library your programming language already provides." - That one is so wrong it's not even funny. You can refer to basically every single source on PRNGs to make sure. – Michael Foukarakis Aug 28 '09 at 11:07
0

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 ?

MSalters
  • 173,980
  • 10
  • 155
  • 350
-1

This might work:

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

Daren Thomas
  • 67,947
  • 40
  • 154
  • 200
  • That a good idea, didn't really think of using things like the thread id. Although this isn't available on all platforms, i should be able to grab a fair bit of random data from variables that are scattered around the system (such as current scan-line number and values grabbed from simplistic stack walks). – Grant Peters Aug 12 '09 at 14:15
  • 1
    This is sort of a terrible answer because it will mostly be a sequential stream (the time won't necessarily change, and I don't see why the thread id would be changing at all) – Steven Lu Feb 17 '14 at 21:04
  • @StevenLu, I agree. That was a terrible answer! I don't even remember writing that... – Daren Thomas Feb 21 '14 at 08:45
-1

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

-1

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.

Community
  • 1
  • 1
ConcernedOfTunbridgeWells
  • 64,444
  • 15
  • 143
  • 197
-1

Try this. Courtesy of George Marsaglia.

Can't argue with 2 billion random numbers per second.

Steven Lu
  • 41,389
  • 58
  • 210
  • 364
  • Yeah, that would be great if I only had to deal with SSE capable processors. Unfortunately I deal with x86 (many of them rather trimmed down to bare minimum features), PowerPC, Arm, MIPS and Cell processors (and a few others on occasion). – Grant Peters Feb 20 '14 at 03:15
  • Just use one of the less-optimized Marsaglia RNGs, then. – Steven Lu Feb 20 '14 at 09:28
-1

if the problem is that some objects or threads are generating the same ids as other objects or threads, consider padding those ids with say 10k reserved children ids.

if youre generating random ids from the previous id, its going to be the same problem because prngs are deterministic. ie id 25653 will always generate id 7567832 next. always.

you might consider only using the prng for non standard id generation like objects that generate ids. like observe under what conditions these clashes occur and fix those cases with a prng. the rest can safely be sequential, probably.

Bad Radish
  • 111
  • 1
  • 2