4 ms·

Fast exact summation using small and large superaccumulators

31 points by nanis 10y ago

deleted 10y ago
[deleted]
crb002 10y ago
Sort/bucket the abosute value within some epsilon then merge pairwise in a binary tree. Or split FloatMax into 32-2048 bins. Start all at zero. Add incoming numbers to the corresponding bin. If a bin goes out of range zero it and add the sum where it needs to go. When you are done keep adding the lowest magnitude bin to the next highest.
dzdt 10y ago
Related blog post : https://radfordneal.wordpress.com/2015/05/21/exact-computation-of-sums-and-means/ https://radfordneal.wordpress.com/2015/05/21/exact-computati... As someone who has worked with building, testing, and numerical software, this seems like a great thing. Generally floating point computations are effectively non-deterministic: you (or the compiler) change something that doesn't seem like it matters and all of a sudden your result changes. Having more methods available that give you the deterministically best right thing at little additional expense is great!
- dchapp 10y ago
  You might be interested in ReproBLAS too.(http://bebop.cs.berkeley.edu/reproblas/ http://bebop.cs.berkeley.edu/reproblas/) It uses a different approach than superaccumulators, which as far as I know was first explored for the purpose of determinizing parallel floating-point sums by the folks working on ExBLAS (https://exblas.lip6.fr/ https://exblas.lip6.fr/)
- Chris2048 10y ago
  Was the software you worked on a general numerics platform, or something more specialised? I'm trying to learn more about the topic myself, from a finance perspective.
  - al2o3cr 10y ago
    This technique seems like overkill for most finance applications - you can fit nearly any sensible currency amount into a 64-bit fixed-point number (or a 128-bit if you're doing whole-economy calculations).
simonbyrne 10y ago
Funny coincidence. I happened to point to some papers and code for superaccumulators in a StackOverflow answer yesterday: http://stackoverflow.com/a/41741276/392585 http://stackoverflow.com/a/41741276/392585
- nanis 10y ago
  Thank you. That's where I saw this.

31 points by nanis 10y ago

deleted 10y ago

[deleted]

Sort/bucket the abosute value within some epsilon then merge pairwise in a binary tree. Or split FloatMax into 32-2048 bins. Start all at zero. Add incoming numbers to the corresponding bin. If a bin goes out of range zero it and add the sum where it needs to go. When you are done keep adding the lowest magnitude bin to the next highest.

dzdt 10y ago

Related blog post : https://radfordneal.wordpress.com/2015/05/21/exact-computation-of-sums-and-means/ https://radfordneal.wordpress.com/2015/05/21/exact-computati... As someone who has worked with building, testing, and numerical software, this seems like a great thing. Generally floating point computations are effectively non-deterministic: you (or the compiler) change something that doesn't seem like it matters and all of a sudden your result changes. Having more methods available that give you the deterministically best right thing at little additional expense is great!

dchapp 10y ago
You might be interested in ReproBLAS too.(http://bebop.cs.berkeley.edu/reproblas/ http://bebop.cs.berkeley.edu/reproblas/) It uses a different approach than superaccumulators, which as far as I know was first explored for the purpose of determinizing parallel floating-point sums by the folks working on ExBLAS (https://exblas.lip6.fr/ https://exblas.lip6.fr/)
Chris2048 10y ago
Was the software you worked on a general numerics platform, or something more specialised? I'm trying to learn more about the topic myself, from a finance perspective.
- al2o3cr 10y ago
  This technique seems like overkill for most finance applications - you can fit nearly any sensible currency amount into a 64-bit fixed-point number (or a 128-bit if you're doing whole-economy calculations).

simonbyrne 10y ago

Funny coincidence. I happened to point to some papers and code for superaccumulators in a StackOverflow answer yesterday: http://stackoverflow.com/a/41741276/392585 http://stackoverflow.com/a/41741276/392585

nanis 10y ago
Thank you. That's where I saw this.