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.