newton

std.func.newton · Level L3

Solve f(x) = y elementwise by Newton's method from x₀, given f and its derivative df, until every residual |f(x) − y| is at most tol. A While over newton_step. A template over f and df, verified through f = softplus and df = sigmoid, which inverts softplus; a test takes √2 as the root of x² = 2.

x ← x − (f(x) − y)/df(x) while maxᵢ |f(xᵢ) − yᵢ| > tol

Signature

newton(x0: f64[n], y: f64[n], tol: f64[]) → 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.
Agrees with the reference witness f = softplus, df = sigmoid: Newton steps while the largest residual is above tol to 80 digits (100-digit arithmetic), on all 40 test cases.
All 137 float64 results inside the running error bound; the closest uses 20% of it.
Interpreter and NumPy backend return bit-identical results.
At float32 too: the 40 test cases rounded to float32, and 30 of them inside the running error bound at u = 2⁻²⁴; the closest uses 16% of it. Uncertified, too ill-conditioned at float32 for a finite bound: 10.

Accuracy in detail

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

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.

Note

df must be f's derivative for Newton's convergence, but NOVA does not check that: a wrong df is a different, well-defined iteration. tol must be above the rounding of f near the root, or the loop reaches max_steps and fails rather than return an unconverged x. The verification follows each case's exact path and checks that every stopping decision is certain. It takes y in [1/4, 8¼]: for y near 10⁵, the first step from x₀ = −8 overshoots to about 10⁸, where the oracle's Sigmoid bound, which takes the input error through |σ′| ≤ 1/4 at every x, is too loose to decide when to stop.

Identity

Calls

newton_step newton_unconverged

Called by

—

sha256:1074fed36a1c82c79489b0c957c27aab0aa2087ed8dd1eec830e25c8bec1f424

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

Control handle

Symbol: Ω:std.func.newton[df=std.elementwise.sigmoid,f=std.elementwise.softplus]
Pins: sha256:83cac11330389da8a7830d76f34a18f94b56bf01431c911934603e445052e4b5this graph and the 5 it reaches through calls
Evidence: sha256:271728a5decc5ce88e76bc01b2cd94b9dc1bbbf1a10677bf474879b50d262c8cthe 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.