суммы

Быстрые функции суммирования.

Пример:

static:
  block:
    const data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    doAssert sumKbn(data) == 45
    doAssert sumPairs(data) == 45

Импорты

math

Функции

func sumKbn[T](x: openArray[T]): T

Суммирование по методу Кахана-Бабушки-Неймайера: рост ошибки O(1) в ущерб значительному увеличению вычислительных затрат. Исходный код Изменить

func sumPairs[T](x: openArray[T]): T

Парное (каскадное) суммирование x[i0:i0+n-1], с ростом ошибки O(log n) (по сравнению с O(n) для простого цикла) с незначительными затратами производительности, если базовый случай достаточно большой.

См., например:

• http://en.wikipedia.org/wiki/Pairwise_summation Higham, Nicholas J. (1993), "The accuracy of floating point summation", SIAM Journal on Scientific Computing 14 (4): 783–799.

Фактически, рост среднеквадратического отклонения, предполагая случайные ошибки округления, составляет всего O(sqrt(log n)), что практически неотличимо от O(1) на практике. См.:

• Manfred Tasche and Hansmartin Zeuner, Справочник по аналитическим и вычислительным методам в прикладной математике (2000).

Исходный код Изменить