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:
- Testing the randomness of C# generator.
- A comparison between two methods of generating random numbers.
- 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
- 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...
- 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()
{
int k,count;
for(int i=1;i<=n;i++)
etalon[i]=i;
count=n;
while (count!=0)
{
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)
{
if (n==0) return 1;
else return(n*fact(n-1));
}
public long getposition()
{
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;
}
- 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)
{
long k1=0;
long k2=0;
int j,restinpeace;
if (n==1) if (lol<=sume) return 1;
else return 0;
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