The BFS used to walk the whole 1<<CELL_SIZE table for every edge, keep the
states in an unordered_set and the parents in a second unordered_map. For
the six plane full adder layer 4 is 642729 states, and layer 5 never
finished (75s, heading for GBs).
A state is now CELL_SIZE bit planes, each a truth table over only the
inputs that influence the answer, so a state is CELL_SIZE * 2^K bits --
48 bits for every adder-shaped problem -- and a block is a handful of
64-bit ops. The instruction list also lost its duplicated encodings
(378 instead of 762 for six planes).
The bigger win is not expanding the last layer at all. A block clears its
own plane, so for the goal to be its target goal[s] must be 0; the
preimages of the goal under each such block are enumerated exactly and
looked up in the BFS table. For full_add that is 9.3e3 lookups instead of
7.4e9 edges, which turns "unreachable" into "5 blocks, proven shortest,
7 seconds".
Results (r8veritas<6>, max_depth 5, MSVC /O2):
copy 2 33 states
clb_and 3 3398
clb_half_add 4 32898
half_add 4 32898
full_add_S 4 656528
full_add_Co 5 20388515
full_add 5 20388515 7.2s
All of those lengths are proven minimal, and the old bit_raw_add needed
eight blocks for the same slice.
Richer instruction sets were tried as well -- per destination OR/XOR, and
adding set_0 on top (6144 blocks) -- and neither admits a four-block full
adder, so five is not an artifact of the model.
CELL_SIZE stays a template parameter; the truth table compression picks K
at run time and dispatches on it. CMake flags got the same fix as r8asm:
stop clobbering CMAKE_CXX_FLAGS so Debug keeps /RTC1 and MSVC keeps /EHsc.
R8Veritas
ROT-8 / R8ASM 的最短程序搜索器。
给两个真值表(输入 → 输出),找最短的一段中间代码把它算出来;代码可以直接翻译成
R8ASM 的 biz 块。
中间代码
一条指令(一层)就是一个 biz 块:
.tp s
biz
.tp b ; mask 里每一位一条
set_1 / flb
.tp s
flb
rnz
s是被牺牲的那一位:块的条件是bit s,块结束时它一定被清掉mask里的每一位b会被cond(bit s为 1 的那些输入)或上 / 异或上- 一层 = 一个块,所以长度 = 层数
这些位来自不同的 cell,是调用方传进来的参数(%1..%n),一层只是一次条件重写。
状态与位平面
一个状态是整张真值表:每个输入组合下,这些位各自的值。
按位平面来存(plane[b] = 所有输入下第 b 位的取值),一层就变成几个 64 位操作:
cond = plane[s]; plane[s] = 0;
for b in mask: plane[b] |= cond (set_1)
plane[b] ^= cond (flb)
compress_stat_space 会先清掉不影响答案的输入 —— 加法器这类问题上往往只剩 3 个相关输入,
于是每个 plane 只是一张 8 bit 真值表,整个状态 48 bit,塞得进一个 uint64_t。
参数个数是模板参数 CELL_SIZE,搜索里没有写死。
搜索
- 前向 BFS 到第 d−1 层,每个状态记下它是哪条指令、从哪个状态来的
- 最后一层不前向展开。因为指令会清掉自己的平面,目标态必须满足
goal[s] == 0; 对每个合法的块,把目标的全部一步前驱枚举出来(异或目的地唯一,或目的地按位自由), 拿这些前驱去 BFS 表里查 - 找到了 → 长度 d 且最优(前 1..d−1 层已经穷尽)
- 没找到 → 展开第 d 层,继续
最后一步反向查表是性能的关键:full_add 上第 5 层直接展开要算
19.7e6 × 378 ≈ 7.4e9 条边,而枚举目标的 1 步前驱只有 9.3e3 次查表。
反向枚举要遍历
cond的2^K种取值,所以只在K <= 3时启用;K > 3时最后一层仍然前向展开。
结果
r8veritas<6>,max_depth = 5(单核,MSVC /O2):
| 问题 | 最短层数 | 状态数 | 用时 | 最优性 |
|---|---|---|---|---|
| copy (A → bit0,bit1) | 2 | 33 | 0.0005 s | 证明 |
| clb_and (A&B → bit2) | 3 | 3,398 | 0.0008 s | 证明 |
| clb_half_add | 4 | 32,898 | 0.008 s | 证明 |
| half_add | 4 | 32,898 | 0.008 s | 证明 |
| full_add_S (S → bit3) | 4 | 656,528 | 0.10 s | 证明 |
| full_add_Co (Co → bit4) | 5 | 20,388,515 | 7.1 s | 证明 |
| full_add | 5 | 20,388,515 | 7.2 s | 证明 |
full_add 的最短程序(%1..%6 对应 6 个参数 cell):
sacrifice %1, FLIP {%2,%3,%6}
sacrifice %2, FLIP {%1,%4,%6}
sacrifice %3, FLIP {%1,%2,%5,%6}
sacrifice %4, SET1 {%3,%5}
sacrifice %6, FLIP {%1,%2,%3,%4,%5}
output_ins(..., false) 打出来就是 5 个 r8asm 块,可以直接替换 raw_add.r8asm 里的
bit_raw_add(那一版是 8 个块)。
试过但没能把层数压到 4 的做法
full_add 上,下面每一种都做了穷尽搜索,都没有 4 层解:
| 放宽方式 | 指令数 | 搜索规模 | 结论 |
|---|---|---|---|
| 每目的地独立选 OR / XOR | 1,458 | 前向 3 层 1.73e6 状态 + 反向 20,096 前驱 | 无 4 层 |
再加 set_0(&~cond) |
6,144 | 前向 3 层 9.56e6 状态 + 反向 40,928 | 无 4 层 |
| 参数从 6 个加到 7 / 8 个 | 2,040(8 个时) | 穷尽 5.4e6 / 44.1e6 状态 | 无 4 层 |
| 条件位 ≠ 牺牲位 | 2,304 | 前向 3 层 3.17e6 状态 + 反向 1,280 | 无 4 层 |
最后一种是这套指令里唯一能让条件位活下来的写法:
.tp s
biz
.tp b
set_1 ; 目的地可以各自选 set_1 / flb / set_0
.tp t
set_0 ; rnz 测的是这里,t 才是被清掉的那个
rnz
它比原模型严格更强(原模型只能 s == t),但 full_add 仍然要 5 层。
至于完全不牺牲:biz/rnz 的循环必须让 rnz 测到的那个 cell 变成 0 才会退出,
所以一层里清掉某一位是硬约束,只能换位置,不能取消。
还能往哪儿走
一层 = 一个条件块这个粒度下,full_add 的地板就是 5。要在 4 层以内,只能让一层表达力更强, 剩下的方向是复合条件:
.tp %1
biz
.tp %2
biz
... ; 条件变成 %1 AND %2
.tp %7
set_0
rnz
.tp %6
set_0
rnz
嵌套 biz 在 ROT-8 里完全合法,于是一层可以写好几个「与」条件的小块,
Co = AB|AC|BC 就能在一层里用三个 A&B 小块直接置位。层数能掉到 2–3,
但磁带会变长(每个小块自带一组 biz/set_0/rnz)。
也就是「层数最少」和「代码最短」在嵌套条件下会分叉,得先确定要哪个指标。
用法
#include "r8veritas.hh"
r8veritas<6> v;
v.initialize_nicknames();
v.initialize_tp_paths();
auto raw = v.generate_truthtable([](r8veritas<6>::cell inp) -> r8veritas<6>::cell {
// 这里写你要算的函数
});
auto compressed = v.compress_stat_space(raw);
r8veritas<6>::options opt;
opt.max_depth = 5;
auto res = v.solve(compressed, opt);
if (res.found) {
v.print_program(res.program, std::cout, false); // 直接是 r8asm
v.run_program(compressed, res.program); // 拿参考语义复核一遍
}
res.proven_optimal 为真表示:res.program 的长度已经被穷尽搜索证明是最短的。
限制
- 相关输入最多 6 个(状态要塞进 64 位字里)
- 反向查表需要
2^K小(K <= 3),否则最后一层仍按前向展开 options.max_states是内存闸门,撞到它会返回「搜索未完成」而不是假装最优