PocketMagic

PocketMagic

Where Technology meets magic


Android
53 Posts
BlackBerry
6 Posts
Electronics
84 Posts
Hardware
142 Posts
High Voltage
57 Posts
Image processing
5 Posts
iPhone
4 Posts
Linux
2 Posts
Nuclear
27 Posts
Optics
11 Posts
Photography
7 Posts
Photoshop
3 Posts
Research
21 Posts
Reviews
19 Posts
Robotics
9 Posts
Security
9 Posts
Software
90 Posts
Symbian
2 Posts
Tubes
23 Posts
Windows Mobile
11 Posts

Sponsored Links


   

Top Articles!


Single Chip Computer | 562 Views | Rate 43.23
Single Chip Computer
AVR SDCard FAT support with FatFS | 14543 Views | Rate 32.03
AVR SDCard FAT support with FatFS
3V to 400V regulated inverter for Geiger counters | 1446 Views | Rate 13.9
3V to 400V regulated inverter for Geiger counters
Electric Fence - 20KV pulses for perimeter defense | 11403 Views | Rate 9.92
Electric Fence - 20KV pulses for perimeter defense

   

News & Updates


2014-10-29, Statie de monitorizare a radiatiei de fond in Timisoara

2014-10-29, uRADMonitor - Online Radiation monitoring station

2014-10-17, Single Chip Computer

2014-07-23, High Voltage Power supply - 140KV

 

  

Linear Pseudorandom number generator (PRNG)


By Radu Motisan Posted on January 17th, 2010 , 430 Views (Rate 0.25)



Intro

Very often we need to generate random numbers for different purposes ranging from simple games to advances encryption algorithms.
Many C/C++ programmers are well used with the srand() / rand() functions, but simply using a predefined code to achieve the given tasks, is sometimes not enough.
Fully understanding what a random number is, how it can be generated, helps getting the best solution.

Starting with my first university years, I used a linear pseudorandom generator, easy to implement, and quite useful in many applications.
A pseudorandom number generator (PRNG) is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG's state. Read more here.

A simple approach

Let's consider a,b and c three integer constant. We plan to generate a set of pseudorandom numbers X0, X1, ... , Xn. Assuming X0 = d, the rest of the numbers can be computed in a recurrent using the formula:
Xn+1 = (a*Xn + b) % c .

a,b,c and d are the initial values, also known as the PRNG's state.

c limits the resulting values to the interval 0.. c-1
a and b are affecting the linear angle.

Here is a simple C algorithm to better illustrate the formula:

#include

int main()
{
int a=71, b=19, c=256, d = 3;

int x[200] , i = 0;
x[0] = d;
for (i=1;i<200;i++)
x[i] = (a*x[i-1] + b) % c;

printf("The pseudo random numbers are:\n");
for (i=0;i<200;i++)
printf("%d ", x[i]);

return 1;
}

You can see the result in the following image:
pnrg1
Source code here:pnrg1.

