divided_differences

std.seq.divided_differences · Level L2

The coefficients of Newton's form of the polynomial through (xⱼ, yⱼ), x distinct: cₖ = f[x₀, …, xₖ], the divided differences. A Scan of divided_difference_step, one order per step, so that p(t) = c₀ + c₁(t − x₀) + … + cₙ₋₁(t − x₀)…(t − xₙ₋₂).

cₖ = f[x₀, …, xₖ] = Σⱼ₌₀ᵏ yⱼ / Πₗ≠ⱼ (xⱼ − xₗ)

Signature

divided_differences(x: f64[n], y: f64[n]) → f64[n]

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ₖ = Σⱼ yⱼ / Πₗ≠ⱼ (xⱼ − xₗ), j, l ≤ k in exact rational arithmetic, on all 40 test cases.
All 150 float64 results inside the running error bound; the closest uses 15% 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 15% of it.

Accuracy in detail

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

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

divided_difference_step

Called by

poly_interp

sha256:22253e3b3a6f62671c3cc6de4c1fee8ccab97fcf270b072ab224cfb4752dd581

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

Control handle

Symbol: Ω:std.seq.divided_differences · Ω:divided_differences
Pins: sha256:d951d4560e71ec777214214408fe8598e1a1eec07c75991aa3add577de9cec82this graph and the 1 it reaches through calls
Evidence: sha256:dac0a392357ae4db567e56200e0a2ab9e9561427edd4ea3cb9c0bdb13e755a81the 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.