code wiki / (root) / sketch_freq_directions_vs_topnorm_bench.nx

sketch_freq_directions_vs_topnorm_bench.nx

buildroot/runtime/sketch_freq_directions_vs_topnorm_bench.nx

6369 B223 linesdepth 5pulls 8 transitivereach 0 importersview sourcekind benchtopic sketch
docsdependenciesstructsconstsfunctions

about

sketch_freq_directions_vs_topnorm_bench.nx -- paired bench, FD vs naive top-norm. CLAIM TO VALIDATE: Frequent Directions reconstructs the true covariance matrix A^T A more accurately than a naive "keep top-l rows by norm" baseline at the same sketch size. Liberty's headline 2013 theorem: ||A^T A - B^T B||_F <= ||A - A_k||_F^2 / (l - k). The naive baseline has no such guarantee -- it discards correlation information. SHARED WORKLOAD: - 50 random rows in d=4 dimensions, Q14 fixed-point in [0, 1) - Both sketches at l = 3 rows - Deterministic LCG generator seeded identically MEASUREMENT: true: G_true = A^T A (4x4 Gram matrix) FD est: G_fd = B_fd^T B_fd (4x4) naive est: G_naive = B_naive^T B_naive (where B_naive = top 3 rows of A by L2 norm) Scalar error metric (Frobenius): fd_err = sum_{i,j} (G_true[i,j] - G_fd[i,j])^2 naive_err = sum_{i,j} (G_true[i,j] - G_naive[i,j])^2 Smaller wins. Reuses nx_cmp_memory(our, theirs, tol) as the "scalar smaller-wins" comparator (the function does NOT care that the inputs are covariance-error rather than literal bytes; smaller-wins is the axis semantics). HARD-WIN GATE: verdict == BEATS with delta_ppm > 10000 (1% improvement).

dependencies 4 imports · 0 importers

syscalls.nx sketch_freq_directions.nx sketch_comparator.nx sketch_types.nx sketch_freq_directions_vs_topn

imports: syscalls.nxsketch_freq_directions.nxsketch_comparator.nxsketch_types.nx

imported by: nobody (leaf or entry point)

structs

none

consts

40const NX_FDB_Q14: i64 = 16384
41const NX_FDB_D: i64 = 4
42const NX_FDB_L: i64 = 3
43const NX_FDB_N: i64 = 50
45const NX_FDB_LCG_A: i64 = 1103515245
46const NX_FDB_LCG_C: i64 = 12345
47const NX_FDB_LCG_MOD: i64 = 0x7FFFFFFF

functions

49func nx_fdb_row_norm_sq(row: *i64, d: i64) -> i64
59func nx_fdb_outer_accumulate(G: *i64, row: *i64, d: i64) -> i64
72func nx_fdb_frob_sq_diff(A: *i64, B: *i64, n: i64) -> i64
83func main() -> i64