PocketMagic

PocketMagic

Where Technology meets magic


Android
51 Posts
BlackBerry
6 Posts
Electronics
82 Posts
Hardware
139 Posts
High Voltage
56 Posts
Image processing
5 Posts
iPhone
4 Posts
Linux
2 Posts
Nuclear
26 Posts
Optics
11 Posts
Photography
7 Posts
Photoshop
3 Posts
Research
20 Posts
Reviews
18 Posts
Robotics
8 Posts
Security
9 Posts
Software
88 Posts
Symbian
2 Posts
Tubes
23 Posts
Windows Mobile
11 Posts

Sponsored Links


   

Top Articles!


Bluetooth and iOS - Use Bluetooth in your iPhone apps | 58161 Views | Rate 90.03
Bluetooth and iOS - Use Bluetooth in your iPhone apps
Simple Switched power Supplies | 59522 Views | Rate 82.44
Simple Switched power Supplies
AVR SDCard FAT support with FatFS | 17376 Views | Rate 65.82
AVR SDCard FAT support with FatFS
Programmatically Injecting Events on Android - Part 1 | 41119 Views | Rate 56.79
Programmatically Injecting Events on Android - Part 1

   

News & Updates


2014-04-15, Electric Fence Circuit for perimeter protection

2014-03-28, Infused™ project

2014-03-28, Discussing security in online on TV News show

2014-03-20, Global radiation monitoring network

 

  

Linear Pseudorandom number generator (PRNG)


By Radu Motisan Posted on January 17th, 2010 , 2876 Views (Rate 1.85)



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:

Electric Fence Circuit for perimeter protection | 351 Views | Rate 43.88
Electric Fence Circuit for perimeter protection
Using FS1000A/XY-FST RF Radio module with AVRs | 10922 Views | Rate 40.91
Using FS1000A/XY-FST RF Radio module with AVRs
A 3D Carousel View for Android | 12462 Views | Rate 39.69
A 3D Carousel View for Android
Android Bluetooth controlled robot - Part 1 | 45916 Views | Rate 36.15
Android Bluetooth controlled robot - Part 1
How to set the AVR Fusebits | 14383 Views | Rate 35.25
How to set the AVR Fusebits
Global radiation monitoring network | 9851 Views | Rate 34.44
Global radiation monitoring network

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

Please copy the string K4ezeU to the field below: