# `clb_divmod` 的设计推理与实测数据 契约(签名、cell 数、吃什么留什么、谁验证)在 [`SPEC.md`](../SPEC.md) §7.6;这里只放 "为什么这么写"和实测数字。原来的位置是 SPEC §14。 ## 1. 为什么换、每轮的状态 旧版 O(N/D):`2047/1` 要 2047 轮、每轮约 2.4k 步,直接撞 2000 万步上限(实测 HANG)。 新版固定 **W 轮**(11 轮),跟 N、D 的值无关。 N 被除数(W 位)。每轮 `rol N`,于是 N 的 LSB 就是**最高位起**的下一位 (rol 把 bit W-1 转到 bit0) —— 转满 W 轮 N 自动复原,所以 N 不被消耗 R 部分余数 = (Rhi:Rlo),Rlo 是普通 cell,Rhi 只有 bit0 有意义(轮内布尔) D 除数(W 位),每轮都要拿它去比/减 → 必须保留 → 这就是 `raw_sub` 存在的理由 Sd 减法结果(W 位,Rlo - D) Bo raw_sub 给的"没借位"(1 表示 Rlo >= D) 每轮:`R = (R << 1) | 位`,然后 `R >= D ? (R -= D, 商位 = 1) : (商位 = 0)`。 ## 2. W+1 位比较拆成"一个 W 位减 + 一个布尔"(实际用到的版本) `R = (Rhi:Rlo)`、`D < 2^W`。先算 `Sd = Rlo - D` 与 `Bo = (Rlo >= D)`,那么 提交(R >= D) ⟺ Rhi == 1 或 Bo == 1 → **commit = Rhi | Bo** 四种情况都对得上(`Rhi = 0, Bo = 0` 就是 `R < D`,不提交)。所以**不需要真的做 W+1 位减法**,只要一个 W 位 `raw_sub`(顺带给出 Bo)+ 一个按位或。 原设计里还有一条 `Shi = Rhi & Bo`("提交后的新高位")和对应的 `clb_bit_and`, **实际实现把它省掉了**:每轮开头 R < D < 2^W(提交之后 R 一定小于 D),所以 Rhi 在轮首恒为 0;而 `Rhi = 1 且 Bo = 1` 这个组合会要求 R = 2^W + Rlo >= 2D,与 "轮首 R < D ⇒ 左移后 R < 2D" 矛盾,不可能出现。于是新高位恒为 0,Rhi 只是轮内的 H,`clb_bit_or` 顺手把它清零就够了 —— 省一个 `clb_bit_and`、一次 copy 和一个变量。 ## 3. 每轮实际骨架(`asm/divmod.r8asm`) .tp N ; rol ; 下一位进 N 的 LSB .tp R ; rol ; clb_bit_mov Rhi ; Rlo 左移,绕回位先搬进 Rhi(顺带清 bit0) .tp N ; bit_copy Rlo buf ; 注入这一位(38 字符,保留 N) raw_sub Rlo D Sd Bo Cm Ci buf ; Sd = Rlo - D,Bo = (Rlo >= D) clb_bit_or Rhi Bo Cm ; 提交条件(两个输入都被吃掉) .tp Q ; rol ; 商左旋一位(bit0 一定是 0) .tp Cm ; biz .tp Sd ; copy R buf ; R = Sd(495 字符,只在提交时跑) .tp Q ; set_1 ; 商位 = 1 .tp Cm ; flb ; 吃掉条件 rnz .tp NR ; set_0 ; ror ; 轮数吃掉一个 7 个草稿格(`S+0..S+6`):Rhi、Sd、Bo、Cm(= `raw_sub` 的 Bc,兼提交标志)、Ci、 buf、NR。固定代价里最大的是 `raw_sub` 的 2793 字符和提交时那个 `copy` 的 495 字符。 ## 4. 坑(都踩过或实测过) 1. **R 的跨格左移顺序**:`rol` 把 Rlo 的最高位绕回 bit0,必须**先**把它搬进 Rhi (`clb_bit_mov` 搬的同时清掉绕回位),**再** `bit_copy` 注入 N 的那一位。 顺序错了就丢位 —— `clb_mul` 当年在这里返工两轮。单点验证驱动是 `drv/div_shift.r8asm`(`r8forge_derive drv/div_shift.r8asm -1 0=1024 2=0 4=1` 等三条,见文件头)。 2. **`biz` 是循环对**:门控提交的 body 最后必须把条件吃掉(`flb`);商位的 `set_1` 和那个 `flb` 合在同一个块里。条件块的身体都回到自己的条件 cell(净位移 0)。 3. **Rhi 只有 bit0 有意义**,它当布尔用,别当字节。 4. **轮数计数器**:`%rep _CELL_SIZE { set_1; ror }` 造出来的就是 W 个 1,轮首的 LSB 已经是 1、**不用再补一条 `rol`** —— 原来的设计笔记里说要补,实测不需要 (`clb_mul` 也是这么用的)。 5. **N 要保留就得用 `bit_copy`**(保留源),不能用 `clb_bit_mov`(吃源);代价是 每轮 38 字符 + 约 40 步。余数因此要单独一格 R(旧版"余数就在 N 里"的约定没有了)。 ## 5. 验收(实测) * **Q/R 逐对比**:`byte_op_test` 的 `test_divmod` 现在跑 **8 个除数 × 全部 2048 个 被除数 = 16384 组**(旧的 76 组抽样表是它的子集),全对;顺带断言 N、D 原样返回。 * **步数**(`drv/divmod.r8asm`,11 位): | 算式 | 旧(重复减法) | 新(移位-恢复) | |---|---|---| | `2047/10` | 495,986 | **28,593** | | `2047/2` | 2,461,650 | **31,997** | | `999/7` | 340,086 | **28,661** | | `2047/1` | **HANG**(>2000 万) | **32,383** | | `7/10` | 3,014 | 25,315 | | `100/7` | 34,940 | 27,460 | 16384 组里最坏 **32,383** 步。**N/D 很小时反而慢**(固定 11 轮),和 `clb_mul` 的取舍一样:拿它换"除数和商再大也不会挂"。 * **`clb_digits`**:`test_digits` 现在**穷举全部 2048 个值**,全对;`0=2047` 从 740,695 步降到 **113,288** 步(最坏 123,755 —— 小值反而慢,同上)。纸带 `clb_digits` **11717**(13 格草稿重排之前 13717,再往前 10829 —— 重排见 SPEC §7.7), `clb_divmod` **4499**(旧 4189)。 **纠正一个流传的数字**:这里原来写"`2047/10` 要 148 万步"、"`clb_digits` 的 1.48M 步"。 按 SPEC §1.3 的口径实测旧实现是 **495,986**(`2047/10`)和 **740,695**(digits `0=2047`), 没有 148 万 —— 那个数不知道是别的驱动还是别的版本量的,**别再引用**。 ## 6. 没做的优化(想让除法再快一档的话) 把"每轮 copy 一份 D 再取反"(`raw_sub` 内部,单轮 2019 步)换成**开循环前预计算 `NegD = ~D`、每轮只跑 `raw_add Rlo NegD Ci Sd Bo buf`**:单轮 973 步(两者都是拿同一 张驱动单独跑出来的),纸带基本不变(循环体 −594、循环外 +518,净 −76)。按这个差值 估计 `clb_divmod` 28.6k → 约 **17.6k** 步(未实测)。没换的原因是 §3 指名用 `raw_sub`、而它是上一轮专门为长除法加的(SPEC §7.8)。真要换的话注意:多一个 NegD 草稿格;`Ci = 1` 在循环外设一次就够(`raw_add` 结束会把 Ci 还原成进入时的值,实测两次 调用都保持 1);`Bo` 语义不变(`A + ~D + 1` 的进位就是"没借位")。