Re: Random number question?

From: Randall Hyde (randyhyde_at_earthlink.net)
Date: 06/21/04 

Date: Mon, 21 Jun 2004 15:28:57 GMT

"Paul Allen Panks" <panks@sdf.lonestar.org> wrote in message
news:cb5u35$plp$1@chessie.cirr.com...
> How does HLA's random number generator differ from traditional BASIC's
> version? I've long based much of my adventure gaming on random numbers,
> especially during player/monster fighting. Does seeding a number truly
> make it random, or only quasi-random?

Well, *all* random number generators are "pseudo-random", by
definition as they all use an algorithm to compute the next
random number (i.e., the result can be predicted).

HLA's rand.randomize function reads the Pentium's timestamp
counter (if available on the CPU) to reseed the value. While
this starts a new sequence, arguably it is not random as the
timestamp counter simply increments with each clock cycle.

There are two random number generator algorithms found in
the rand library: a traditional modulo-based algorithm
(which isn't bad at all) and a table-based algorithm from
Knuth (which is actually quite good, with respect to randomness).
Having said this, however, I'd point out that I've never
run the usual statistical tests to determine the quality of
the random number generators.

>
> Let's say I have a number between 1 and 35. What guarantee do I have that
> the computer won't habitually (or accidentally) pick the same range of
> numbers twice? Or the same individual number twice?

There are a suite of tests you can run on random number generators to
determine
exactly these qualities. As I've said, I've not actually run those test
myself. But I
trust the sources of the algorithms I've used in the rand package, so I'm
not too worried
about degenerate behavior (unless you pick a really weird starting seed
value, which
I don't do).

Couple of comments: the rng will always pick the same range of values :-)
And it will pick the same number twice, even in a row, on occasion. The
definition
of a random number generator doesn't prevent this (indeed, it predicts this
will
happen). If you want to guarantee that you get a unique sequence of numbers
between 1 and 35, use the rand.deal iterator in the rand package.

BTW, I hope you're calling rand.range to limit your random numbers between
1 and 35. The traditional way (computing (rand mod 35)+1 generates very
bad results because the L.O. bits of a random number generator are rarely as
random as the whole number (see Knuth Volume Two for details). The
rand.range
number creates a random number in some range by using various bits through
the normal 32-bit random number that the generators emit.

>
> To find out, I wrote a simple QBasic program below:
>
> 1 CLEAR
> 5 CLS : PRINT "Random Number test"
> 10 FOR x = 1 TO 10
> 20 RANDOMIZE TIMER
> 30 i = INT(RND * 35) + 1
> 40 PRINT i
> 45 NEXT x
>
> The program was run three separate times, with the following results:
>
> Test #1
> Random Number test
> 27
> 25
> 17
> 31
> 24
> 18
> 27
> 34
> 23
> 22
>
> Test #2
> Random Number test
> 32
> 29
> 21
> 35
> 29
> 22
> 32
> 4
> 27
> 27
>
> Test #3
> Random Number test
> 21
> 18
> 10
> 24
> 17
> 11
> 21
> 28
> 16
> 16
>
> Ah oh...the last two tests repeated the last two sets of numbers not once
> but TWICE! That's not good!

"Equally likely" means exactly that. But the problem with this
code is exactly what I mentioned earlier - the (n mod m)+1 algorithm
for generating random numbers within some specified range is known
to generate less than random sequences. It's not BASIC, it's the mod
algorithm you're using. This is why I stuck rand.range (and rand.urange)
in the HLA standard library, to provide a better solution for people who
don't understand the inner workings of random number generators.

>
> Now for the same program in HLA:
>
> program random;
> #include ("console.hhf");
> #include ("stdlib.hhf");
> #include ("math.hhf");
> static
> i:int32:=0;
> x:int32:=0;
> begin random;
> console.cls();
> stdout.put("Random number test",nl);
> start:
> add(1,x);
> rand.randomize();
> rand.urange(1,35); // pick a random number, 1 through 35
> mov(eax,i); // move it into i variable
> mov(i,eax); // set i to eax value
> stdout.put(i,nl);
> if(x<10) then
> jmp start;
> endif;
> end random;
>
> The HLA version gives the following 3 results:
>
> Test #1
> Random number test
> 29
> 24
> 11
> 19
> 22
> 8
> 27
> 33
> 27
> 28
>
> Test #2
> Random number test
> 19
> 4
> 32
> 30
> 23
> 34
> 24
> 20
> 20
> 30
>
> Test #3
> Random number test
> 35
> 26
> 29
> 17
> 26
> 18
> 33
> 29
> 19
> 1
>
> Some repeats, but not as bad as before.

Repeats are perfectly reasonable in a random number generator.
As I said, if you don't want any repeats at all, consider using
the rand.deal iterator.

By the way, assuming a perfect even distribution of random numbers,
if you choose ten numbers out of 35, there is a one in 3.5 chance of
getting a repeated number. Depending on which bits rand.urange
decides to choose, this ratio is probably even worse. So getting
repeats in the examples above is actually expected.

>
> Is there a way to truly limit the number of repeats during a set of random
> number generation? I can foresee a lot of random numbers in my own mind,
> but they have to be truly, truly random for the random number generator to
> be doing a good job.
>

Well, there are very few *truly* random number generators out there (most of
them
are hardware devices that measure alpha decay of some radioactive isotope).
HLA's is far from the best, but it is relatively fast. Statistically *good*
random
numbers are expensive to compute, not something you'd want to use in most
games (okay, it's probably good for a text-based adventure:-) ).

> Any ideas as to why both sets of random number generators seem different
> in functionality?

Sure, they use completely different algorithms.
Cheers,
Randy Hyde

Relevant Pages

  • Re: Random number question?
    ... > How does HLA's random number generator differ from traditional BASIC's ... Or the same individual number twice? ... > Some repeats, but not as bad as before. ... Runs of numbers and other patterns occur far more ...
    (sci.math)
  • Re: Agduria dungeon generation
    ... stage of the algorithm and rise appropriate error, ... A NTAE generator doesn't have to have any ... NTAE will happily accept all valid inputs and RNG states and produce ...
    (rec.games.roguelike.development)
  • Re: Math.random
    ... That's not the only possible algorithm; ... without much difficulty implement a long shift-register generator; ... doublevalue or null/undefined/false for auto reseeding, ... I think 0 to 364 would be better; it goes well with zero-based arrays, ...
    (comp.lang.javascript)
  • Re: real random
    ... Feel free to post such an algorithm, ... it as a generator of a stream of numbers, ... You need a genuine source of entropy, ... By suggesting Fortuna (which gathers genuine entropy as it goes), ...
    (comp.lang.c)
  • Re: Agduria dungeon generation
    ... Depends entirely on the pseudo random number generator, ... algorithm don't suddenly change that probability. ... TAE isn't even obviously less ... algorithms but do understand their NTAE algorithms, ...
    (rec.games.roguelike.development)