Added n-ary vector summation

appengine/findit/libs/math/vectors.py

Index: appengine/findit/libs/math/vectors.py
diff --git a/appengine/findit/libs/math/vectors.py b/appengine/findit/libs/math/vectors.py
new file mode 100644
index 0000000000000000000000000000000000000000..2d97d35a554ac3f3a2e9d1d238cb6a375ed2d00e
--- /dev/null
+++ b/appengine/findit/libs/math/vectors.py
@@ -0,0 +1,42 @@
+# Copyright 2016 The Chromium Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+import math
+import numpy as np
+
+
+def vsum(vs, shape=None):
+  """Accurate summation of a list of vectors.

[inferno, 2016/12/05 00:12:37]

Where is this implementation based off ? Can you add wiki link or point to
source.

[wrengr, 2016/12/05 19:06:43]

This implementation is a gross hack to compute the sums element by element,
since mbarbella@ et al thought it wouldn't be worth the maintenance cost to
actually vectorize Shewchuk's algorithm. There is no source to link; though I
can provide links for where numpy said they WontFix their not providing this
function.

+
+  This function is like ``math.fsum`` except operating over collections
+  of vectors rather than collections of scalars.
+
+  Args:
+    vs (list of np.ndarray of float): The vectors to add up.
+    shape (tuple of int): the shape of the vectors. Optional.
+
+  Returns:
+    Returns an ``np.ndarray`` if all is well, otherwise returns
+    ``None``. The situations where all is not well (and so we return
+    ``None``) are: (1) ``vs`` is empty and ``shape`` is not provided;
+    (2) a ``shape`` is provided but does not match the actual shape of
+    the vectors; (3) not all the vectors in the list have the same shape.
+  """
+  if shape is None:
+    if not vs:
+      return None
+
+    shape = vs[0].shape
+
+  # It'd be better to vectorize the implementation of Shewchuk's
+  # algorithm directly, so we can avoid needing to traverse ``vs``
+  # repeatedly. However, this is deemed to have too high a maintinence
+  # cost for the performance benefit.

[inferno, 2016/12/05 00:12:37]

typo: of a maintenance

[wrengr, 2016/12/05 19:06:43]

Done.

+  total = np.zeros(shape)
+  it = np.nditer(total, flags=['multi_index'], op_flags=['writeonly'])
+  while not it.finished:
+    it[0] = math.fsum(v[it.multi_index] for v in vs)
+    it.iternext()
+
+  return total