CODEWITHSUNDEEP
c#algorithmoptimizationnested
Karma
Karma

Reputation: 31

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

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.

Upvotes: 2

Views: 135

Answers (2)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186718

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;

Edit: let's have a look at general case, where we have to work with arbitrary numbers, say, arrays a and b:

long total = 0;

for (int i = 0; i < a.Length; ++i)
  for (int j = 0; j < b.Length; ++j)
    total += a[i] * b[j];

We can't propose closed formula in this case, but we can optimize the computation. We are looking for the total of

  a[0] * b[0] + a[0] * b[1] + ... + a[0] * b[m] +
  a[1] * b[0] + a[1] * b[1] + ... + a[1] * b[m] +
  ...
  a[n] * b[0] + a[n] * b[1] + ... + a[n] * b[m] = 


= a[0] * (b[0] + b[1] + ... + b[m]) +
  a[1] * (b[0] + b[1] + ... + b[m]) +
  ...
  a[n] * (b[0] + b[1] + ... + b[m]) =


= (a[0] + a[1] + ... a[n]) * (b[0] + b[1] + ... + b[m])

So far so good, instead of nested loops and O(n * m) complexity we have two separated loops and just O(n + m) time complexity.

Often we do such tasks with a help of Linq:

using System.Linq;

...

long total = a.Sum(item => (long) item) * b.Sum(item => (long) item)

But you can well use good old loops:

long sumA = 0;

foreach (var item in a)
  sumA += item;

long sumB = 0;

foreach (var item in b)
  sumB += item;

long total = sumA * sumB;

Upvotes: 8

user1196549
user1196549

Reputation:

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).

Upvotes: 2

Related Questions