bezout

std.elementwise.bezout · Level L4

The extended Euclidean algorithm on each pair of non-negative integers: their greatest common divisor g and Bézout coefficients x and y with a·x + b·y = g. A While with six int64 states (Round 14.10): the remainders and both coefficient sequences, carried side by side.

g = gcd(a, b) = a·x + b·y

Signature

bezout(a: i64[n], b: i64[n]) → i64[n], i64[n], i64[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.
Equal to the reference extended Euclid: r, s, t sequences from (a, b), (1, 0), (0, 1) in exact rational arithmetic, on all 40 test cases.
All 495 int64 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 int64 nearest the exact value): 100%
bit-equal to the NumPy formula in int64: 100%
largest error, in units in the last place: 0

Note

A pair with b = 0 gives g = a, x = 1, y = 0. Lamé's bound keeps pairs below 10⁶ within 35 steps; max_steps is 64.

Identity

Calls

bezout_running bezout_step

Called by

—

sha256:e26a75297edb1374d58004a6792e5409d539fa3203ef006f7554fc749e9bce56

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

Control handle

Symbol: Ω:std.elementwise.bezout · Ω:bezout
Pins: sha256:ac3c21bceb9921b64b151d537e31380f005b5a0137d2cc242582395732e48769this graph and the 2 it reaches through calls
Evidence: sha256:dbe3c5152d1e1873c105357f4fc4de8a2b3de547dd6ebb51cd12c3eebe77194fthe 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.