Finite barycentric interpolation evaluator

The inputs are a natural number $n\ge 0$, a floating-point system $(\mathbb{F},N_{\min },N_{\max },\mathrm{fl})$ satisfying The standard relative floating-point model and unit roundoff, finite arrays $X$ and $Y$ of real candidate nodes and data, and a real query $x$. No length assumption is imposed on $X$ or $Y$; their intended lengths are $n+1$, which the procedure checks. The output is either a record with status success and a value in $\mathbb{F}$, or one of the statuses invalid_nodes, invalid_data, and range_failure.

Use checked operations as follows. For $a,b\in \mathbb{F}$ and $\circ \in \{+,-,\times ,÷\}$, return range_failure if division has $b=0$ or if the exact real result $a\circ b$ is nonzero and outside the normal range $N_{\min }\le \mathrm{\mid }a\circ b\mathrm{\mid }\le N_{\max }$. Otherwise return $\mathrm{fl}(a\circ b)$, using the exact-zero rule when the result is zero. Each checked operation has the tagged outcome either range_failure or a value in $\mathbb{F}$; if an operation in a displayed sequence returns range_failure, stop before evaluating the next operation and return that status. Thus $\mathrm{fl}$ is called only on arguments in the domain of the stated model.

Procedure:

1. If the node array has length other than $n+1$, any node is not in $\mathbb{F}$, or the nodes are not strictly increasing, return invalid_nodes. If the data array has length other than $n+1$, or any data value or the query is not in $\mathbb{F}$, return invalid_data.
2. If $x=x_i$ for some $i$, return success with value $y_i$.
3. If $1\mathrm{\notin }\mathbb{F}$, return range_failure. Otherwise, for each $j=0,\dots ,n$, initialize $d_j=1$. For each $k=0,\dots ,n$ with $k\mathrm{\ne }j$, compute $\delta ={\mathrm{checked}}_{-}(x_j,x_k)$ and then replace $d_j$ by ${\mathrm{checked}}_{\times }(d_j,\delta )$. After this inner loop set $w_j={\mathrm{checked}}_{÷}(1,d_j)$. Any checked-operation failure returns range_failure.
4. Initialize $N=0$ and $D=0$. For each $j=0,\dots ,n$, compute ${\delta }_j={\mathrm{checked}}_{-}(x,x_j)$, $u_j={\mathrm{checked}}_{÷}({\mathrm{checked}}_{\times }(w_j,y_j),{\delta }_j)$, and $v_j={\mathrm{checked}}_{÷}(w_j,{\delta }_j)$. Replace $N$ by ${\mathrm{checked}}_{+}(N,u_j)$ and $D$ by ${\mathrm{checked}}_{+}(D,v_j)$. Any checked-operation failure returns range_failure.
5. If $D=0$, return range_failure. Otherwise return success with value ${\mathrm{checked}}_{÷}(N,D)$, unless that final checked operation returns range_failure.

The exact-arithmetic target of steps 3–5 is the quotient in Barycentric interpolation identities. This finite-arithmetic procedure provides no forward-error bound, conditioning guarantee, or accuracy certificate; close or widely separated nodes can cause a range failure or an inaccurate successful value.