Conservative interval arithmetic library in Javascript

Question

Is there a good existing library for conservative interval arithmetic in Javascript?

By conservative I mean that given two intervals representing ranges of real numbers (whose endpoints happen to be floating point), their interval sum contains all sums of real numbers from the original intervals, and similarly for the other operations. The only library found by a quick search is https://github.com/Jeff-Tian/JavaScriptIntervalArithmetic, but it doesn't appear to be conservative.

Since we don't have access to rounding modes, it's fine (actually preferable for speed) if the intervals aren't optimal. For example, it would be fine if the square of a number was conservatively approximated by [(1-epsilon)*(x*x),(1+epsilon)*(x*x)], even though this is larger than the optimal floating point interval.

`interval sum contains all sums of real numbers` There are infinitely many real numbers between any two real numbers, so this would always be _Infinity_, no? — Paul S., Apr 15 '14 at 02:15
@PaulS: It might help to think about the simpler example of "conservative integer arithmetic". For example, [2,10]/[3,3] = [0,4] in conservative integer arithmetic, since the noninteger bounds are rounded outwards ([2/3,10/3] isn't an integer interval). — Geoffrey Irving, Apr 18 '14 at 08:06
@GeoffreyIrving `⅔ ∉ ℤ`, I know, but the first mention of _integers_ is in your comment. Was integer implied by the word "conservative"? The word really tripped me up, I took it to mean "smaller payload" than the what you linked. If the only issue is that of the _integers_, then it can be _"solved"_ using `Math.floor(a), Math.ceil(b)` for the end-points. — Paul S., Apr 18 '14 at 12:07
@PaulS: Integer occurred first in that comment because I was constructing a simpler example for you. The question is about conservative floating point arithmetic. You still need to round from the exact real number answers to conservative floating point bounds. — Geoffrey Irving, Apr 18 '14 at 23:01
So you want to know how big the floating point error is from a real solution, then put bounds either side, or something? i.e. `x * y ∈ [a, b]`, but the issue then becomes "how do you calculate this error". Maybe [**this question**](http://stackoverflow.com/questions/588004/is-floating-point-math-broken) and [**it's answers**](http://stackoverflow.com/a/588014/1615483) will be interesting for you. — Paul S., Apr 19 '14 at 12:53
I already know several different ways to write the library I want. I am asking whether it already exists. — Geoffrey Irving, Apr 19 '14 at 23:14

score 3 · Accepted Answer · answered May 12 '15 at 18:36

Have a look at https://github.com/maurizzzio/interval-arithmetic whose intervals represent floating point numbers bounding it with the next/previous double-precision floating point number that can be represented

var Interval = require('interval-arithmetic');

// { lo: 0.3333333333333333, hi: 0.3333333333333333 }
new Interval().singleton(1 / 3); 

// { lo: 0.33333333333333326, hi: 0.33333333333333337 }
new Interval().boundedSingleton(1 / 3);

Typed Arrays now provide a way to deal with the bytes that make a double-precision floating number, the library modifies the last bit of the significand of this representation here and all operations carry over this rounding error

score 0 · Answer 2 · answered Apr 15 '14 at 02:36

I'm not quite sure what you mean by "conservative" but I guess adding to the prototype of Array should be faster than creating custom objects, and you only need implement the methods you want.

Array.prototype._interval_plus = function (arr2) {
    return [this[0] + arr2[0], this[1] + arr2[1]];
};
Array.prototype._interval_minus = function (arr2) {
    return [this[0] - arr2[0], this[1] - arr2[1]];
};
Array.prototype._interval_multiply = function (arr2) {
    var ac = this[0] * arr2[0],
        ad = this[0] * arr2[1],
        bc = this[1] * arr2[0],
        bd = this[1] * arr2[1];
    return [Math.min(ac, ad, bc, bd), Math.max(ac, ad, bc, bd)];
};
Array.prototype._interval_divide = function (arr2) {
    var ac, ad, bc, bd;
    if (arr2[0] === 0 || arr2[1] === 0)
        throw new Error('division by zero');
    ac = this[0] / arr2[0],
    ad = this[0] / arr2[1],
    bc = this[1] / arr2[0],
    bd = this[1] / arr2[1];
    return [Math.min(ac, ad, bc, bd), Math.max(ac, ad, bc, bd)];
};
Array.prototype._interval_pow = function (arr2, pow) {
    var ac = this[0] * Math.pow(arr2[0], pow),
        ad = this[0] * Math.pow(arr2[1], pow),
        bc = this[1] * Math.pow(arr2[0], pow),
        bd = this[1] * Math.pow(arr2[1], pow);
    return [Math.min(ac, ad, bc, bd), Math.max(ac, ad, bc, bd)];
};

Now you can do stuff like

var x = [ 0  ,  1  ];
    y = [ 0.5,  3.5];
x._interval_plus(y)     // [ 0.5 ,   4.5 ]
 ._interval_multiply(y) // [ 0.25,  15.75]
 ._interval_minus(y)    // [-0.25,  12.25]
 ._interval_pow(y, 2);  // [-3.0625, 150.0625]

That might be helpful for speed, but is entirely orthogonal to the question of conservativeness. — Geoffrey Irving, Apr 18 '14 at 08:07

Conservative interval arithmetic library in Javascript

2 Answers2