To resemble the srand() and rand() functions you're all used to, I need to highlight that they're also using a PRNG. srand() "seeds" the random generator and practically all that does is to set the initial values (PRNG's state).
You can easily adapt the generator above to work like srand() and rand():

#include

int a = 71,b = 19, d = 0;

void mysrand(int seed)
{
d = seed;
}



int myrand(int threshold)
{
int x = d;
x = (a*x + b) % threshold;
d = x; // advance with each function call
return x;
}

void main()
{
mysrand(122);
printf("PseudoRandom number: %d\n", myrand(256));
printf("PseudoRandom number: %d\n", myrand(256));

}

Result as pictured below:
pnrg2
The source code here: pnrg2

You'll quickly notice that the PRNG produces the same output every time you initialize the mysrand with the same value:
mysrand(122) -> myrand(256)=233
But this is the same in the case of the built in srand() and rand() function too. The reason is that we don't have a good source for chaos. You can overcome this by using:
mysrand(GetTickCount());
or
mysrand(Cursorpos.x)
or
mysrand(FreeRAMMemory())
or
mysrand(UserLastKeyPressed)
or etc, linking the initialization function to a random event.

Further analysis

Talking about the chaos level of this generator, there is a simple way of analyzing a sequence of numbers, in our case the X0,...,Xn serie outputed by the linear PRNG.
1. In a single dimensioned space, represented by the real number axis and the corresponding set of all real numbers (R), a given number can be viewed as a single entity corresponding to a point on the axis.
For eg., see the following picture:
pnrg3
It represents a few real numbers on the axis. One might ask, what's the meaning of number -1.13 . The simple answer is: -1.13 is the entity that sits on the axis at the given position. Several properties can be extrapolated, and we get a meaning of what -1.13 is, and most important: what can we do with it.
2. For a given pair of numbers, we can image a bidimensional space, where the pair represents a point in a Cartesian system of reference. The pair receives a meaning, and we can further elaborate on that, using the pair for various purposes.

In a similar way, for a given set of numbers (x0,x1,...,xn) that seem random and meaningless at first, let's not forget that in a n-dimensional space, the set of numbers has a very simple and clear meaning: it represents a point.

Luckily, for the PRNG's the things are simpler.
Given a set of numbers generated with the linear PRNG, they can be represented without any meaning in one dimension: they would be "random" points on the number axis.
BUT, we can search for a "path" or a "meaning" by moving to a superior space, in this case to two dimensions, and representing the pseudo numbers set by point of coordinates (Xn-1, Xn).

See the following sample:
1- The first PRNG sample I've posted, produced the following numbers:
3 232 107 192 83 24 187 240 163 72 11 32 243 120 91 80 67 168 .... etc
It is very hard to understand what these numbers mean or to give a purpose to this sequence or even to understand the pattern that served to produce them.

2- Let's write a simple program to graphically illustrate in two dimensions pairs of numbers (Xn, Xn+1) as points in a Cartesian system.
Linear Pseudo Random Number Generator
The points in the picture are nothing else then the 200 pseudo random numbers (3 232 107 192 83 24 187 240 163 72 11 32 243 120 91 80 67 168
171 128 147 216 251 176 227 8 75 224 51 56 155 16 131 104 235 6
4 211 152 59 112 35 200 139 160 115 248 219 208 195 40 43 0 19
88 123 48 99 136 203 96 179 184 27 144 3 232 107 192 83 24 187
240 163 72 11 32 243 120 91 80 67 168 171 128 147 216 251 176
227 8 75 224 51 56 155 16 131 104 235 64 211 152 59 112 35 200
139 160 115 248 219 208 195 40 43 0 19 88 123 48 99 136 203 9
6 179 184 27 144 3 232 107 192 83 24 187 240 163 72 11 32 243
120 91 80 67 168 171 128 147 216 251 176 227 8 75 224 51 56 155
16 131 104 235 64 211 152 59 112 35 200 139 160 115 248 219 20
8 195 40 43 0 19 88 123 48 99 136 203 96 179 184 27 144 3 232
107 192 83 24 187 240)

Interestingly, what at first seemed total chaos, now reminds the proper order of a orchard with trees properly planted in rows and columns, at a given angle, in our image represented by the black dots.
Get the source code here: pnrg3gui

If viewing the sequence in two dimensions doesn't show anything useful, we can move further and check the representation in three dimensions, points of coordinates (Xn-1, Xn, Xn+1), and so on.

As shown above, at one given level, the "random" content will get a meaning.

Hope this helps,
Radu



More on PocketMagic:

Simple Switched power Supplies | 6256 Views | Rate 6.86
Simple Switched power Supplies
How to set the AVR Fusebits | 3999 Views | Rate 6.68
How to set the AVR Fusebits
Atmega8 and Nokia 5110 LCD  | 3344 Views | Rate 5.86
Atmega8 and Nokia 5110 LCD
uRADMonitor - Online Radiation monitoring station | 3986 Views | Rate 5.39
uRADMonitor - Online Radiation monitoring station
Coil Winding machine counter with Atmega8 and Reed relay | 2598 Views | Rate 4.96
Coil Winding machine counter with Atmega8 and Reed relay
Building a robot – Make the robot follow you | 3096 Views | Rate 4.91
Building a robot – Make the robot follow you

Thank you for commenting. Your comment won't show until approved, which can take some time.

Please copy the string LWfzyb to the field below: