Loop optimization in C

Question

I am tasked with optimizing the specific for the loop in C. Here is the loop:

#define ARRAY_SIZE 10000
#define N_TIMES    600000

for (i = 0; i < N_TIMES; i++)
{
    int j;

    for (j = 0; j < ARRAY_SIZE; j++)
    {
        sum += array[j];
    }
}

I have to use loop reversal, loop breaks and pointers to speed it up, but every time I try to implement something, the program does not return. Here is what I have tried so far:

for (i = 0; i < N_TIMES; i++) 
{
    int j,k;

    for (j = 0; j < ARRAY_SIZE; j++) 
    {    
        for (k = 0; k < 100; k += 2) 
        {
            sum += array[k];
            sum += array[k + 1];
        }
    } 
}

I do not understand why the program did not even return. Any help would be appreciated.

Answer 1

This second part of the code is inefficient and incorrect because it adds more values ​​than the source code.

Scrolling the loop (or decreasing in this case, since you probably do not want to expand the loop of ten thousand iterations), will be:

// Ensure ARRAY_SIZE is a multiple of two before trying this.
for (int i = 0; i < N_TIMES; i++)
    for (int j = 0; j < ARRAY_SIZE; j += 2)
        sum += array[j] + array[j+1];

, , . - , , , .

. , , , :

int temp = 0;
for (int i = 0; i < ARRAY_SIZE; i++)
    temp += array[i];
sum += temp * N_TIMES;

O(n), n (, ). , gcc -O3 , . .

, : -)

Answer 2

... . 50 , ...

2 fors: 600.000 * 10.000 = 6.000.000.000 .

3 fors: 600.000 * 10.000 * 50 = 300.000.000.000 ...

Answer 3

Loop , . , . , .

. , . array[j] i, , , .

( ) . , - :

sum += *arrayPointer++;

Instead of using j, provided that it will be initialized accordingly. But I doubt that you will get anything from him.

According to the comments, if it was real life, you just let the compiler display this stuff.