Find sum of elements in the array

Наткнулся на задачу, которую предлагают в Yandex на собеседовании:

Ниже приведены три варианта суммирования чисел с плавающей точкой (предполагается, что числа в массиве только положительные).

double sum1(std::vector<double>& v)
{    
    if (v.empty()) {
        return 0.0;
    }
    for(size_t i = 0; i < v.size() - 1; ++i) {
        std::sort(v.begin()+i, v.end());
        v[i+1] += v[i];
    }
    return v.back();
}

<...>

Остальные варианты пока нам не интересны, их можно посмотреть тут (кстати, в последнем варианте бесконечный цикл). Зачем тут лишняя сортировка ясно сразу — предполагается, что точности double не хватит для расчетов. Ведь если суммировать числа от больших к меньшим, то сумма быстро растёт, и, когда мы дойдём до маленьких чисел, они могут быть денормализованы с огромной ошибкой.

Чтобы оценить о каком порядке ошибки идет речь посмотрим на следующий пример:

const double x = 0.01;
double s = 1000000000.; // initial sum
for (int i = 0; i < 10000; ++i ) {
    s = s + x;
}
const double e = 1000000100. - s;
std::cout << e << std::endl;

На моей машине он выдает результат: 9.53674e-05

Итого, простое суммирование чисел в худшем случае имеет ошибку, которая растет пропорционально \(n\), и среднеквадратичную ошибку, которая растет как \(\sqrt n\) на случайных данных.

Однако, хочется суммировать без ошибок и при этом делать это не за линейно-логарифмическое время \(O(n\log n)\), а за линейное \(O(n)\). Это нам позволяет алгоритм автора стандарта IEEE 754, Уильяма Мортона Кэхэна (Kahan). Он разработал алгоритм для минимизации ошибки при сложении чисел в представлении IEEE 754, который был назван в его честь. Предыдущий пример с учетом алгоритма Кэхэна:

const double x = 0.01;
double c = 0; // keep error here, initial error is zero
double s = 1000000000.; // initial sum
for (int i = 0; i < 10000; ++i ) {
    const double y = x - c;
    const double t = s + y;
    c = (t - s) - y; // Beware eagerly optimising compilers!
    s = t;
}
const double e = 1000000100. - s;
std::cout << e << std::endl;

В итоге выдает 0.

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