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

Question

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

数字存储在 "cellimal" 系统中的数组中（基数 = 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+ operation的思路来代替。

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

A faulty algorithm for subtraction of big integers in Forth

arrays

algorithm

biginteger

forth

gforth