Tuesday, 31 July 2012

Generating random numbers

One thing that is always difficult in a system is generating a truly random number.  Computers aren't random, they're very logical, therefore this is inherently difficult.  Having said that, there's always a way to calculate a number which is "random enough".  There is no function for this in Uniface, so I'm going to look at a few different ways to achieve this.

1) perform - the only way we could find to do this originally was to build a random number function in C++ and then call out to it from our Uniface program.  Something like this...

  perform "GetRandomNumber" ;call 3gl function which returns 0-32767
  rand = $1 / 32767

2) $uuid - since the Uniface Unique Identifer function was added, this has given an alternative method.  This is largely based on the current timestamp and either includes the processor ID or the ethernet address, depending on the operating system you are using.  The value returned is a 32 character hexadecimal string, so we need to remove the non-numeric characters.  

  rand = "0.%%$replace($replace($uuid,1,'&',"",-1),1,"-","",-1)%%%" * 1

We actually found that this was not random enough on non-Windows systems, as the last part of the identifier is the same throughout each transaction, so we have used characters from 3 identifiers.

3) DIY - you could also create your own random number generator, after all, these are just mathematical formulas.  The C++ "rand" function that we utilise in method (1) is a simple Linear Congruential Generator.  This takes an initial seed value and then uses it to create the next number in the sequence, which is then used as the seed for the next number.  The key is finding a combination of values that gives an evenly distributed spread of numbers, to ensure that the numbers appear suitably random.

  $$rand = ((214013 * $$rand) + 2531011) % 4294967296
  rand = $$rand / 4294967296

As you can see, this relies on the seed value already being populated, which I've stored in a global register in this example.  This could be set in the application shell execute trigger, maybe using $uuid or a time based numeric.  

Often these algorithms return a subset of the bits in order to improve the spread, but it is not possible to do extraction at the bit level in Uniface, as far as I'm aware.  Another algorithm that is popular (and generally considered better) is a Mersenne Twister, but this uses bit-shifting techniques that I don't think are possible in Uniface either.

So let's test the performance of these different methods of 2,000,000 iterations...

1) perform = 00:10.00, 00:10.00, 00:10.01 (10 seconds)
2) $uuid = 00:32.31, 00:32.44, 00:32.39 (over 32 seconds)
3) DIY = 00:34.75, 00:34.72, 00:34.72 (under 35 seconds)

As you can see, the original perform is the quickest method (although we've found that generally using a 3GL function does not hold up very well under load and these tests are only as a single user).  It can be hard to support a 3GL function across multiple platforms, but this solution is mathematically the most random method.  Out of the alternatives, $$uuid is quite simple but does not give a good spread of random numbers, not compared with the DIY method.  

It should be emphasised that none of these methods are truly random, and therefore should not be used for cryptographic purposes.  They should be suitable for simple things though, like simulating a dice throw.

Hopefully one day Uniface will provide it's own $rand or $random function - a native function should perform the best and would hopefully be implemented in a way that was suitably random with a decent spread.

Summary: If it's feasible to use a perform then this is the best way to go, both for speed and randomness.  However, you may wish to consider building your own random number generator, possibly using a Linear Congruential algorithm.

No comments:

Post a Comment