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

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here