Hi, Gary.

At 5/1/99 07:47 PM , Gary L. Biggs wrote:
>I need to generate a good random number in an ALLBASE/SQL Stored procedure.
>I need a Session ID for an IMAGE/SQL transaction that originates from the
>web. I can't call the normal MPE functions from ALLBASE, so I have to 'roll
>my own'. If anyone has a source for an algorithm that uses only a time
>function, a looping construct (if then : goto and/or DO While) and simple
>math to generate a random number, I'd sure appreciate a look at the logic
>(any language will do).

I went looking in a couple of books for random number generators since (like
encryption) it's harder to generate a relatively random sequence of numbers
than it often seems.  Thinking about the algorithms I found in the context of
the environment you will be using them (SQL stored procedures, about which I
admittedly know little) had me first wondering what resources you would
have...  for example, whether there is persistent storage available for holding
the intermediate results of one calculation for use in the next.  Without the
ability to store at least a little data, or a timer with a resolution higher
than the maximum rate you will ever assign these session IDs, or some other
number supplying function of high enough resolution to be sure there is no
duplication, I believe there's no way to generate a sequence that's not going
to duplicate numbers.

I then realized that you don't seem to actually need a random sequence of
numbers, only a sequence that doesn't duplicate numbers for a long period.  The
ideal solution for that purpose would be a simple integer counter.  It will
have a period that matches the maximum value which can be stored and used which
is at least as long as the maximum possible random sequence.

If you think you need a random number to obfuscate knowledge of what session
IDs are recently used or soon to be used, then scramble the bits in the counter
a bit...  perhaps simply rotating the bits by some fixed offset.  For example,
if a period of 4 billion unique values is sufficient, then a 32 bit integer can
be used.  There can't be any duplication until the counter wraps.  That's true
even if you swap the first 16 bits with the last 16 bits before use, swap bytes
1 for 4 and 2 for 3, reverse the bits end to end or otherwise scramble the
value without dropping any bits.

Simply incrementing a counter and rotating the bits a bit will be faster and
simpler than most any random number generator worth the effort to code and
should provide you with a longer period of unique values.  If you need a bigger
ID use 64 bits, either through a single storage location or concatenating two
32 bit integers.  If you increment one each time, use it as the first 32 bits
and only increment the last 32 bit value when the first wraps to zero, then you
will have a sequence of unique values that change by 4 billion and some, and
has a period of 2^64, which is more than 18 quintillion...  That's
18,446,744,073,709,551,616  which at a rate of 1000 session IDs a second, every
second, 24 hours a day, 365.25 days a year would last *half a billion*
(actually 584,542,046) *years* before it duplicated values.  By the time that
duplicates, I think we can safely assume it will be someone else's problem.
;)  They might have to handle the "64bit bug crisis" and go to 128 bit
integers, though 96 bits would make the period 2.5 quintillion (that is 25 with
17 zeroes after it) years at that same 1000 IDs a second, though by then the
IDs may be needed faster than that.  :)

A 32 bit integer at the same 1000 IDs per second rate would last only 49.7 days
before duplicating.  If you use a 32 bit or smaller value you will probably
want to make sure that any value assigned can't be still in use, perhaps by
expiring them based on date stamp, if the session ID is more than a month old,
then it's invalid as it may be duplicated.  Choose the expiration period
according to what size value you are using and how fast you are might ever
allocate them.  That will require that you date stamp the session in addition
to assigning a session ID, but that could be part of the same session ID if
desired.  Another way to look at the calculations above is that 32 bit values
will last for at least 24 hours unless the average rate exceeds 49,700
increments per second.

That's a lot of web transactions these days... even for a 3000.  :)
--
Jeff Woods
[log in to unmask]  [PGP key available here via finger]