RANDOM isn't so random.

[Ñuño Martínez]

Hello.

I've found that "RANDOM (n)" returns some numbers more often than others. the game I was coding needs to select a random number from [0..20] and I get [5..15] much more often than the others, and [5..10] more than [11..15]. It's too obvious for me and I need a more regular frequency. I'm using RANDOMIZE too. I must say that these numbers are selected few times. In a 'standard' play it searches about 10-15 numbers each player.

Is it usual? Is there a way to "normalize" it or another random algorithm available?

I'm using Lazarus 0.9.22 (FPC 2.0.4). If FPC 2.2.0 fixes it, how can I update Lazarus' compiler?

Thanks in advance.

[arthurprs]

pascal random gives you a number at range from a list generated at app init {not sure}

to corrent use a code like the above

Randomize;
RandSeed := GetTickCount; // gettickcount is from windows unit, if you don't use it declare the following line
// function GetTickCount: Cardinal; stdcall; external 'kernel32.dll';
random(n); //now random will be a true random :)


There are better ways but this one works perfectly with 2 lines added

[arthurprs]

to upgrade your lazarus install a new snapshot

ftp://ftp.hu.freepascal.org/pub/lazarus/Lazarus-0.9.23-fpc-2.2.1-20071006-win32.exe
ftp://ftp.hu.freepascal.org/pub/lazarus/Lazarus-0.9.23-fpc-2.2.0-20071006-win32.exe

[Traveler]

Quite a few years ago I asked something similair. I'm not really sure if it's what you're after as well, but here's the thread (http://www.pascalgamedevelopment.com/viewtopic.php?p=2414&highlight=#2414)

[off topic]I just discovered that if you do a search for that particular thread, you wont find it. :? Makes you wonder what else stays hidden n pgd.[/offtopic]

[User137]

I'm curious on how did you made the testing?
Firstly there is:
21 numbers in 0..20
10 numbers in 0..4 + 16..20
11 numbers in 5..15

Would it differ if using floating point random instead of integer random() or different value range?

Then to have basics clear, examples:
Integer random: Random(10) returns integer [0..9]
Floating random: Random() returns ]0..1[ (never returns exactly 0 or 1)

Edit: Also Randomize; should only be called once when application starts. After that simply Random() calls.

[arthurprs]

Use RandomRange from Math unit
{Description
The RandomRange function generates a random Integer number within the range RangeFrom to RangeTo inclusively. *

This provides a more convenient version of the System unit Random function.

Both use a pseudo random number sequence of 232 values. Each time you run your program, the values generated will be the same, unless you reposition the generator to a different part of the sequence using the Randomize or RandSeed functions.}
function RandomRange ( const RangeFrom, RangeTo : Integer ) : Integer;

[cairnswm]

15 numbers isn't a very big sample to use and then say it isn't random. Using true randomisation means that at one time you could (very small chance of) getting 15 values of 5s in your sample.

I did a similar test useing 1000 random checks, I never get one number with more than 2599 or less than 2400 over 10 runs. Seems pretty normal for me. :) [1000 runs means 0-4 on average 2500 times]

[dmantione]

Free Pascal uses the Mersenne Twister for random numbers:

http://en.wikipedia.org/wiki/Mersenne_twister

As the Mersenne Twister has a mathematical underpinning, I would not expect it to fail such a simple distribution test; it is expected to provide uniform distribution over [0..20].

Do the numbers you get are really contrary to what you would mathematically expect? For example, one rule of randomness is that when you draw 10 numbers, on average sqrt(10) numbers will appear twice in the drawn set.

I don't recommend playing with randseed as it is "emulated"; the true random seed for the Mersenne Twister is an array of values inside the system unit.

[cronodragon]

In one of the Game Programming Gem books there is an article about creating a true randomizer, reading different inputs, system states, clocks, etc and combining them all. It's very interesting, if you want to take a look at it.

[pstudio]

In one of the Game Programming Gem books there is an article about creating a true randomizer
In theory you can't make a true randomizer, but I suppose reading input etc. would make a pretty good aproximation

[Brainer]

In theory you can't make a true randomizer, but I suppose reading input etc. would make a pretty good aproximation

Why? :o I think it's possible to make a true randomization with the code presented by: arthurprs


Randomize;
RandSeed := GetTickCount; // gettickcount is from windows unit, if you don't use it declare the following line
// function GetTickCount: Cardinal; stdcall; external 'kernel32.dll';
random(n); //now random will be a true random Smile


Or maybe you could use the DecodeDateTime function, decode current date and time to several Word variables and then use this:


RandSeed := DateDay + DateMonth * (DateHour / DateSec) + GetTickCount();


Won't this return a truly random number? :o

[dmantione]

A) True randomness is possible

There are events in a computer that are unpredictable, so as exactly when the next key is pressed, or when a network package will arrive. Using these events you can feed your random generator with entropy. As soon as you have collected enough entropy you can generate a really unpredictable number.

B) Time based seeding is not true randomness.

It's simple: Someone who knows when your program is executed knows all random numbers that will be generated. This is very important in security, since you don't want someone to be able to predict your 2048-bit RSA keys you use to encrypt your sessions.

C) Very few situations require true randomness

Pseudo-random numbers generators generate random sequences with good random properties, like distribution, variance etc. Sure, if you know the random seed, you know all next numbers, which is incompatible with randomness. But this is seldomly a problem. I.e. players of a game do not try to obtain the random seed to predict all future events, therefore pseudo-random generators are perfectly usable to generate random events in games.

[cronodragon]

In one of the Game Programming Gem books there is an article about creating a true randomizer
In theory you can't make a true randomizer, but I suppose reading input etc. would make a pretty good aproximation

In the same article they show why that algorithm (or technique) is a true randomizer, the drawback is the speed to generate a number.

Also, I remember reading somewhere that a random generator unit could be integrated in processors or as single chips in the future. It would use electric static charges to generate the values, that would be very cool.

[pstudio]

There are events in a computer that are unpredictable, so as exactly when the next key is pressed, or when a network package will arrive. Using these events you can feed your random generator with entropy. As soon as you have collected enough entropy you can generate a really unpredictable number.
It's true that you can put in a number of unpredictable factors in your randomizer, but in the end it's still just an algorithm that calculates a number. That means that in theroy you should be able to reproduce the same calculation. However it is a different thing when it comes to reality.
But again as you mention, you'll hardly ever need a true randomizer in a game.

[Brainer]

It's true that you can put in a number of unpredictable factors in your randomizer, but in the end it's still just an algorithm that calculates a number.

That's right. Nevertheless, I think it's possible to generate a number that can't be reproduced in the future. It's only a matter of an algorithm. A good algorithm is to count all files in system32 directory and then divide it by the file count on your desktop. Then, you can multiply it by GetTickCount! :)

[User137]

I'd forget GetTickCount, it can by max give you a 1ms detail. But in fact you can call Random() several times within 1ms therefore giving same result for many consecutive calls. Although just thought about Queryperformancecounter.. with custom made range function to parse the floating point value you wouldn't even need seed or built in random function.

[arthurprs]

using randomseed := gettickcount;
is more than good for me :?

it gives a new list based on how ms count from windows start ultil the time of the call

[dmantione]

Always use "randomize" over your own inventions with randseed. "randomize" will work cross-platform and often has seen more thought than your own inventions (such as wether you need gettickcount or querypeformancecounter).

[Ñuño Martínez]

There are a lot of information here, I'm really impressed :shock:

By the way I go to get this (which is my question answer):

15 numbers isn't a very big sample to use and then say it isn't random. Using true randomisation means that at one time you could (very small chance of) getting 15 values of 5s in your sample.

I did a similar test useing 1000 random checks, I never get one number with more than 2599 or less than 2400 over 10 runs. Seems pretty normal for me. :) [1000 runs means 0-4 on average 2500 times]Yes, 15 chances is a very small sample, and yes, I did 1000 random checks and I get a 'normal' distribution, so I think that was lucky.

May be I'll use a "card-deck algorithm" (That is, create an array with all values, including the repetition I'm looking, shuffle it and then pick the values from there). I used it in another part of the game that uses "real" cards. This way, if I put only 2 copies for each value I'll get a better distribution. As example:VAR
Values: ARRAY [0..19] OF INTEGER;
Next: INTEGER;

PROCEDURE Shuffle;
VAR
Cnt, Tmp1, Tmp2: INTEGER;
BEGIN
{ Insert values. }
FOR Cnt := 0 TO 9 DO
BEGIN
Values[Cnt * 2] := Cnt;
Values[(Cnt * 2) + 1] := Cnt;
END;
{ Shuffle. }
FOR Cnt := 0 TO 19 DO
BEGIN
Tmp1 := Random (20);
Tmp2 := Values[Cnt];
Values[Cnt] := Values[Tmp1];
Values[Tmp1] := Tmp2;
END;
{ First value. }
Next := 0;
END;

FUNCTION PickValue: INTEGER
BEGIN
PickValue := Values[Next];
Inc (Next);
IF Next > 19 THEN
Shuffle;
END;

By the way, thanks for the interest to all. This is a very interesting thread. May be I'll use it in other projects.