1918708 - [Meta] Implement the Math.sumPrecise proposal

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement, P2)

Description

[Dan Minor [:dminor]]

Making a separate bug to track the implementation.

Comment 1

[Dan Minor [:dminor]]

For implementation, I think we should go with the Shewchuk's algorithm (https://github.com/tc39/proposal-math-sum/blob/main/Shewchuk-robust-arithmetic.pdf), it's relatively simple, and used, for example, by Python's implementation of the equivalent functionality. The proposal author has written a polyfill that could be used as the basis for a self-hosted implementation, or converted to C++.

Comment 2

[bakkot]

I would recommend looking into faster algorithms than Shewchuk; e.g. this library (which has a bug, but the author is working on a fix).

If you really do want to stick with Shewchuk, you might want to look at CPython's implementation, though it will need a little bit of tweaking to handle intermediate overflow. My JS implementation was designed only for correctness, not performance.

Comment 3

[bakkot]

The library I linked (xsum) is fixed now. It's MIT licensed, incidentally.

Comment 4

[Dan Minor [:dminor]]

We don't currently have any Python licensed code, and I don't think we'd want to go through the license review requirements just for this, so I don't think we'd use their implementation directly. I like Shewchuk because of the simplicity, relatively small amount of code, and the fact that it's being used by other language implementations.

The xsum implementation looks bigger and more complicated, although admittedly there are a lot of utility and debugging functions in there, so it might not be as large as it seems at first glance. It might make sense to start with it, and see if fuzzing turns up any problems. We can always fallback to an implementation of Shewchuk if necessary.

Thanks for the suggestions :)

Comment 5

[bakkot]

Yeah, xsum has a handful of other high-precision algorithms we don't need here. The actual library is just two files, xsum.h and the xsum.c, and if you strip those down to just the relevant functions - xsum_small_init, xsum_small_add1, xsum_small_addv, and xsum_small_round and their transitive callees - it ends up being ~500 lines plus comments and # IFs etc.

Usage is simple:

  xsum_small_accumulator sacc;
  xsum_small_init(&sacc);
  FOR_EACH_ITEM (ITEMS, v) {
    xsum_small_add1(&sacc, v);
  }
  double result_s = xsum_small_round(&sacc);

or if you already have an array of doubles in contiguous memory:

 xsum_small_accumulator sacc;
 xsum_small_init(&sacc);
 xsum_small_addv(&sacc, ITEMS, ITEMS_LENGTH);
 double result_s = xsum_small_round(&sacc);

Comment 6

[Dan Minor [:dminor]]

I think Debadree is going to take over the implementation of this proposal.

Comment 7

[Debadree Chatterjee]

Yes, I am working on it! should be ready with patches soon! thank you for the opportunity once again :-)