Re: Generating random unique alphanumeric IDs

On 2009-08-17, Sam Mason <sam(at)samason(dot)me(dot)uk> wrote:
> On Sun, Aug 16, 2009 at 04:53:01PM -0600, Bob Gobeille wrote:
>> One way is to use a LFSR (linear feedback shift register function). I
>> haven't used one in a long time but I recall generating pseudo random
>> numbers that are guaranteed not to repeat after billions of
>> iterations. It's very fast as well. Then translate the resulting
>> integer into the character sequence of your choosing. Here is a
>> reference: http://en.wikipedia.org/wiki/Linear_feedback_shift_register
>
> Not sure if this is very applicable; LFSRs can have a very long period,
> or interval before they repeat

ideally (2^n)-1

(i.e. their internal state is the same as
> it was before) but individual numbers *will* be repeated.

numbers will not be repeated intil the state wraps if the number
returned represents the entire state of the LFSR.

for the OP's problem this means building a LFSR with n=5c (where c is
the number of charactes in the serial code, and n is the number of bits in
the LFSR state) and then taking a single LFSR result and peeling off 5
bits at a time and using each 5 to make each charcter in the result.

(or anternately clocking c 5 bit numbers out of the LFSR) for each
result.

> The performance claims tend only to apply to hardware implementations,
> there are much faster pseudo-random number generators available for
> software. The fastest one I found recently is a SIMD implementation of
> the "Mersenne Twister" called SFMT[1].

LFSR can be optimised using look-up tables same as CRC32 is (CRC32 is an
LFSR with an input as well as an output)

MT is too big (too much state), linear congrutential is probably a better
approach when a software generated non-revisiting sequence is wanted.
for good results use a prime m less than 32^c and an r near sqrt(32^c)