Thread: Running time difference

  1. #1
    Registered User
    Join Date
    Dec 2018
    Posts
    13

    Running time difference

    Hi, I have two programs that perform the same task:

    Code:
    #define N 100000000
    
    int main()
    {
            long int x;
            double sum=0;
            char str[100];
    
            for (x=1;x<=N;x++)
                    sum = sum + x;
    
            sprintf(str,"%.0lf\n",sum);
            write(1,str,strlen(str));
    
            exit(0);
    }
    Code:
    #define N 100000000
    
    double sum[N+1];
    
    int main ()
    {
            long int x;
            char str[100];
    
            sum[0]=0;
            for (x=1;x<=N;x++)
                    sum[x] = sum[x-1] + x;
    
            sprintf(str,"%.0lf\n",sum[N]);
            write(1,str,strlen(str));
    
            exit(0);
    }

    In the first one the intermediate additions are being stored in the variable "sum", in the second one every addition is stored in the array. What is the reason behind the second one taking so much longer, if in both cases the value is being stored anyway?

  2. #2
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    5 things here:

    1- If you are using libc (sprintf function), why do you choose to write to stdout using write?
    2- In your second program,the array is 100 bytes long, but you are trying to access from byte 0 to 99999999?!
    3- In your first program sum is of type double (why?).
    4- In your programs the iterator x is of type long int (why?).

    Isn't it simplier and faster if you do:
    Code:
    #include <stdio.h>
    
    #define N 1000000000
    
    int main( void )
    {
      long long sum;
    
      sum = (long long)(N+1)*N / 2;  // Arithmetic Series Sum...
      printf( "%lld\n", sum );
    }

  3. #3
    Registered User
    Join Date
    Dec 2018
    Posts
    13
    Those pieces of code are part of an assignment. I need to work on them later on to optimize them in different ways, however at this point I'd like to understand why the second one takes much longer to run. I know that local variables work in general faster than global ones, but I'd like to know also if there's any other reason involved (like the use of arrays, for instance).

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Well the OS has to physically map the 400MB of memory you basically use as write-only memory.

    That's a lot of memory to write once, read once from.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Dec 2018
    Posts
    13
    Thanks Salem

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 13
    Last Post: 12-09-2008, 11:09 AM
  2. Replies: 10
    Last Post: 04-07-2008, 09:14 AM
  3. Running time
    By wu_weidong in forum Tech Board
    Replies: 1
    Last Post: 09-05-2005, 04:03 PM
  4. Replies: 3
    Last Post: 11-15-2003, 11:20 AM
  5. Replies: 3
    Last Post: 06-13-2003, 06:47 AM

Tags for this Thread