Discuss
  • Directed rounding

Directed rounding

# Martin von Gagern (9 years ago)

Hello,

I'm getting the impression that the next version of EcmaScript after 2015 (congratulations to that, by the way) will support quite advanced numerical computations, with SIMD and all that. To complement that, I'd wish for support for directed rounding. I'd like to have intrinsics to perform elementary arithmetic operations with controlled rounding, in particular rounding to positive and negative infinity, but for the sake of completeness also towards and away from zero. Note that this is about rounding the float mantissa as part of an arithmetic operation, and not rounding to integers as Math.round does it.

The applications I have in mind could be summarized as certified numerical computation results. When a numerical computation is being used as the basis for some decision making, that decision may be affected by rounding errors. One way to deal with the situation is by performing the computations in question using interval arithmetic. If the final result contains zero, its sign is unknown, so the decision cannot be reliably made, and the application can react appropriately.

One example of why this is needed could be the CGAL library. It's a C++ library of geometric operations, like e.g. convex hull. Many of these operations can only work if the underlying number type allows for exact evaluation of predicates, which can be achieved by doing reasonably fast interval arithmetic in most cases, but slow arbitrary-precision rational arithmetic if numerical precision is insufficient. It would be nice if similar code could be written in ES as well.

I don't want to ask for a ready-to-use interval arithmetic library in ES (although I wouldn't mind if you decided that this would be preferable). Such a library could be implemented in application code. But performing interval arithmetic usually relies on directed rounding, to ensure that the interval bounds will expand as required. This is supported by hardware, and it would be nice if that hardware support could be made available to the application, since reproducing the same in software is hardly efficient (but can be done for the sake of compatibility on low-end devices).

What I envision is one object per rounding mode, which contains methods for elementary arithmetic operations: at least addition, subtraction, multiplication and division. Additional operations could be added to that, e.g. a fused multiply and add, or a square root, or even some trigonometric functions or anything else you might find in the Math object. But I'd say that these additional methods shoul only be available if the hardware supports the operations in question. That way the burden for the ES implementation is low, since it doesn't have to implement a bunch of correctly-rounding special functions, and the application can make informed decisions about how to choose between different possible computations in order to maximize efficiency.

If you want to see a code example, something like this should become possible for applications:

const down = Math.directedRounding("-Infinity"); const up = Math.directedRounding("+Infinity");

function interval(lo, hi) { this.lo = lo; this.hi = hi; }

interval.prototype.add = function(that) { return new interval(down.add(this.lo, that.lo), up.add(this.hi, that.hi)); }

It would be nice to have similar functionality for floating-point SIMD types as well. Not sure whether these should be methods of the SIMD constructor or of the directed rounding objects envisioned above.

I don't know if any of this has been suggested before, but if it has, I couldn't find it. If there is some interest in following this up, I'll be glad to help in whatever way I can to get this properly specified. I'd welcome any useful pointers though, as I haven't followed the ES specification process closely, and haven't contributed to it at all.

Greetings, Martin von Gagern

# Martin von Gagern (9 years ago)

Hello!

Would you consider providing intrinsic functions for directed rounding, to encapsulate the corresponding features of IEE 754 floating point computations (resp. the fesetround function of C99)? That would be useful for mathematical applications, in particular when implementing interval arithmetic for exact predicates.

I wrote about this before, on June 20, but probably that post was way too verbose, since I didn't receive any reaction at all. So I'll keep the initial post short this time.

Thanks for any comment, Martin von Gagern

# C. Scott Ananian (9 years ago)

fesetround would be a terrible way for JavaScript to implement this, as it would allow a piece of code to affect the behavior of completely unrelated pieces of code by screwing with global rounding mode bits. That's not going to happen.

I believe there have been proposals to allow greater access to IEEE floating point intrinsics, and I suspect they were better engineered for modularity. Perhaps one of the other readers of this list remembers enough details to give you a good citation.

# Martin von Gagern (9 years ago)

Hello Scott,

Thanks for the comment!

On 26.08.2015 17:22, C. Scott Ananian wrote:

fesetround would be a terrible way for JavaScript to implement this,

