Is there a good way to optimise a nested for loop that is multiplying the iterations?-CodePudding

I have a for loop that is creates a sum by multiplying the values in the loop:

int i;
int j;

float total = 0;
int x = 1000;

for (i = 0; i < x; i  )
{
    for (j = 0; j < x; j  )
    {
        total  = i * j;
    }
}

Is there a better way of writing this? When x gets larger, the time it takes to process is incredibly long.

My research suggests that nested for loops are good enough, but I'm wondering if there's a way to simplify this.

CodePudding user response：

You don't want nested loops at all, the closed formula for given x is

total = x * x * (x - 1) * (x - 1) / 4;

Just be careful with integer overflow (note long for both the result and for x)

long x = 1000;
long total = x * x * (x - 1) * (x - 1) / 4;

CodePudding user response：

For your specific case, there is of course a constant-time expression (see Dmitry's answer). For a more general case, you can use

Σi Σj Xi.Yj = (Σi Xi).(Σj Yi)

This turns O(N²) to O(N).