Certified range evaluation for elementary real and complex functions

Input: a finite, well-formed, typed expression DAG with one or more designated output nodes; finite real interval or complex rectangle assignments for its input nodes; exact dyadic constants or constants supplied with certified enclosing intervals/rectangles; a finite dyadic format $(p,e_{\min },e_{\max })$ with $p\ge 2$ and $e_{\min }\le e_{\max }$; and an integer truncation index $N\ge 1$. Input interval endpoints and supplied constant enclosures use this format. All constants, including every Machin enclosure of $\pi$, use the same fixed $N$ and format throughout a call. Real nodes support input and constant nodes and the operations $+,-,\times ,÷,\sqrt{\phantom{x}},\exp ,\ln ,\arctan ,\sin ,\cos ,\tan$. Complex nodes support input and constant nodes and $+,-,\times ,÷,\exp ,\mathrm{Log}$. Each operation has homogeneous real or complex inputs of its stated type; no implicit conversion between real and complex nodes is performed. Unsupported node types, arities, or type combinations return inconclusive with the offending node.

Output: a finite interval/rectangle enclosure for every designated output node, or one of empty, entire, domain-error, split-domain, overflow, or inconclusive with the node and unresolved domain piece. If any supplied input is empty, return empty. No value from a system libm routine is treated as a certified endpoint. Each DAG node is evaluated once; shared nodes reuse their interval/rectangle enclosure and do not preserve correlations between distinct paths.

1. Check that node identifiers are unique, all references resolve, every designated output is a node, and the supported node types and arities above hold. Use each supplied input enclosure as its node value. For an exact real dyadic constant $c$, use $[\mathrm{rd}(c),\mathrm{ru}(c)]$ in the selected format. For an exact complex dyadic constant, do this to each coordinate. A finite subnormal endpoint remains a valid endpoint; if a coordinate conversion overflows, return overflow with that constant node. Use a supplied certified constant enclosure as given. Construct a topological order by repeatedly removing a node whose predecessors have already been removed, breaking ties by lexicographically smallest node identifier. If no such node exists before all nodes are ordered, return inconclusive with a node in the cycle. Evaluate nodes in this order and store each finite enclosure for its successors. Arithmetic nodes use Outward-rounded interval, rectangle and ball operations; if an operation returns a non-finite status, propagate it immediately with its node and unresolved piece. For $\sqrt{X}$ require $X\subseteq [0,\mathrm{\infty })$ and for $\ln X$ require $X\subseteq (0,\mathrm{\infty })$; otherwise return domain-error rather than silently discarding points.

2. For a real exponential node, set $s=\max (0,e_{\max }+2)$ using the format in Dyadic floating-point format and directed rounding. Since $N_{\max }<2^{e_{\max }+1}$, exact comparison gives $N_{\max }\mathrm{/}{2}^s<1\mathrm{/}2$. For its input interval $X$, form the exact dyadic interval $U=2^{-s}X$ without storage rounding. Evaluate the degree-$N$ exponential polynomial and add the symmetric tail from Range-reduced exponential, logarithm and arctangent series have certified tails, using ${\max }_{u\in U}\mathrm{\mid }u\mathrm{\mid }<1\mathrm{/}2$, by exact rational interval arithmetic. Round only the resulting interval endpoints outward, then square that interval $s$ times. If its lower endpoint is not positive or an endpoint overflows, return inconclusive or overflow with the node and input interval.

For a real logarithm node, first require $X\subseteq (0,\mathrm{\infty })$. List all integers $j$ for which $X_j=X\cap [2^j,2^{j+1}]$ is nonempty; exact endpoint comparisons find this finite list because $X$ has positive finite endpoints. On each piece form $Y=2^{-j}{X}_j\subseteq [1,2]$ and $V=(Y-1)\mathrm{/}(Y+1)$ by exact rational endpoint formulas without storage rounding, so $V\subseteq [0,1\mathrm{/}3]$. Evaluate the logarithm polynomial and its tail determined by $\max \mathrm{\mid }V\mathrm{\mid }$ by exact rational interval arithmetic, round the result outward, and form $j\ln 2+\ln Y$ by outward arithmetic. Compute the fixed enclosure for $\ln 2$ once by the same series and tail at $y=2$, hence $v=1\mathrm{/}3$, and reuse it in every bin. If any piece cannot be evaluated finitely, propagate its status and that piece. Otherwise take the interval hull of all piece enclosures as the node enclosure.

3. Partition a real arctangent input at the fixed breakpoints $-3,-1,-1\mathrm{/}2,1\mathrm{/}2,1,3$ into nonempty closed pieces, allowing shared endpoints. On pieces in $[-1\mathrm{/}2,1\mathrm{/}2]$, evaluate its alternating power series. For positive pieces in $[1\mathrm{/}2,1]$, use $\arctan t=\pi \mathrm{/}4-\arctan ((1-t)\mathrm{/}(1+t))$; in $[1,3]$, use $\arctan t=\pi \mathrm{/}4+\arctan ((t-1)\mathrm{/}(t+1))$; for $t\ge 3$, use $\arctan t=\pi \mathrm{/}2-\arctan (1\mathrm{/}t)$. Evaluate negative pieces by odd symmetry. Form each reduced interval by exact rational endpoint formulas and evaluate its polynomial and symmetric tail by exact rational interval arithmetic before outward conversion; every reduced argument lies in $[-1\mathrm{/}2,1\mathrm{/}2]$. Combine the converted enclosure with the fixed $\pi$ enclosure by outward arithmetic. Enclose $\pi$ using Machin's identity and the alternating series at $1\mathrm{/}5$ and $1\mathrm{/}239$, forming rational partial sums and tail endpoints exactly before final outward conversion. If every piece is finite, take the interval hull of all piece enclosures. If any branch test or piece is unresolved, return its non-finite status with that piece and do not use a partial hull.

4. For each sine or cosine node, first compute one outward Machin interval $P_N$ for $\pi$ using the same $N$ and format, combining the rational series endpoints exactly before final outward conversion. If $P_N$ is non-finite or its lower endpoint is not positive, return inconclusive. For finite input $X=[a,b]$, put $M_X=\max (\mathrm{\mid }a\mathrm{\mid },\mathrm{\mid }b\mathrm{\mid })$, $p_{-}:=\inf (P_N)>0$, and $K=\lceil 2M_X\mathrm{/}{p}_{-}\rceil +1$, with the ceiling computed by exact rational comparisons. If the width of $X$ is at least $2\sup (P_N)$, outward-round the exact endpoints $-1$ and $1$; if either conversion overflows, return overflow with the node and input interval, and otherwise return the resulting interval. Otherwise examine the finite candidate list $k=-K,\dots ,K$ for the canonical cells $[k\pi \mathrm{/}2-\pi \mathrm{/}4,k\pi \mathrm{/}2+\pi \mathrm{/}4]$. For each candidate form the exact rational interval enclosure $C_k=k{P}_N\mathrm{/}2+[-1\mathrm{/}4,1\mathrm{/}4]P_N$ of its canonical cell. For $k>K$, the exact left endpoint $(2k-1)\pi \mathrm{/}4$ of cell $k$ is at least $(2k-1)p_{-}\mathrm{/}4>M_X$; for $k<-K$, its exact right endpoint $-(2\mathrm{\mid }k\mathrm{\mid }-1)\pi \mathrm{/}4$ is at most $-(2\mathrm{\mid }k\mathrm{\mid }-1)p_{-}\mathrm{/}4<-M_X$. Thus no omitted exact cell can intersect $X$. Include each candidate whose $C_k$ intersects $X$; exclude only candidates whose intersection is empty by exact comparison. Let $X_k$ be the exact interval hull of $X\cap C_k$, without rounding these endpoints, and form the residual enclosure $R_k=X_k-k{P}_N\mathrm{/}2$. Certify $R_k\subseteq [-1,1]$, evaluate the sine polynomial through degree $2N+1$ or the cosine polynomial through degree $2N$, and add the corresponding explicit geometric tail from Trigonometric identities, Machin's formula and reduced Taylor tails by exact rational interval arithmetic. For $j\in \{0,1,2,3\}$ the quarter-period map for a sine node is respectively $\sin r,\cos r,-\sin r,-\cos r$, and for a cosine node it is respectively $\cos r,-\sin r,-\cos r,\sin r$, where $j$ is the least nonnegative residue of $k$ modulo $4$. For a negative sign, negate the interval and reverse its endpoints. Intersect each mapped enclosure with $[-1,1]$. Round the final endpoints outward and take the hull over every included cell. If no candidate is included, a cell cannot be certified in the reduced interval, or any candidate endpoint overflows, return inconclusive or overflow with the cell; never omit that piece from a finite hull.

