Not So Float

Not So Float is a pure TypeScript library that implements Interval Union Arithmetic over IEEE 754 double precision floats (JS numbers).

[!TIP] Try the interval calculator for an interactive demo of interval union arithmetic.

import * as nsf from "not-so-float";

const X = nsf.union([nsf.interval(-10, -1), nsf.interval(100, 120)]);
const Y = nsf.union([nsf.interval(-10, 2)]);
const Q = nsf.div(X, Y);

console.log(`(${X.toString()}) / ${Y.toString()} = ${Q.toString()}`);

([-10, -1] U [100, 120]) / [-10, 2] = [-Infinity, -0.49999999999999994] U [0.09999999999999999, Infinity]

References:

• Hickey, T., Ju, Q. and Van Emden, M.H., 2001. Interval arithmetic: From principles to implementation. Journal of the ACM (JACM), 48(5), pp.1038-1068.
• Schichl, H., Domes, F., Montanher, T. and Kofler, K., 2017. Interval unions. BIT Numerical Mathematics, 57(2), pp.531-556.

Design goals:

• No dependencies
• Functional (stateless) API
• Strong focus on simplicity and clarity of implementation
• No signed zero convention, -0 === 0 should still be true in the context of interval bounds
• Interval bounds are always inclusive
• No empty interval, but empty unions
• Support division by intervals containing zero without compromise

[!TIP] If you like this open-source project consider sponsoring me on GitHub, thank you ❤️

Installation

not-so-float build version is available on npm:

npm install not-so-float

Import the library with:

import * as nsf from "not-so-float";

Outward Rounding

The main interest of interval arithmetic is the inclusion property. Any interval operation result is always guaranteed to contain all possible results obtained from the underlying real operation. However floating point operations are inexact. So we must use outward rounding when computing interval bounds to maintain the inclusion property.

Unfortunately JS doesn't allow controling the IEEE 754 rounding mode, and rounds to the nearest representable float, like most programming languages. This is a computer science tragedy of the first order, because IEEE 754 actually specifies rounding modes that would allow clean implementations of interval arithmetic natively. Instead, we implement two functions: next() and prev() using typed arrays bit manipulation. These functions return the next and previous representable floating point value, exactly like the C function nextafter().

function next(x: number): number;
function prev(x: number): number;

By making sure every interval bound operation rounds outward, we can maintain the inclusion property even with numerical precision errors inherent to floating point.

Interval

An interval is a pair of IEEE 754 double precision numbers called the lower (lo) and upper (hi) bounds:

$$ [\text{ lo}, \text{ hi }] $$

The only restriction is that bounds must always be less or equal: $\text{lo} \leq \text{hi}$. The lower bound may be negative infinity, the upper bound may be positive infinity. This table describes the set of real numbers that an interval represents:

| lo | hi | Interval Type | Represents any $x \in \mathbb{R}$ such that | | :-------: | :-------: | :-----------: | :---------------------------------------------: | | $a$ | $b$ | Real | $a \leq x \leq$ b | | $-\infty$ | $b$ | Semi-Infinite | $x \leq b$ | | $a$ | $+\infty$ | Semi-Infinite | $a \leq x$ | | $-\infty$ | $+\infty$ | Infinite | $x \in \mathbb{R}$ |

Where $a$ and $b$ are real IEEE 754 values (not infinite).
The special case when both bounds are equal is called a degenerate interval.

To construct an interval, use the nsf.interval() function:

nsf.interval(a: number, b: number) : Interval

For example:

> I = nsf.interval(0, 6)
Interval { lo: 0, hi: 6 }

The interval class member functions:

class Interval {
    isFull(): boolean;
    isFinite(): boolean;
    isDegenerate(): boolean;
    contains(value: number): boolean;
    hull(): Union;
    superset(other: Interval): boolean;
    subset(other: Interval): boolean;
    width(): number;
    toString(numbers?: (x: number) => string): string;
    print(): void;
}

Union

A union is an ordered disjoint set of intervals:

$$ [a, b] \cup [c, d] \ldots \cup [e, f] $$

To construct a union, use the nsf.union() function:

function union(list: (Interval | Union)[]): Union

Union class member functions:

class Union {
    isEmpty(): boolean;
    isFull(): boolean;
    isFinite(): boolean;
    isSingle(): boolean;
    equalsSingle(lower: number, upper: number): boolean;
    count(): number;
    lower(): number;
    upper(): number;
    contains(value: number): boolean;
    subset(other: Union): boolean;
    superset(other: Union): boolean;
    hull(): Union;
    width(): number;
    forEach(callback: (x: Interval, index: number) => void): void;
    toString(numbers?: (x: number) => string): string;
    print(): void;
}

For example:

> const U = nsf.union([nsf.inter(1, 2), nsf.inter(4, 6)])
> U.toString()
'[1, 2] U [4, 6]'
> U.intervals
[ Interval { lo: 1, hi: 2 }, Interval { lo: 4, hi: 6 } ]

You can also use the shorthand nsf.single() to construct a singleton, i.e. a union with a single interval:

const U = nsf.single(-0.1, 0.1);

Constants are also provided:

• FULL: all real numbers
• EMPTY: the empty union

Set theory

Compare and compute intervals and unions with the following implementations of set theory operations:

function overlap(A: Interval | Union, B: Interval | Union): boolean;
function disjoint(A: Interval | Union, B: Interval | Union): boolean;
function intersection(A: Interval | Union, B: Interval | Union): Union;
function complement(A: Union | Interval): Union;

Arithmetic

| Operation | API function | | ------------------------------------------: | :----------------- | | Addition | nsf.add(A, B) | | Unary negation | nsf.neg(A) | | Subtraction | nsf.sub(A, B) | | Multiplication | nsf.mul(A, B) | | Division | nsf.div(A, B) | | Exponentiation(integer exponent) | nsf.powInt(A, n) | | Exponentiation(interval/union exponent) | nsf.pow(A, B) |

[!IMPORTANT] Note that every operation returns a union. This is for consistency, because while some operations (add, sub, mul) between intervals can return a single interval, others (division, exponentiation, log, sqrt) can return zero, one or two disjoint intervals even with interval inputs.

Unary Functions

| Operation | API function | | ----------------: | :------------- | | Absolute value | nsf.abs(A) | | Natural logarithm | nsf.log(A) | | Exponential | nsf.exp(A) | | Square root | nsf.sqrt(A) | | Inverse square | nsf.sqinv(A) | | Cosine | nsf.cos(A) | | Sine | nsf.sin(A) | | Tangent | nsf.tan(A) |

Binary Functions

| Operation | API function | | --------: | :-------------- | | Minimum | nsf.min(A, B) | | Maximum | nsf.max(A, B) |

Future improvements

• Support multiple rounding modes
• Improve unit test coverage