所有程序均使用固定种子
20260715(splitmix64
PRNG)和与时钟无关的确定性指标(错误率、收缩步数、比较次数、最大负载、割边数)。
| 文件 | 内容 | 命令 |
|---|---|---|
freivalds_exp.c |
精确整数 / \(\mathbb{F}_p\) / \(\mathbb{F}_2\) Freivalds 矩阵验证、\(2\times 2\) 穷举反例、IEEE-754 浮点失效演示与 \(n=64\) 误判率 | gcc -O2 -Wall -Wextra -o freivalds_exp freivalds_exp.c -lm && ./freivalds_exp |
karger_exp.c |
Karger 与 Karger-Stein 最小割在示例图、双团桥接图、双 6-正则循环图上的单次命中率与总收缩步数对比 | gcc -O2 -Wall -Wextra -o karger_exp karger_exp.c -lm && ./karger_exp |
select_balls_maxcut.c |
QuickSelect 与 BFPRT 比较次数、\(d=1,2,3\) 及 Vöcking 不对称投球最大负载、条件期望与成对独立性 MAX-CUT 去随机化 | gcc -O2 -Wall -Wextra -o select_balls_maxcut select_balls_maxcut.c -lm && ./select_balls_maxcut |
plot_experiments.py |
读取 results.txt 生成
../balls-bins-karger.svg |
python3 plot_experiments.py |
run.sh |
一键编译、执行、ASan+UBSan 检查并重绘 SVG(不残留可执行文件) | sh run.sh |
校验命令
三个 C 程序均以
-O1 -g -Wall -Wextra -fsanitize=address,undefined -fno-sanitize-recover=all
编译并完整运行,无任何警告或 sanitizer 报错。
源码下载
本文相关源码已整理,共 6 个文件。