arrays - Forth中大整数减法的错误算法

Question

我的算法有一个神秘的错误，用于减去各种长度的无符号整数。它几乎适用于每一对数字，但如果 n 不小于单元格中的位数，则(2^n +1)-(2^n - 1) <> 2. 我不明白为什么算法不起作用。

这些数字存储在“cellimal”系统中的数组中（base = 2^bits），lowmem 中的最低有效单元格。ad1 处的数组要从 ad2 处的数组中减去，两者的 len 维数相同，结果应存储在 ad2 中：

false borrow ! len 0
do i ad2 + @ borrow @ +
   i ad1 + @ 2dup u< dup borrow !
   if 1 swap 0 d- drop                      \ subtraction with borrow
   else -                                   \ subtraction without borrow
   then i ad2 + ! cell
+loop

注意：我认为错误来自从包含零值的单元格中借用...

也许有人可以纠正算法？

Answer 1

是的，我们在借的时候也应该保留进位标志。直接的解决方案就是在D-任何地方使用：

0 borrow !
len 0 DO
  ad2 I +     @ 0
  borrow      @ 0 D-
  ad1 I +     @ 0 D-
  ABS borrow  !
  ad2 I +     !
cell +LOOP

或一些变化（循环体）：

  borrow  @ S>D
  ad2 I + @ 0     D+
  ad1 I + @ 0     D-
  borrow  !
  ad2 I + !

或许，正确的做法是改用M+操作的思想。