diophantine

std.elementwise.diophantine · Level L4

A solution of the linear Diophantine equation a·x + b·y = c, for a, b ≥ 0: where d = gcd(a, b) divides c, the particular solution x₀ = x·(c/d), y₀ = y·(c/d) from bezout's certificate, and ok = 1. Every solution is then (x₀ + (b/d)t, y₀ − (a/d)t). Where d does not divide c there is none, and ok = 0. a = b = 0 is solvable only for c = 0, by every pair.

a·x + b·y = c, solvable ⇔ gcd(a, b) | c

Signature

diophantine(a: i64[s], b: i64[s], c: i64[s]) → i64[s], i64[s], f64[s]

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 extended Euclid on (a, b); scale by c/g where g | c in exact rational arithmetic, on all 40 test cases.
All 492 float64 results are exact: the error is zero.
Interpreter and NumPy backend return bit-identical results.
At float32 too: the 40 test cases rounded to float32, and 40 of them exact, with zero error.

Accuracy in detail

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

Identity

Calls

bezout

Called by

—

sha256:e5c37de03e98d825e768063df149479b4f4c650bde44652a53769dc993af9776

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

Control handle

Symbol: Ω:std.elementwise.diophantine · Ω:diophantine
Pins: sha256:5b7b017bbe5174429113f3bc9fcc7f233d2c964bf3dceb11d41fb5aa52794590this graph and the 3 it reaches through calls
Evidence: sha256:6dda8551d497f3f124ab95f42d782eba663ce486153b86924a0a33c3e1d7aff1the 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.