lundi 13 juillet 2015

Randomness of Random class in Java

I will be generating two random numbers one after the another using the Random class in Java between 0 and a given number x.My aim is to fill an array of length x+1 using these numbers and calculate the following:

Magnitude:The maximum difference between two numbers.

degree:The number of random number generations, required before the array gets filled.Note that two numbers generated consecutively add 1 to the degree.

degree_of_intersection:The number of times the interval between 2 generated numbers overlapped with some interval of previously generated 2 numbers.

I calculated this using the following code in Java and for simplicity i have assumed x=9.

class Randm
{
 public static void main(String []args)
 {
     int a,count=0,r_no1,r_no2,l,r;
     Random rd=new Random();    
     int magnitude=0,degree=0,degree_of_intersection=0;     
     int []jump=new int[10];
     for(int i=0;i<10;++i)
     {         
         jump[i]=0;
     }     
     while(count!=10)
     {
         ++degree;
         r_no1=rd.nextInt(10);
         r_no2=rd.nextInt(10);
         if(Math.abs(r_no1-r_no2)>magnitude)
          magnitude=Math.abs(r_no1-r_no2);
         if(r_no1<r_no2)
         {l=r_no1;r=r_no2;}
         else {r=r_no1;l=r_no2;}
         for(int i=l;i<=r;++i)
         {
            if(jump[i]!=0)
             {
                 ++degree_of_intersection;
                 i=jump[i];
                 continue;
             }
            else
             {
                 jump[i]=r;
                 ++count;
                 /*FILL THE ARRAY AT INDEX i*/
             }
         }
     }
     System.out.println("\nthe magnitude and degree of randomness is "+magnitude+" and "+degree);    
     System.out.println("\nthe degree of intersection is "+degree_of_intersection);    
 }
}

The problem is that because i have used an array jump of length x+1 that helps me to calculate degree_of intersection easily, my space complexity is LINEAR

Whereas, I have to achieve constant space complexity.

Kindly note that besides the array to fill all other data structures used will be counted in space complexity.




Aucun commentaire:

Enregistrer un commentaire