Thread: tips on making my program faster?

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    33

    tips on making my program faster?

    hello ladies and gentlemen

    i want some help on making my program faster

    for input N=1000000 it's runtime is 1,8 secs

    i want to make it <=1 secs

    here is the code, im using an implementation i made of eratosthenes algorithm to solve a problem

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    int main(void) {
        
        int N;
        
        FILE *fp=fopen("test.in","r");
        FILE *fout=fopen("test.out","w");
        fscanf(fp,"%d",&N);
        fclose(fp);
        int *array,i,size,k,check,*array2;
        check = 0;
        
        array = (int*)malloc(N*sizeof(int));
        
        for (i=0;i<N;i++){
            
            array[i] = i+1;
            
            if ( array[i] % 2 == 0 && array[i] != 2){
                 array[i] = 0;
                 }
                 
           //      printf("%d\n",array[i]);
                 }
                 array[0]=0;
      
      for (k=3;k<sqrt(N);k++){
                               
                        if (array[k-1]!=0){
                                                    
            for (i=k;i<N;i++){
                                
                       if (i%k == 0 && i!=k){ 
                                              
                            array[i-1] = 0;
                            
                                       }
                          }            
                      }
              }              
    
       size = -1;
       
        for (i=0;i<N;i++){
            if (array[i]!=0){
                             size = size + 1;
                             }
                             }
                             
         array2 = (int*)malloc((size)*sizeof(int));
         
         size = -1;
         
        for (i=0;i<N;i++){
            if (array[i]!=0){
                             size = size + 1;
                             array2[size] = array[i];
                             
                             }
                             }
    
        for (i=0;i<=size;i++){
            
            for (k=0;k<=size;k++){
                
                if (N == (array2[i] + array2[k])){
      
                         fprintf(fout,"%d %d\n",array2[i],array2[k]);
                         fclose(fout);
                         check = 1;
                         break;
                         }
            }
            if (check == 1){
                      break;
                      }
                    }
            
        free(array);
        free(array2);
    
              return 0;
              
              }
    thank you

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    One obvious optimisation would be to avoid calling sqrt() in the loop condition when its result is the same for all the iterations.

    You might want to indent your code more consistently and write a comment describing what the program is supposed to do.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Laserlight mentions one obvious optimisation, but there are tons more optimisations that can be done there!

    When marking off composite values using the sieve, you can start at k*k rather than just k, because any multiples of k less than k*k would have been marked off already. I.e. when marking off multiples of 5, you don't need to mark of 15 because that is also a multiple of 3 which means it would have already been marked off. So start that for loop at k*k.

    Can you fix the code to replace tabs with a fixed number of spaces before we help any more though please. It's too annoying to have to read the code when it's horribly indented like that.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    If you only need your code to be twice as fast, sometimes turning on the optimization option will do.

  5. #5
    Registered User
    Join Date
    Feb 2009
    Posts
    33
    thanks everyone, sorry for the code, but you ve actually helped me enough to reduce the time of the runtime

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Program to help you read faster
    By Nutshell in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 07-19-2003, 02:06 PM
  2. fopen();
    By GanglyLamb in forum C Programming
    Replies: 8
    Last Post: 11-03-2002, 12:39 PM
  3. Making a program which....
    By Zophixan in forum C++ Programming
    Replies: 9
    Last Post: 11-01-2002, 09:29 AM
  4. Help!! Tips on Matrix Calculator Program please!
    By skanxalot in forum C++ Programming
    Replies: 12
    Last Post: 03-11-2002, 11:26 AM
  5. help making a program run
    By Dummies102 in forum C++ Programming
    Replies: 3
    Last Post: 02-22-2002, 12:51 PM