XRandom

• Download source files - 44.2 Kb

Introduction

The goal of the application is to test the C# random generator numbers. There are three sub applications that cover all the aspects of a random generator:

1. Testing the randomness of C# generator.
2. A comparison between two methods of generating random numbers.
3. A little game.

For the simplicity of the formalism let's make the following conventions:

• RI - An ideal random numbers generator.
• R - C# random generator.
• P(n) - The set of permutations of n elements .

Details

1. Assume we want to want to apply the test on a permutation of n numbers: We generate the permutation using the brute method. We call the R even it can generate a number that we already have. We retain the number of the calls(NC) of G . It's quite simple to demonstrate that RI will generate our sequence calling [n*(1+1/2+.....1/n)] times his generator. So we can calculate the error of G:abs(n*(1+1/2+.....1/n)-NC) / ([n*(1+1+1/2+......1/n)]. The rest you can see in the application...
2. The brute method spent quiet a lot of time for generating a permutation. Take a lock at the following method that calls only n times R.A. The method is called replace method.

   public void  generate()    // the algorithm is verry simple
           {
               int k,count;   // fist i initiliaze an array of
               // n number with the value:x[i]=i(i>0;i<n)
                       
                                        
               for(int i=1;i<=n;i++)
                   etalon[i]=i;
   
               count=n;
               while (count!=0)  //i call the generator only n times
               {   // each time i generate a number(k)
                   // i move the last number of the initial
                   // array on the k position , i retain the value
                   // that i have found here and then 
                   // i remove the last element
                   k=gen.Next(count)+1;
                   a[n-count+1]=etalon[k];
                   etalon[k]=etalon[count];
                   count--;
               }
   
           }
   

   But what interests us is the efficatity of those two methods (brute and replace) The efficatity is the number of different permutation those method can generate in a imitated period of time. You can see the efficatity between those two methods running the application. For counting the number of different permutation I use a bijection between P(n) and n! (the number of permutation of n elements).

   See the bijection for n=3 lock like this :-

   1 2 3----->1
   2 3 2----->2
   2 1 3----->3
   2 3 1----->4
   3 1 2----->5
   3 2 1----->6

   Here's the code of the bijection

   private long fact(int n)   //a method for calculating n!
           {
               if (n==0) return 1;
               else return(n*fact(n-1));
           }
           public long getposition()     // the main method of the class
           {                             // it's calculate the bijection
               // from P(n) to [1..n!]
               int i,j,k,rest,cate,ii;
               long suma=0;
               for( i=1;i<=n;i++)
               {
                   
                   for(j=i;j<=n;j++)
                   {
                       cate=0;
                       for(k=i;k<=n;k++)
                           if (a[j]>a[k]) cate++;
                       a[j]=cate+1;
                   }
                   
                   suma+=fact(n-i)*(a[i]-1);
           
               }
               return suma+1;
           }
   

3. I implemented a simple game. The user picks up an array and tells the computer the length of the array and the sum of the elements. The elements must be greater than 0 and they can repeat .The computer will put "yes/no" questions and will try to guess the array. I know that are lot's more algorithm to make the computer play better (minimum number of questions), but i use a pure random algorithm (almost all the decisions are made using a random asign). I also calculate at the begin of each game the number of the solutions, using a simple recursive method.
   

   public long dami(int n,int sume,int lol)
           {                                       //calculate the number
               long k1=0;                         //of solution in for 
               long k2=0;
               int j,restinpeace;                  //a given lenght
               if (n==1) if (lol<=sume) return 1;  //and a given sum
                         else return 0;            // the initial call
               //of the function will be
               // dami(n,sume,1)
               k1=dami(n-1,sume-lol,lol);
               restinpeace=sume-(lol+1)*(n-1);
               for(j=lol+1;j<=restinpeace;j++)
                   k2+=dami(n-1,sume-j,j);
               return k1+k2;
           }
   
   

Sorry for my English