Random Generator

[JoRo]

Hi,
I need to know, with which algoritmus PureBasic generates the random numbers.

Johannes

[geoff]

Yes, this would be useful.

For example, you may need to write decryption routines in another
language that are compatible with Purebasic code.

At the moment random() is a language specific black box.


Experimenting with this command reveals that Random(Maximum) allows
Maximum to be 2^31-1, ie the largest signed long integer. So in effect
you get 31 random bits returned. It would be useful if it were possible to
get 32 random bits returned. For example if Random(0) returned a
random 32 bit unsigned number.

[Fred]

BTW, I would suggest to write your own random routine if you want to have full control over it. The current random can be changed one day or enhanced for speed reason, so don't assume it willn't change.

[Num3]

More info on random algorithms here:

ModuloN - Christopher J Martens [CMartens@mail2Canada.com].txt


Back



The Modulo-N Randomization Algorithm

Warning: This article does discuss a lot of math, but nothing we didn't sleep
through in elementary school.

Wordy Introduction:

There is a paradoxical need for randomized, "unpredictable" input generated from
ordered, "predictable" systems. Although both theoretically and practically
impossible, several methods to randomly generate numbers do exist; one such is
the modulo-n pseudo-random algorithm, employed in many facets of computer
science such as public key cryptography and statistical analysis to name a few.

The underlying principle of the system is to generate a sequence of numbers with
no discernable pattern. A seed value is provided to the algorithm to establish a
starting point and the algorithm presents a numeric sequence of finite length.

This algorithm, or another similar to it, is usually included in software
development environments. The purpose of this article is to shed some light on
the workings of the algorithm.

The equation:

This method of random numbers is something you've probably worked with already.
However many treat it like a black box, knowing inputs and outputs but not the
actual workings, and up until four months ago, so did I.

The basic framework of the theorem is this:

X = (Y) MOD (N)

Simply put, X will be the remainder after dividing C by N (Y/N).

Now, you probably know that the range of values possible for X will be 0 to N-1.
For instance:

Y = 21, N = 7 : X = 0
Y = 23, N = 7 : X = 2
Y = 27, N = 7 : X = 6
Y = 28, N = 7 : X = 0

Obviously, the afforementioned equation is not really a useful equation. The
actual modulo-n equation is this:

NewValue = [ (A * OldValue) + B ] MOD (N)

To get this to work, we need four values: A, B, OldValue and N. The old value
you've probably heard of before. It's sometimes called the seed value.

This still follows the same principle as the first equation, except that the Y
variable from the first equation changes as numbers are generated
(ie. A * OldValue + B = Y). Let me demonstrate using this equation...

Assuming A = 13, B = 3, N = 2^3 = 8

We'll need a seed number. I'll pick 6 for now.

N = [ ( 13 * 6 ) + 3 ] MOD 8 = 81 MOD 8 = 1

Now throw this newly generated number back into the equation as the seed...

N = [ ( 13 * 1 ) + 3 ] MOD 8 = 16 MOD 8 = 0

And again, doing the same...

N = [ ( 13 * 0 ) + 3 ] MOD 8 = 3
N = [ ( 13 * 3 ) + 3 ] MOD 8 = 2
N = [ ( 13 * 2 ) + 3 ] MOD 8 = 5
N = [ ( 13 * 5 ) + 3 ] MOD 8 = 4
N = [ ( 13 * 4 ) + 3 ] MOD 8 = 7
N = [ ( 13 * 7 ) + 3 ] MOD 8 = 6 <= Same as original seed
N = [ ( 13 * 6 ) + 3 ] MOD 8 = 1 <= Notice the beginning of a pattern?


So the actual sequence of numbers generated by the algorithm is 1, 0, 3, 2, 5,
4, 7, 6, 1, 0, 3, 2, 5, 4, 7, 6 and so on and so forth. These are technically
random.

Observations/Discussion:

There may be a bit of a detectable sequence (1 to 0, 3 to 2, 5 to 4, 7 to 6),
but in real life when larger numbers are used, it is very difficult to detect
any pattern. Also, it is important to remember how you're using these numbers.
For all the C/C++ goons out there, what do we do once we get a number from the
rand() function? We force it to the range of values we want for the specific
purposes we want these random numbers for.

Example code fragment:

// Format generated number between Max and Min.
int x = rand() % (Max - Min) + Min;

By doing this, we increase the "randomness" of the whole process, because the
chances of getting the exact same number from the generator for the exact same
purpose are pretty low. However, at some point there'll be a pattern setting,
but there are many ways to either get around them or prevent them altogether,
many of which are common knowledge.

Additionally, there are a few things I've found out that could be helpful.
Variable A *really* needs to be a prime number, otherwise you might get a value
for A being wholly divisible by N and then that would shorten the sequence
prematurely. This is also the case for B, but the need for this has to be
emphasized. If the previous number was 0 and B / N leaves no remainder then you
will get B MOD N to be 0; which is the exact same as the value before it. In
short, the whole algorithm crashes to a halt and keeps outputting 0 until you
manually provide a new seed.

Another interesting thing to notice is that when everything works perfectly, you
will always get N unique sequence steps. That is, if N = 8, you'll get 8
discreet steps before the sequence repeats itself. If this is the case, then the
sequence generated will have to include every possible value from 0 to N-1
before it repeats.

It is also beneficial to have N as a power of 2. If N = 2^m, then every number
generated will fit into an allocated space inside memory of 'm' bits. That way,
you can create random numbers that are guaranteed to fit into a specific
variable type, be it a byte (8 bits) a word (16 bits) or a double word (32 bits).

Conclusions:

I've written a little program for C++ which I've experimented with, try it out
if you're curious. (My apologies to those who do not use C++, although it
should be easy to figure out) It's far from bulletproof, however, especially if
you enter character input.

#include <iostream.h>

void main( void )
{
int A, B, N, seed;

// Display cheesy intro
cout << "Modulo-N Algorithm Demonstration:\n"
<< "Please enter required parameters\n";

// Get intro values
cout << "A = ";
cin >> A;

cout << "B = ";
cin >> B;

cout << "N = ";
cin >> N;

cout << "Seed value = ";
cin >> seed;

// Generate random numbers
cout << "Generating numbers...\n\n";

int count = 0;

while( count <= N )
{
// Generate the number
seed = ( ( A * seed ) + B ) % N;

// Display the number
cout << seed << ", " << flush;

// Advance the count
count++;
}

cout << "Done!" << endl;

return;

}

Anyways, I'd better quit. Hopefully, this satifies some curiosity as to why and
how the random number generator inside a computer works and maybe give some
insight into how to use it effectively. Please email me and let me know if
something didn't make sense and/or what I could do to make this little article
clearer and more coherent.

Cheers,

Chris Martens
CMartens@mail2canada.com

[geoff]

Num3 thanks for that info.

I think Fred's advice makes sense, if you want to use a particular random
sequence long term then better program it yourself.

Num3's algorithm
new_value=(old_value*A + B)mod N
is simple and fast.

[geoff]

After a little more thought, I don't think this modulo-n algorithm is as
useful as the author claims.

The least significant binary digit of the output number cycles between 1
and 0 on subsequent numbers. The 2nd significant digit repeats on a cycle
of 4, the 3rd digit on a cycle of 8 and so on. This is nothing like random,
and if you used it for cryptography your messages would be broken very easily.

I think the suggestion that N be an exact power of 2 is the problem.
Choose N to be a large prime number and this method may be OK.