stillwater-sc / universal / 37881109786

86%

master: 84%

push

github

feat(poxel): enclosing sqrt for tile_interval and the quadratic-roots application (#1649)

* feat(poxel): enclosing sqrt for tile_interval and the quadratic-roots application

sqrt for tile_interval needs no extra precision. The tile of t * t, for
an exact lattice point t, contains t^2 exactly, so comparing its key
with v orders t^2 against v without rounding. A bisection over the
lattice finds the largest t with t^2 <= v. sqrt(v) is t itself if t * t
is exactly v, and otherwise lies in the open tile above t.
- The interval sqrt applies this at both ends, since sqrt is monotone.
  Open ends stay open.
- An interval reaching below zero is restricted to its non-negative
  part; one entirely below zero gives nan.
- tile_sqrt is the single-tile, sticky-flag counterpart.
- Tests: every tile and small hull of poxel<8,0>, poxel<9,2>,
  areal<8,2> and areal<9,3>, checked exactly as L^2 <= x <= U^2 with
  strict open ends. Exact inputs must give the single containing tile,
  in agreement with tile_sqrt.
- Five mutations are caught: never the open tile above, a strict search
  comparison, an open lower end not moved inward, the wrong neighbour
  for an open upper end, and an upper end one tile too far in.

applications/precision/ubit/quadratic_roots.cpp bounds both roots of
3x^2 + 100x + 2 by the quadratic formula (The End of Error, pp. 181-184).
- It compares half, posit, float and double (relative errors), single
  tiles, and tile intervals at 16, 32 and 64 bits (equal storage).
- Each root is computed by the textbook formula and by the stable
  r1 = 2c / (-b - sqrt(d)).
- Inputs are exact, or ULP-wide (the open tile above 3, 100 and 2).
- Every enclosure is verified exactly in einteger arithmetic: signs of
  q(x) and q'(x) at the dyadic endpoints, checked against each corner
  polynomial for ULP-wide inputs. The same test, run as a bisection
  over the tiles, gives the tightest enclosure.

Measured:
- The textbook r1 spans 1365+ tiles at 32 and 64 bits, agai... (continued)

31 of 31 new or added lines in 1 file covered. (100.0%)

47171 of 54628 relevant lines covered (86.35%)

9995546.6 hits per line