inclusion_exclusion

std.sets.inclusion_exclusion · Level L4

Inclusion-exclusion for a finite indexed family S_1 … S_s of subsets of 0 … m − 1 (one row each): the size of the union counted directly, and the alternating sum Σ over all 2^s − 1 nonempty index sets I of (−1)^(|I|+1)|∩_{i ∈ I} S_i|, a While over ie_step. The two agree. Repeated sets are counted by index; stopping after singles and pairs gives only a Bonferroni bound for s ≥ 3.

|∪S_i| = Σ_{∅≠I} (−1)^(|I|+1) |∩_{i∈I} S_i|

Signature

inclusion_exclusion(S: f64[s, m]) → 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.

input
operation
constant
call
output

Verification

Signature proven by NOVA’s shape solver, for every size.
Equal to the reference the union counted, and every nonempty index set in Python in exact rational arithmetic, on all 40 test cases.
All 80 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

growth_step ie_open ie_step

Called by

—

sha256:ed6f0040c0433cdc3fb406ff36e72c6879c69604df9f0bbedc8761d7d750d6d6

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

Control handle

Symbol: Ω:std.sets.inclusion_exclusion · Ω:inclusion_exclusion
Pins: sha256:07dc2d5bd7caa2d65ff1c9f60eeb5e04aa24ed58b85d13292710ec53e68bd4c3this graph and the 3 it reaches through calls
Evidence: sha256:a1079531330ed70386230f85805e4702f5498bf3308b98225656d98777daa670the 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.