一种在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+运营的思想来代替。