stillwater-sc / universal / 25017180363

84%

master: 84%

push

github

feat(lns): Polynomial and ArnoldBailey add/sub algorithms (Phase C of #777) (#786)

* feat(lns): Polynomial and ArnoldBailey add/sub algorithms (Phase C of #777)

Add the fourth and fifth policies in the configurable lns add/sub
framework: a closed-form polynomial approximation and a
piecewise-linear approximation. Both are zero-table algorithms that
fit the gap between DirectEvaluation (slow but exact) and Lookup
(fast but memory-hungry).

PolynomialAddSub<Lns>
---------------------
Approximates sb_add(d) = log2(1 + 2^d) via the classical (1+x)/(1-x)
substitution: x = u/(2+u) where u = 2^d, mapping u in (0, 1] to
x in (0, 1/3]. The series

    log2((1+x)/(1-x)) = (2/ln 2) * (x + x^3/3 + x^5/5 + x^7/7 + ...)

converges rapidly over the reduced domain. Degree-7 truncation gives
~5.6e-6 absolute error worst-case (the next omitted term, x^9/9 at
x = 1/3, is 5.6e-6).

For sb_sub the analogous substitution (x = u/(2-u)) requires u <= 0.5
to keep x in [0, 1/3]; past that we are in the catastrophic-cancellation
regime where the series diverges, and we fall back to direct
cm::log2/cm::exp2 -- same hybrid pattern as Lookup's sb_sub.

Cost: one transcendental at runtime (the 2^d to recover u from d),
one division, no table. A good fit for general-purpose firmware where
SRAM is at a premium.

ArnoldBaileyAddSub<Lns>
-----------------------
Cheapest of the configurable algorithms: piecewise-linear approximation
matching the function value at integer d-knots (d = 0, -1, -2, ..., -5).
Each piece evaluates as a + b*d -- two multiplies, one add, no
transcendentals at runtime, no table, no division. Knot values are
computed at compile time via cm::log2 so we don't bake in approximate
constants.

Worst-case error ~2.5% relative near d = 0 (where the curvature of
log2(1 + 2^d) is highest), dropping rapidly toward the tail. For
sb_sub we use the same pattern with knots derived from log2(1 - 2^d)
and a direct-evaluation fallback in the cancellation regime u > 0.5
(d > -1)... (continued)

71 of 75 new or added lines in 1 file covered. (94.67%)

45633 of 54096 relevant lines covered (84.36%)

6344194.11 hits per line