For tangent, form the same finite canonical-cell list even when the input width meets the wide-input shortcut; do not use that shortcut. For each included cell $k$, form its reduced input interval $R_k$ as above and evaluate sine and cosine on that cell. Divide their enclosures only when the cosine enclosure excludes zero. Otherwise, for odd $k$, form the exact dyadic pole enclosure $K_k=k{P}_N\mathrm{/}2$. If $K_k$ is contained in the cell's input intersection, then $k\pi \mathrm{/}2$ lies in that cell and is a cosine zero, so return split-domain with the cell. If the cosine enclosure contains zero but this pole test does not certify a zero, return inconclusive with the cell. Take the interval hull of tangent enclosures only when every piece is finite.

5. For complex exponential on $X+iY$, evaluate real $\exp (X)$, $\cos (Y)$, and $\sin (Y)$ and combine their enclosures by rectangle operations. For principal $\mathrm{Log}$, first require a rectangle excluding zero and every point of the negative real branch cut; otherwise return domain-error. Compute an outward Machin interval $P_N$ for $\pi$ using this call's $N$ and format; if it is non-finite or its lower endpoint is not positive, return inconclusive. Split each coordinate interval into its nonempty strictly negative and strictly positive portions, plus the singleton $\{0\}$ when it contains zero. Use the closures of the strictly signed portions as interval enclosures; form their Cartesian products for the quadrant pieces, and handle products with an axis singleton separately. Omit empty pieces. These finitely many pieces cover the rectangle, with quadrant closures allowed to overlap their axis pieces. On a quadrant where the denominator interval excludes zero, use $\mathrm{Arg}(x+iy)=\{\begin{array}{ll}\arctan (y\mathrm{/}x),& x>0,y>0,\\ -\arctan ((-y)\mathrm{/}x),& x>0,y<0,\\ \pi -\arctan (y\mathrm{/}(-x)),& x<0,y>0,\\ -\pi +\arctan ((-y)\mathrm{/}(-x)),& x<0,y<0.\end{array}$ Write this call's fixed interval as $P_N=[p_{-},p_{+}]$ and form the exact dyadic sector intervals $S_{\mathrm{I}}=[0,p_{+}\mathrm{/}2],S_{\mathrm{I}\mathrm{I}}=[p_{-}\mathrm{/}2,p_{+}],S_{\mathrm{I}\mathrm{I}\mathrm{I}}=[-p_{+},-p_{-}\mathrm{/}2],S_{\mathrm{I}\mathrm{V}}=[-p_{+}\mathrm{/}2,0]\mathrm{.}$ For every ratio-based quadrant piece, obtain its finite real arctangent enclosure by the real rules above; propagate any non-finite result. Form the full argument interval $A$ in the displayed quadrant formula by exact rational endpoint arithmetic, using this same $P_N$ for each occurrence of $\pi$. Before final outward conversion or hull formation, replace $A$ by $J=A\cap S_q$, where $q$ is that piece's quadrant. Compute the intersection by exact endpoint maxima and minima. If it is empty, return inconclusive with the piece and status empty-argument-intersection; do not omit the piece. If the denominator interval has a zero endpoint, use $J=S_q$ instead of a ratio formula.

For an interval $J=[a,b]$ produced by either branch, apply the same final conversion $H(J)=[\mathrm{rd}(a),\mathrm{ru}(b)]$ in the selected format. Perform this conversion after intersection for a ratio branch and after selecting $S_q$ for a coarse branch. Finite subnormal endpoints are accepted; an overflow returns overflow with the piece. On the positive imaginary axis use $H(P_N\mathrm{/}2)$, on the negative imaginary axis use $H(-P_N\mathrm{/}2)$, and on the positive real axis use $H([0,0])$. The initial domain check excludes the origin and negative real axis, so these are all remaining axis cases.

On each piece enclose $\ln \sqrt{X^2+Y^2}$ using the real operations and evaluator, and combine it with the converted argument interval into a rectangle. If every piece is finite, take the coordinatewise hull of all piece rectangles. If any piece, conversion or branch is unresolved, return its status and piece without forming a partial hull.