Вычислить сумму

В качестве ещё одного варианта, давайте рассмотрим квадратную таблицу

x1*x1  x1*x2  x1*x3  ...  x1*xn
x2*x1  x2*x2  x2*x3  ...  x2*xn
 ...    ...    ...   ...   ...
xn*x1  xn*x2  xn*x3  ...  xn*xn

Ваша сумма — это сумма всех чисел над главной диагональю, а также сумма всех чисел под главной диагональю (они одинаковы). Поэтому искомая сумма равна сумме всех чисел таблицы минус сумма чисел на главной диагонали, и всё вместе ещё поделить на 2.

Сумма чисел на главной диагонали — это x1 * x1 + x2 * x2 + ... + xn * xn. (n умножений, n - 1 сложение).

А сумма всех чисел таблицы — это просто сумма всех возможных попарных произведений чисел xi и xj, то есть это просто (x1 + x2 + ... + xn) * (x1 + x2 + ... + xn). (Можно легко убедиться, раскрыв скобки.) Таким образом, сумма чисел в таблице вычисляется за n - 1 сложение и одно умножение.

Итого получается 2n - 2 сложений, n + 1 умножение и одно деление на 2 (ну или умножение на 0.5, если хотите).

Ну, может, так?

int sum = 0;
int part = 0;
for(int i = n; i > 1; --i)
{
    sum += x[i-1]*(part += x[i]);
}

Судя по отсутствию реакции, осталось непонятно :)

Сначала вычисляется и прибавляется к sum значение x[n-1]*x[n] и part становится x[n-1]+x[n]

Затем вычисляется и прибавляется к sum значение x[n-2]*(x[n-1]+x[n]), а part становится равным x[n-2]+x[n-1]+x[n]...

Словом, вычисляем с конца, наращивая сумму. Получается n-1 умножений и 2n-2 сложений.

Интересно сравнить варианты @VladD и мой (VC++ 2015).

Вот сравниловка:

using number = double;
const int n = 100000;
vector<number> x(n+1);
inline number Harry()
{
    number sum = 0;
    number part = 0;
    for(int i = n; i > 1; --i)
    {
        sum += x[i-1]*(part += x[i]);
    }
    return sum;
}

inline number VladD()
{
    number sum = x[1];
    for(int i = 2; i <= n; ++i) sum += x[i];
    sum = sum*sum;
    for(int i = 1; i <= n; ++i) sum -= x[i]*x[i];
    return sum/2;
}
int main(int argc, const char * argv[])
{
    for(int i = 0; i < x.size(); ++i)
        x[i] = rand();
    number sum  = 0;
    {
        muTimer mu;
        for(int i = 0; i < 10000; ++i) sum += VladD();
        cout << sum << endl;
    }
    sum = 0;
    {
        muTimer mu;
        for(int i = 0; i < 10000; ++i) sum += Harry();
        cout << sum << endl;
    }
}

Несмотря на просьбы inline, встраивать код компилятор не захотел.
При number = int получаем, что на небольших размерах переполнение куда раньше наступает в методе @VladD. Зато по скорости оно бьет мой метод: 255 против 462 ms. Но если отключить оптимизацию, то получим обратный эффект - 27 против 18 секунд. Связано с тем, что мой метод оптимизатор никак не может соптимизировать до использования XMM-регистров, в отличие от метода @VladD, где полно кода наподобие

$LL4@VladD:
    movups  xmm0, XMMWORD PTR [edx+eax*4]
    paddd   xmm2, xmm0
    movups  xmm0, XMMWORD PTR [edx+eax*4+16]
    add eax, 8
    paddd   xmm1, xmm0
    cmp eax, 99993              ; 00018699H
    jle SHORT $LL4@VladD

Но если взять number = double, то оптимизатор начинает оптимизировать соответствующим образом и мой метод, так что получаем 1670 против 750 ms в мою пользу.

Писано просто так, для тех, кому интересно почитать. Никакой особой морали, так сказать, не вижу... Но раз уж сделал - почему не рассказать? :)