Results 1 to 2 of 2

Math Help - complexity of this algorithm in my program

  1. #1
    Banned
    Joined
    Nov 2008
    Posts
    63

    complexity of this algorithm in my program

    Code:
    #include <stdio.h>
    #include <math.h>
        int primetest(int n){ 
        
            int temp = n,i;
           
            for(i = sqrt(n);i>=2;i--){
         
               if(!(temp%i)) 
              
               return 1; 
            } 
           
            return 0; 
        } 
        int MOD(int x,int y,int n){
     
         unsigned long i,j;
     
         if(x>=1000){
      
         i=x/1000;
         
         j=x%1000;
         
         return (((i*y)%n)*1000+(j*y))%n;
      
          }
     
             else if(y>=1000){
      
               i=y/1000;
               
         j=y%1000;
         
            return (((i*x)%n)*1000+(j*x))%n;
          }
          else{
           
               return (x*y)%n;
             }
      
         }
         int Fermat_test(int N,int a){
          
          int i,temp,bit=0,binary[20],n,mod;  
         
             unsigned long pm[20];
         
             if(primetest(N)){
         
               n=N;
         
                 N=N-1;
      
              while (N!=0){
          
                 bit++;
       
                    i=N%2;
         
                    binary[bit]=i;
       
                    N=N/2; 
                 } 
        
              pm[0]=a%n;
              
                 mod=pow(a,binary[1]);
          
              for(i=1;i<=bit-1;i++){
          
           pm[i]=MOD(pm[i-1],pm[i-1],n);
       
           if(binary[i+1]!=0){
        
           mod=MOD(mod,pm[i],n);
           }
              }
              
         if(mod==1){
          
          return 1;
         }
         else{
          
          return 0;
         }
           }
    }
    main() 
    { 
        
           int a,N,i;
         
           FILE * fp;
       
           fp=fopen("c:\\output.txt","w+");
           
           printf("Enter the value of a: <=13 ");
           
           fflush(stdout);
           
           scanf("%d",&a);
         
           for(i=a+1;i<=1000000;i++){
          
             if(Fermat_test(i,a)==1){
           
              fprintf(fp,"%d\n",i);
              }
           }  
           
           return 0;
    }

    we only consider this part of our program:

    Code:
             if(primetest(N)){
                 n=N;
                 N=N-1;
                 while (N!=0){
                     bit++;
                     i=N%2;
                     binary[bit]=i;
                     N=N/2; 
                  } 
                 pm[0]=a%n;
                 mod=pow(a,binary[1]);
                 for(i=1;i<=bit-1;i++){   
                     pm[i]=MOD(pm[i-1],pm[i-1],n);
                     if(binary[i+1]!=0){
                         mod=MOD(mod,pm[i],n);
                     }
                  }
              }
    what is the time complexity of this part? They asked about a function O(f(N))= g(N) and discuss the ratio g(N)/f(N) as N goes to infinity.
    Last edited by CaptainBlack; September 3rd 2009 at 01:21 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by silversand View Post

    we only consider this part of our program:

    Code:
             if(primetest(N)){
                 n=N;
                 N=N-1;
                 while (N!=0){
                     bit++;
                     i=N%2;
                     binary[bit]=i;
                     N=N/2; 
                  } 
                 pm[0]=a%n;
                 mod=pow(a,binary[1]);
                 for(i=1;i<=bit-1;i++){   
                     pm[i]=MOD(pm[i-1],pm[i-1],n);
                     if(binary[i+1]!=0){
                         mod=MOD(mod,pm[i],n);
                     }
                  }
              }
    what is the time complexity of this part? They asked about a function O(f(N))= g(N) and discuss the ratio g(N)/f(N) as N goes to infinity.
    This fragment:

    Code:
                while (N!=0){
                     bit++;
                     i=N%2;
                     binary[bit]=i;
                     N=N/2; 
                  }
    looks like it is finding the binary expansion of N, and has complexity O(log(N)).

    Similarly this fragment:

    Code:
                 for(i=1;i<=bit-1;i++){   
                     pm[i]=MOD(pm[i-1],pm[i-1],n);
                     if(binary[i+1]!=0){
                         mod=MOD(mod,pm[i],n);
                     }
                  }
    has complexity O(length(bit))=O(log(N)).

    The trouble is the the complexity of primetest(N) which has to be calculated then the problem becomes what range of N do you want the average complexity over, or do you want the worst case complexity...

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] complexity theorie, deterministic turing-machines, time complexity
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 06:44 AM
  2. karmarkar s algorithm - linear program
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: March 9th 2010, 12:32 AM
  3. Matlab - Determining the complexity of an algorithm
    Posted in the Math Software Forum
    Replies: 5
    Last Post: March 19th 2009, 03:25 AM
  4. Complexity of Algorithm
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: June 21st 2008, 10:13 AM
  5. Complexity of Prime Algorithm
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 3rd 2006, 01:09 PM

Search Tags


/mathhelpforum @mathhelpforum