Question: 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.

Answer: 
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;

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