randomized-algo 复现程序

目录

所有程序均使用固定种子 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 个文件。

打开下载目录 →


By .