gwen (gwenix) wrote,
gwen
gwenix

  • Mood:
  • Music:

and finally, good news from my life.



I was especially clever tonight. I am very proud of myself for this.

First, why I needed what I did. We're writing a program in my Java
class to roll 5d6 (that's five normal dice, for the non-gamers),
which means I need to call up 5 random numbers nearly simultaneously.

Well, it turns out that Java has a poorly implemented Random()
function. For the laymen, I provide some background on how
pseudo-random numbers are generated by computers. First, they take
some seed number gathered from one of a few places (I will get to
that later), and perform some extensive computational formulae on
that seed to generate a new number.

So, for instance, you could have a very simple formula of:

( (seed/2) + (seed*seed) ) / 3

The actual formulae used by the computers are going to be much more
complicated than that, but it will do for the purposes of my
explanation here. What this means is that if you have a seed of,
say, 5.. you do:

( (5/2) + (5*5) ) / 3

Which is, (2.5+25)/3, or 9.1666666. Computers will then drop the
fractional portion (at least for the purposes of making a random
integer) and return the 9 alone.

Now, there are two implementations of Java's Random function,
Random() and Random(seed). Random(seed) essentially means that the
number you enter as the seed value is seeded in the formula like
the 5 above; the next iteration of that same Random(seed) call will
input the number returned as the seed for the next input. However,
this creates a very predictable series of numbers. Why? Well,
using the example above, when we put in 5 as the seed, we will
always get 9 as the return... inputting 9 returns 28, then 28 becomes
266, etc. This is *always* the case for the series when you start
with the same seed number. When rolling dice, you don't really
want to know what numbers are always going to be rolled, so this
becomes useless. When I tried this method, I always got the
series, 4 2 0 1 5, which was nice the first time I ran the game,
but boring the next zillion times I saw it.

Random() is generally more useful, as it looks at the current time
in the system clock and uses that as its seed. But unfortunately,
computers are very fast; so fast that they execute several lines
of code in a single millisecond. The system's clock generally only
gives a number to the millisecond, so if you're trying to gain a
few random numbers within the same area of code the system clock
seed number will not have changed. As above, if you always input
5, you will always return 9. I discovered this problem when I
"rolled" my dice in my program, and consistently got five dice
showing the same number (though that number changed each time I
rolled all five dice). Very big problem.

Ok, so my cleverness... I did some searching and probing some friends
(many thanks to jonrc, who does not have an lj account), I compiled
into my brain some very simple algorithms which still didn't really
work, and some very complex algorithms (Blum Blum Shub!) which work
extraordinarily well for Cryptography, but would be too much overhead
for this class (I promised the prof I'd send on anything I found
to fix the problem so that he could share it with the other students).
And somewhere it sprung out what is probably my reservoir of clever
for the month:

SEED = ( Random() + Random(SEED) ) / 2

The SEED is "static", so each iteration of that formula means the
old SEED is the seed for the next loop; I also return SEED to the
user as the random integer generated. Back to the laymen's terms,
what I am doing is combining the quirks of both the system clock
seeded Random, and the predictable pattern seeded Random, and letting
them interfere with each other enough to generate something more
random than either of them can be. I then take the average simply
so that I keep the generated number around the same range of numbers
the original functions produce.

This isn't airtight, it shouldn't be used in Cryptography, because
honestly, given it starting at *just* the right time, the pattern
of numbers generated can be predicted -- when this formula is
executed in the rapid fire fashion it's being done at, Random()
will remain the same number for the set of numbers generated, and
Random(seed) will give a predictable series of numbers. However,
for the purposes of some game where it's totally unknown when the
initial throw is made, this is just about as random as you can make
it without too much overhead. I also *somewhat* worry about the
Random(seed) series not leading to enough repeat numbers, but when
I did a bunch of tests on it (including a few 100d100 throws), it
was coming out with nice results.

There! I explain my geeky pride! I hope it made sense to y'all!
Or even if it didn't, accept that I was clever! I feel smert! :)
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 5 comments