I agree, the stateful nature of rounding mode is a pain, and should be kept in a tightly closed locker. I was more thinking about a method which sets the rounding mode to something specific, then performs one particular operation in that mode before resetting the mode to default. This would encapsulate the needed functionality without exposing its stateful nature. Of course engines would be encouraged to detect sequences of calls to such intrinsics, and to avoid the mode changes between operations with the same mode. But that's just implementation improvements for the sake of performance, once the semantics are there.

I believe there have been proposals to allow greater access to IEEE floating point intrinsics, and I suspect they were better engineered for modularity.

Better engineered than fesetround? That's easy, I think. Better engineered than my post? Easy as well, since I kept it to the bare minimum. My previous post was more detailed. See esdiscuss.org/topic/directed-rounding or perhaps this example from that post:

  const down = Math.directedRounding("-Infinity");
  const up = Math.directedRounding("+Infinity");

  function interval(lo, hi) { this.lo = lo; this.hi = hi; }

  interval.prototype.add = function(that) {
      return new interval(down.add(this.lo, that.lo),
                          up.add(this.hi, that.hi));
  }

Perhaps one of the other readers of this list remembers enough details to give you a good citation.

I would welcome any pointers in this regard. Searching the Gmane archives, I couldn't find any. Perhaps that was because many search term combinations I could think of resulted in lots of messages dealing with decimal arithmetic, one way or another.

Greetings, Martin

# C. Scott Ananian (9 years ago)

I think the "better idea" would be related to value types ( www.slideshare.net/BrendanEich/value-objects2) which brendan is working on for ES7. I fuzzily recall rounding modes being used as an example in one of these slide decks, perhaps I am misremembering.

At any rate, one option would be for "round down float" and "round up float" to be separate value types. It seems broadly similar to your proposal, except that you could use actual operators. The lower range in an interval would be a "round down float" and the upper range a "round up float".

# Waldemar Horwat (9 years ago)

On 08/26/2015 13:12, C. Scott Ananian wrote:

I think the "better idea" would be related to value types (www.slideshare.net/BrendanEich/value-objects2) which brendan is working on for ES7. I fuzzily recall rounding modes being used as an example in one of these slide decks, perhaps I am misremembering.

At any rate, one option would be for "round down float" and "round up float" to be separate value types. It seems broadly similar to your proposal, except that you could use actual operators. The lower range in an interval would be a "round down float" and the upper range a "round up float".

It doesn't make sense to encode a rounding mode such as "round down" into a value type. If you multiply it by -1, half of the time it will start doing the wrong thing.

Instead, you want functions that perform the primitive operations (+, -, *, /, sqrt, sin, etc.) in a rounding mode specified by the name of the function or perhaps a third parameter. This must be stateless, not carrying a rounding mode with a value or (even worse) in some global environment.

 Waldemar
# Martin von Gagern (9 years ago)

On 26.08.2015 23:37, Waldemar Horwat wrote:

It doesn't make sense to encode a rounding mode such as "round down" into a value type. If you multiply it by -1, half of the time it will start doing the wrong thing.

I agree: If this were implemented using a value type, then I'd envision myself converting between types all the time, since the rounding mode is indeed a property of the operation, not the value. User-definable value types would be very useful to build (multi-precision?) interval arithmetic on top of the directed rounding, though.

Instead, you want functions that perform the primitive operations (+, -, *, /, sqrt, sin, etc.) in a rounding mode specified by the name of the function or perhaps a third parameter.

I wonder which of these would be easier for engines to optimize.

Detecting certain functions and inlining them during JIT compilation is already established, I think. Turning that third parameter into some machine-specific code is likely harder, but shouldn't be too hard as long as the third parameter is a literal or some constant. But this is my guessing, without too much knowledge about how intrinsics are actually handled during compilation.

On the other hand, if that parameter might change, i.e. if you want to perform the same computation repeatedly with different rounding modes, then a parameter might be better than passing different combinations of functions as arguments. I can think of no real-world application where the same lengthy operation would be performed with different rounding modes, due to the sign change issues you already mentioned. But it might be worthwhile to investigate open source code which is using fesetround and friends to see whether I'm missing some application here.

Greetings, Martin von Gagern