pub struct ExactRange {
pub min: f64,
pub max: f64,
}Expand description
The magnitudes of leaves for which an exact stage is valid: every
nonzero leaf x must satisfy min <= |x| <= max. Both are powers of two.
A leaf is an input coordinate for the raw form, the computed difference
for a difference form with Leaves::One, and each of the two
coordinates that are subtracted for a difference form with
Leaves::Two.
§Why the range is sufficient
Write m = min, M = max and u = 2^-53.
Grid. A nonzero f64 of magnitude at least m, a normal power of
two, is an integer multiple of q = m 2^-52; so is zero. For a power of
two g, the rounding of a multiple of g to f64 is a multiple of g:
where the spacing of f64 near the value is at least g, every f64
there is a multiple of g; where it is smaller, the value is
representable and rounds to itself. Every error-free transformation
returns a rounded value and the exact difference between the true result
and it, so with multiples of g as inputs (of g_a g_b for a product of
multiples of g_a and g_b) both outputs are multiples of g. Hence
every value an evaluation handles, every component of the expansion of a
node included, is a multiple of the node’s grid: q for a leaf (also
for both components of a difference two_diff(a, b), which can be far
below m after cancellation but are still multiples of q), the smaller
grid of the operands for a sum, and the product of the grids for a
product. A nonzero component is at least its grid in magnitude; for a
node of degree g in the leaves, the grid is q^g.
Magnitude. Each error-free transformation turns inputs a, b
into x + y = r, where r is a + b or a b, with |y| <= u |x|;
then |x| <= |r| / (1 - u) and |x| + |y| <= (1 + 3u)(|a| + |b|), or
(1 + 3u) |a| |b| for a product. Follow the multiset of values an
evaluation holds (pending inputs, with the factor of a scaling applied,
and outputs): its sum of magnitudes grows by at most a factor 1 + 3u per
transformation, and the output expansion is part of it. So the sum of the
magnitudes of the components of a node, and every value handled on the
way, is at most (1 + 3u)^T S <= (1 + 6uT) S, where T <= 2^51 is the
number of transformations the node depends on, counted with multiplicity
(see the operation counts below), and S follows the structure: M for
a coordinate or a computed difference, 2M for the two components of a
difference of coordinates, |n| for a constant n, the sum of the
operands’ S for a sum or difference, their product for a product.
Rule. The range is the widest pair of powers of two within
[operand_min, operand_max] such that, for every operand of every
product, the grid is at least operand_min and (1 + 6uT) S is at most
operand_max, and (1 + 6uT) S < 2^1020 at every node. Every factor
of every exact product is then zero or in the product domain, and no value
overflows. The grid condition depends only on m and the magnitude
conditions only on M, and both are monotone, so the two ends are found
separately.
The operation counts, with l_x the worst-case length of x: a
difference of two coordinates is one transformation; a sum or difference
at most 2 (l_x + l_y); a product at most 3 l_x l_y for the exact
products of the scalings plus 4 l_x l_y (l_x + l_y) for merging them,
whichever operand is scaled and in whatever order the scalings are
merged.
Fields§
§min: f64The smallest admissible magnitude of a nonzero leaf.
max: f64The largest admissible magnitude of a leaf.