summary refs log tree commit diff stats
path: root/lib/std/sums.nim
diff options
context:
space:
mode:
Diffstat (limited to 'lib/std/sums.nim')
-rw-r--r--lib/std/sums.nim80
1 files changed, 0 insertions, 80 deletions
diff --git a/lib/std/sums.nim b/lib/std/sums.nim
deleted file mode 100644
index a6ce1b85d..000000000
--- a/lib/std/sums.nim
+++ /dev/null
@@ -1,80 +0,0 @@
-#
-#
-#            Nim's Runtime Library
-#        (c) Copyright 2019 b3liever
-#
-#    See the file "copying.txt", included in this
-#    distribution, for details about the copyright.
-
-## Accurate summation functions.
-
-{.deprecated: "use the nimble package `sums` instead.".}
-
-runnableExamples:
-  import std/math
-
-  template `~=`(x, y: float): bool = abs(x - y) < 1e-4
-
-  let
-    n = 1_000_000
-    first = 1e10
-    small = 0.1
-  var data = @[first]
-  for _ in 1 .. n:
-    data.add(small)
-
-  let result = first + small * n.float
-
-  doAssert abs(sum(data) - result) > 0.3
-  doAssert sumKbn(data) ~= result
-  doAssert sumPairs(data) ~= result
-
-## See also
-## ========
-## * `math module <math.html>`_ for a standard `sum proc <math.html#sum,openArray[T]>`_
-
-func sumKbn*[T](x: openArray[T]): T =
-  ## Kahan-Babuška-Neumaier summation: O(1) error growth, at the expense
-  ## of a considerable increase in computational cost.
-  ##
-  ## See:
-  ## * https://en.wikipedia.org/wiki/Kahan_summation_algorithm#Further_enhancements
-  if len(x) == 0: return
-  var sum = x[0]
-  var c = T(0)
-  for i in 1 ..< len(x):
-    let xi = x[i]
-    let t = sum + xi
-    if abs(sum) >= abs(xi):
-      c += (sum - t) + xi
-    else:
-      c += (xi - t) + sum
-    sum = t
-  result = sum + c
-
-func sumPairwise[T](x: openArray[T], i0, n: int): T =
-  if n < 128:
-    result = x[i0]
-    for i in i0 + 1 ..< i0 + n:
-      result += x[i]
-  else:
-    let n2 = n div 2
-    result = sumPairwise(x, i0, n2) + sumPairwise(x, i0 + n2, n - n2)
-
-func sumPairs*[T](x: openArray[T]): T =
-  ## Pairwise (cascade) summation of `x[i0:i0+n-1]`, with O(log n) error growth
-  ## (vs O(n) for a simple loop) with negligible performance cost if
-  ## the base case is large enough.
-  ##
-  ## See, e.g.:
-  ## * https://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.
-  ##
-  ## In fact, the root-mean-square error growth, assuming random roundoff
-  ## errors, is only O(sqrt(log n)), which is nearly indistinguishable from O(1)
-  ## in practice. See:
-  ## * Manfred Tasche and Hansmartin Zeuner, Handbook of
-  ##   Analytic-Computational Methods in Applied Mathematics (2000).
-  let n = len(x)
-  if n == 0: T(0) else: sumPairwise(x, 0, n)