crt

std.elementwise.crt · Level L4

The Chinese remainder theorem: the x in 0 … M − 1, M = m₁·…·mₙ, with x ≡ rᵢ (mod mᵢ) for every i, for pairwise coprime moduli. A Scan of crt_step over the congruences. The solution is unique modulo M, not as an integer.

x ≡ rᵢ (mod mᵢ), i = 1 … n

Signature

crt(r: i64[n], m: i64[n]) → i64[], i64[]

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 x = 0, M = 1; for each (r, m): x += M*((r - x)*pow(M, -1, m) % m); M *= m in exact rational arithmetic, on all 40 test cases.
All 80 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

The moduli must be pairwise coprime; NOVA does not check it, and for moduli that are not, the result need not satisfy the congruences. Exact while M stays below 2⁵³: the verification multiplies up to eight distinct primes below 100.

Identity

Calls

crt_step

Called by

—

sha256:d1a4c6b0a457c6f3fc2d7c5040b4981e12b1ff3a4bae06993045ec4dfa9a6272

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

Control handle

Symbol: Ω:std.elementwise.crt · Ω:crt
Pins: sha256:ab94f6476ca315e77ff3665477b9354333ce85eddeef62d63dae48ab448d6cb5this graph and the 4 it reaches through calls
Evidence: sha256:17eefeda5f034bb6490c32fc521d87e0d8c021f4a5f3512040e5f3ccda203568the 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.