Repeated subtraction ran N/D rounds and hit the 5M step ceiling for D = 1
(2047/1 hangs outright); it also cost 2.46M steps for 2047/2. Binary long
division is fixed at _CELL_SIZE rounds whatever the operands are:
R = 0 ; Q = 0
repeat _CELL_SIZE: R = (R << 1) | next bit (rol N hands the bits out
MSB first and restores N
after W rounds)
if R >= D: R -= D ; quotient bit = 1
The one non obvious part is the comparison. R needs W+1 bits after the shift,
but the high bit (H, the bit rol wraps out of Rlo) only has to decide the
commit: H = 1 means R >= 2^W > D, so commit = H | Bo, where Bo is raw_sub's "no
borrow" (Rlo >= D). SPEC 14's Shi = H & Bo is always 0 under the invariant "R
< D at the start of every round" (H = 1 and Bo = 1 together would need R >= 2D),
so that clb_bit_and and its copy do not exist in the built version.
Signature is now clb_divmod N D Q R S: N and D survive, Q and R each get their
own cell (the old version ate N into the remainder), and S is a 7 cell scratch
block (Rhi, Sd, Bo, Cm, Ci, buf, NR). Only S+5 (the copy buffer) has to be
clean on entry; the rest is rewritten or used as a single bit, which is what
lets clb_digits pass the same dirty block back in every round.
The order that cost clb_mul two reworks is the delicate bit: rol Rlo wraps its
top bit into bit 0, so clb_bit_mov has to move that bit into Rhi (which also
clears it) before bit_copy injects N's bit. bit_copy (not clb_bit_mov) is what
keeps N intact.
Measured on drv/divmod.r8asm (11 bit):
repeated subtraction shift-and-restore
2047/10 495,986 28,593
2047/2 2,461,650 31,997
999/7 340,086 28,661
2047/1 HANG (>5M) 32,383
Small N/D get slower (fixed W rounds) -- the same trade clb_mul made. Worst
case over the sweep is 32,383 steps; the tape grows 4189 -> 4499 characters.
About the numbers in SPEC 14 / AGENTS: the 1.48M steps claimed there do not
reproduce on this tree. Measured before the change, 2047/10 was 495,986 and
clb_digits(2047) was 740,695, so the docs now carry the measured values and say
where the old figure came from.
clb_digits keeps its shape (one divmod in a 4 round loop, written digits shift
up by one cell), with S grown to 13 cells: TEN, quotient, remainder, the 7
divmod scratch cells, the loop counter and add_ip's T/F. 2047 goes from
740,695 to 145,138 steps (worst 164,867) and 10829 -> 13717 characters. It
needs its own %include "asm/add_ip.r8asm" now: that used to arrive through the
old divmod.
Tests: test_divmod sweeps 8 divisors x all 2048 dividends (16384 pairs; the old
76 sample table is a subset) and also asserts N and D come back unchanged;
test_digits sweeps all 2048 values. Both print the worst step count.
Two traps found on the way:
* r8forge_derive (and byte_op_test/synth_test) checked the assembler error flag
before export_rot8(), but an unknown macro or a bad .tp target is found while
the tree is *expanded*: a missing %include left a truncated tape that still
ran and printed a plausible wrong answer (all four digits came out '0'). All
three now check after the export.
* raw_sub's comment claimed Bo = 1 means A < B; the code (and clb_sub_nc) mean
A >= B. Comment fixed, behaviour untouched.
Also adds drv/div_shift.r8asm, the single step check for the cross cell shift
plus injection, and records the measurements in SPEC 7.6/7.7/14 and AGENTS.
37 lines
1.3 KiB
Plaintext
37 lines
1.3 KiB
Plaintext
%include "asm/lib.r8asm"
|
|
|
|
; clb_divmod 的第一步单点验证:R = (Rhi:Rlo) 往左移一格,再把刚转到 bit0 的
|
|
; 那一位(N 的 LSB)注进 Rlo 的 bit0。跨格左移是 `clb_mul` 当年返工过两轮的地方。
|
|
;
|
|
; 这一步就是长除法每轮的头三句,顺序不能换:
|
|
; rol N ; N 左旋:下一位(最高位起)落在 N 的 LSB
|
|
; rol Rlo ; Rlo 左旋:最高位绕回 bit0
|
|
; 搬走绕回位 ; 先搬进 Rhi(**先搬,再清**),再补 N 的那一位
|
|
;
|
|
; 期望(N' = rol N 之后的值):
|
|
; Rlo' = ((Rlo << 1) & _CELL_MAX) | (N' & 1) ; N' 的 LSB = 原来 N 的 bit W-1
|
|
; Rhi' = (Rlo >> (_CELL_SIZE - 1)) & 1
|
|
; N' = rol N
|
|
;
|
|
; r8forge_derive drv/div_shift.r8asm -1 0=1024 2=0 4=1 # 0 1 2
|
|
; r8forge_derive drv/div_shift.r8asm -1 0=1023 2=0 4=2047 # 2047 0 2047
|
|
; r8forge_derive drv/div_shift.r8asm -1 0=5 2=0 4=1 # 10 0 2
|
|
;
|
|
; out 依次是 Rlo、Rhi、N。
|
|
.var Rlo 0
|
|
.var Rhi 2
|
|
.var N 4
|
|
.var buf 6
|
|
|
|
.tp N
|
|
rol ; 下一位进 N 的 LSB(转满 W 轮 N 复原,所以 N 不吃)
|
|
.tp Rlo
|
|
rol ; 最高位绕回 bit0
|
|
clb_bit_mov Rhi ; 绕回位搬进 Rhi(先搬走,顺带清掉 Rlo 的 bit0)
|
|
.tp N
|
|
bit_copy Rlo buf ; Rlo 的 bit0 = N 的 LSB(N 保留)
|
|
|
|
output Rlo
|
|
output Rhi
|
|
output N
|