newton_eval

std.seq.newton_eval · Level L2

Evaluate a polynomial in Newton's form, c₀ + c₁(t − x₀) + … + cₙ₋₁(t − x₀)…(t − xₙ₋₂), at each t, by Horner's rule: a reverse Scan of newton_horner_step.

p(t) = Σₖ cₖ·Πⱼ₌₀ᵏ⁻¹ (t − xⱼ)

Signature

newton_eval(c: f64[n], x: f64[n], t: f64[q]) → f64[q]

Structure

The function as NOVA stores it: one box per input, operation and output, and arrows that carry values. A double border marks another library function this one runs — called once, or by Scan once per element; select it to open that function.

input
operation
constant
call
output

Verification

Signature proven by NOVA’s shape solver, for every size.
Equal to the reference Σₖ c[k]·Πⱼ<ₖ (t − x[j]) in exact rational arithmetic, on all 40 test cases.
All 143 float64 results inside the running error bound; the closest uses 58% of it.
Interpreter and NumPy backend return bit-identical results.
At float32 too: the 40 test cases rounded to float32, and 40 of them inside the running error bound at u = 2⁻²⁴; the closest uses 77% of it.

Accuracy in detail

correctly rounded (the float64 nearest the exact value): 74%
bit-equal to the NumPy formula in float64: 72%
largest error, in units in the last place: 12

Large ulp counts appear where a result is tiny next to the numbers it is computed from (after cancellation, for example), so one unit in the last place is tiny too; the absolute error is still inside the bound. Results within their own error of zero are not counted.

Identity

Calls

newton_horner_step

Called by

poly_interp

sha256:2da5ed9846240f538f7c59219caac3e46239a7031c418d58cae9f0988c63404c

The semantic hash of the graph. It changes when the program changes, and never when only its documentation does.

Control handle

Symbol: Ω:std.seq.newton_eval · Ω:newton_eval
Pins: sha256:0bac7858772e318cfef158589a88683765b1af8371a1e8d010f41c211b5c6885this graph and the 1 it reaches through calls
Evidence: sha256:94116e057d0a16540dfd538a83ab124585cf5e5f9db1399f2e5168f2489b8750the hash of its verification record
Needs: no capability: a pure function

Through NOVA’s control layer, the symbol launches this function only while the program still matches what it pins: a change to this graph, or to any graph it reaches, needs a migration first.