sqrt_newton

std.seq.sqrt_newton · Level L3

√a by Newton's method, starting from (a + 1)/2 and stopping once |s² − a| ≤ 10⁻¹²·a: a While over newton_sqrt_step until sqrt_unconverged says stop.

s ← (s + a/s)/2 while |s² − a| > 10⁻¹²·a

Signature

sqrt_newton(a: f64[]) → f64[]

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.

af64[]1.0Addap10.5Multiplys0While·newton_sqrt_steprootrootf64[]
  • input
  • operation
  • constant
  • call
  • output

Verification

  • Signature proven by NOVA’s shape solver, for every size.
  • Equal to the reference s = (a + 1)/2; while |s*s - a| > 1e-12*a: s = (s + a/s)/2 in exact rational arithmetic, on all 40 test cases.
  • All 40 float64 results inside the running error bound; the closest uses 13% of it.
  • Interpreter and NumPy backend return bit-identical results.
Accuracy in detail
correctly rounded (the float64 nearest the exact value)
83%
bit-equal to the NumPy formula in float64
100%
largest error, in units in the last place
0.69

Note

The number of steps depends on a. The verification follows each case's exact path and checks that every stopping decision is certain, farther from the threshold than its own rounding error, so the float run takes the same steps.

Identity

sha256:9b78fc76abe4de47c75435d85f422d8200c58dbac4d553a9ef1c14c237c36ebe

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

Control handle

Symbol
Ω:std.seq.sqrt_newton · Ω:sqrt_newton
Pins
sha256:41be4d55c13e2ecd8c828cc5f52d7bd6a676cf6d1c3b58ac15e4c83f1f6a72b0this graph and the 2 it reaches through calls
Evidence
sha256:13ccd006fde4246a97889ec90c33446b706b24b6724815721ba1c84036922e14the 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.