{"action":"created","issue":{"url":"https://api.github.com/repos/nim-lang/Nim/issues/9284","repository_url":"https://api.github.com/repos/nim-lang/Nim","labels_url":"https://api.github.com/repos/nim-lang/Nim/issues/9284/labels{/name}","comments_url":"https://api.github.com/repos/nim-lang/Nim/issues/9284/comments","events_url":"https://api.github.com/repos/nim-lang/Nim/issues/9284/events","html_url":"https://github.com/nim-lang/Nim/pull/9284","id":368693162,"node_id":"MDExOlB1bGxSZXF1ZXN0MjIxODEwODc0","number":9284,"title":"Add summation algorithms","user":{"login":"b3liever","id":43617260,"node_id":"MDQ6VXNlcjQzNjE3MjYw","avatar_url":"https://avatars3.githubusercontent.com/u/43617260?v=4","gravatar_id":"","url":"https://api.github.com/users/b3liever","html_url":"https://github.com/b3liever","followers_url":"https://api.github.com/users/b3liever/followers","following_url":"https://api.github.com/users/b3liever/following{/other_user}","gists_url":"https://api.github.com/users/b3liever/gists{/gist_id}","starred_url":"https://api.github.com/users/b3liever/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/b3liever/subscriptions","organizations_url":"https://api.github.com/users/b3liever/orgs","repos_url":"https://api.github.com/users/b3liever/repos","events_url":"https://api.github.com/users/b3liever/events{/privacy}","received_events_url":"https://api.github.com/users/b3liever/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":9,"created_at":"2018-10-10T14:26:07Z","updated_at":"2018-11-11T18:51:19Z","closed_at":null,"author_association":"CONTRIBUTOR","pull_request":{"url":"https://api.github.com/repos/nim-lang/Nim/pulls/9284","html_url":"https://github.com/nim-lang/Nim/pull/9284","diff_url":"https://github.com/nim-lang/Nim/pull/9284.diff","patch_url":"https://github.com/nim-lang/Nim/pull/9284.patch"},"body":"Please pick one:\r\n```nim\r\nfunc sumKbn*[T: SomeFloat](v: Indexable[T]): T =\r\n   # Kahan (compensated) summation: O(1) error growth, at the expense\r\n   # of a considerable increase in computational expense.\r\n   if len(v) == 0: return\r\n   var sum = v[0]\r\n   var c = T(0)\r\n   for i in 1 ..< len(v):\r\n      let vi = v[i]\r\n      let t = sum + vi\r\n      if abs(sum) >= abs(vi):\r\n         c += (sum - t) + vi\r\n      else:\r\n         c += (vi - t) + sum\r\n      sum = t\r\n   result = sum + c\r\n\r\nfunc sumPairwise[T](v: Indexable[T], i0, n: int): T =\r\n   if n < 128:\r\n      result = v[i0]\r\n      for i in i0 + 1 ..< i0 + n:\r\n         result += v[i]\r\n   else:\r\n      let n2 = n div 2\r\n      result = sumPairwise(v, i0, n2) + sumPairwise(v, i0 + n2, n - n2)\r\n\r\nfunc sumPairs*[T: SomeFloat](v: Indexable[T]): T =\r\n   # Pairwise (cascade) summation of v[i0:i0+n-1], which O(log n) error growth\r\n   # [vs O(n) for a simple loop] with negligible performance cost if\r\n   # the base case is large enough.  See, e.g.:\r\n   #        http://en.wikipedia.org/wiki/Pairwise_summation\r\n   #        Higham, Nicholas J. (1993), \"The accuracy of floating point\r\n   #        summation\", SIAM Journal on Scientific Computing 14 (4): 783–799.\r\n   # In fact, the root-mean-square error growth, assuming random roundoff\r\n   # errors, is only O(sqrt(log n)), which is nearly indistinguishable from O(1)\r\n   # in practice.  See:\r\n   #        Manfred Tasche and Hansmartin Zeuner, Handbook of\r\n   #        Analytic-Computational Methods in Applied Mathematics (2000).\r\n   let n = len(v)\r\n   if n == 0: T(0) else: sumPairwise(v, 0, n)\r\n\r\nfunc msum*[T: SomeFloat](v: Iterable[T]): T =\r\n   ## Full precision sum of values in iterable. Returns the value of the\r\n   ## sum, rounded to the nearest representable floating-point number\r\n   ## using the round-half-to-even rule\r\n   var partials = newSeq[T]()\r\n   for x in v:\r\n      var x = x\r\n      var i = 0\r\n      for y in partials:\r\n         var y = y\r\n         if abs(x) < abs(y):\r\n            swap(x, y)\r\n         let hi = x + y\r\n         let lo = y - (hi - x)\r\n         if lo != T(0):\r\n            partials[i] = lo\r\n            i.inc\r\n         x = hi\r\n      setLen(partials, i + 1)\r\n      partials[i] = x\r\n   result = sum(partials)\r\n```"},"comment":{"url":"https://api.github.com/repos/nim-lang/Nim/issues/comments/437694608","html_url":"https://github.com/nim-lang/Nim/pull/9284#issuecomment-437694608","issue_url":"https://api.github.com/repos/nim-lang/Nim/issues/9284","id":437694608,"node_id":"MDEyOklzc3VlQ29tbWVudDQzNzY5NDYwOA==","user":{"login":"b3liever","id":43617260,"node_id":"MDQ6VXNlcjQzNjE3MjYw","avatar_url":"https://avatars3.githubusercontent.com/u/43617260?v=4","gravatar_id":"","url":"https://api.github.com/users/b3liever","html_url":"https://github.com/b3liever","followers_url":"https://api.github.com/users/b3liever/followers","following_url":"https://api.github.com/users/b3liever/following{/other_user}","gists_url":"https://api.github.com/users/b3liever/gists{/gist_id}","starred_url":"https://api.github.com/users/b3liever/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/b3liever/subscriptions","organizations_url":"https://api.github.com/users/b3liever/orgs","repos_url":"https://api.github.com/users/b3liever/repos","events_url":"https://api.github.com/users/b3liever/events{/privacy}","received_events_url":"https://api.github.com/users/b3liever/received_events","type":"User","site_admin":false},"created_at":"2018-11-11T18:51:19Z","updated_at":"2018-11-11T18:51:19Z","author_association":"CONTRIBUTOR","body":"What you want me to do to close this PR?"}}
{"actor":{"display_login":"b3liever"}}