fixed_point

std.func.fixed_point · Level L3

A fixed point x = g(x), elementwise, by Picard iteration from x₀ until every |g(x) − x| is at most tol. For a contraction with constant q < 1 the iteration converges to the unique fixed point, and the error is then at most q·tol/(1 − q). A While over fixed_point_step; a template over g, verified through g = sigmoid, a contraction with q = 1/4.

x ← g(x) while maxᵢ |g(xᵢ) − xᵢ| > tol

Signature

fixed_point(x0: 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 g = sigmoid: iterate while the largest step is above tol to 80 digits (100-digit arithmetic), on all 40 test cases.
All 169 float64 results inside the running error bound; the closest uses 17% 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 20% of it.

Accuracy in detail

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

Note

NOVA does not check that g is a contraction. Without one the iteration may not converge, and it then reaches max_steps and fails rather than return an iterate.

Identity

Calls

fixed_point_open fixed_point_step

Called by

—

sha256:0ea703eb8dfa1645ac0349b1c89c65b969587085c7d0b333c9173c5989080a0b

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

Control handle

Symbol: Ω:std.func.fixed_point[g=std.elementwise.sigmoid]
Pins: sha256:c69c4c36e48fb793ce268818f9d89ffdac145e6a4c72a3a4942a6b4d237f8da3this graph and the 3 it reaches through calls
Evidence: sha256:88c554e710c9dfc962bbfe892e4cd6992ecce84378763c7f4efe04978292cd85the 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.