Интуитивно понятно, почему попарное суммирование дает меньшую ошибку, чем наивное суммирование. ⇐ Python

[Anonymous]

В документации по numpy sum https://numpy.org/doc/stable/reference/ ... y.sum.html
В нем упоминается, что вместо наивного суммирования используется попарное суммирование. для уменьшения количества ошибок
Я не понимаю, почему попарное суммирование лучше для уменьшения ошибок
Наивное суммирование
При простом суммировании числа складываются последовательно, что дает среднюю ошибку O(sqrt(N)) и в худшем случае O(N)

Код: Выделить всё

sum=(((x1+x2)+x3)+…+xn)

Попарное суммирование имеет среднюю ошибку O(log(sqrt(N))) и худший случай O(logN)
Из Google, попарно улучшает простое суммирование за счет разделения списка чисел на пары, суммирования каждой пары, а затем рекурсивного суммирования результатов. Процесс выглядит следующим образом:

• Первоначальное сопряжение: начните с исходного списка номеров.
  { x1,x2,x3,x4,…,xn
  {x1​,x2​,x3​,x4​,…,xn​
  < /li>
  Суммировать пары: суммировать числа попарно.
  {(x1+x2),(x3+x4),…}
  {(x1​+x2​),(x3​+x4​),…
• Рекурсивное суммирование: повторите процесс с суммы предыдущего шага до тех пор, пока не останется единственная сумма.
  {((x1+x2)+(x3+x4)),…}
  {((x1​+x2​)+(x3​ +x4​)),…

Может кто-нибудь объяснить интуицию, в чем улучшение?
Например
Давайте воспользуемся следующим числом, скажем, мантисса равна 3

Код: Выделить всё

1.01x10^10 + 1.01x10-10 + 1.01x10^10 + 1.01x10-10

Наивное дополнение

Код: Выделить всё

(((1.01x10^10 + 1.01x10-10) + 1.01x10^10) + 1.01x10-10)
(((1.01x10^10 + 1.01x10^10) + 1.01x10-10)
(((2.02x10^10 + 1.01x10-10)
2.02x10^10

Попарное суммирование

Код: Выделить всё

(1.01x10^10 + 1.01x10-10) + (1.01x10^10 + 1.01x10-10)
1.01x10^10  + 1.01x10^10
2.02x10^10

Оба результата дают 2,02x10^10

Подробнее здесь: https://stackoverflow.com/questions/784 ... -summation