一种在Forth中减去大整数的错误算法

I have a mysterious error with an algorithm for subtraction of unsigned integers of various lengths. It works for almost every pair of numbers, but if n isn't smaller than the number of bits in a cell then (2^n +1)-(2^n - 1) <> 2. I can't understand why the algorithm doesn't work.

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

The numbers are stored in arrays in the "cellimal" system (base = 2^bits), with the least significant cells in lowmem. The array at ad1 is to be subtracted from the array at ad2, both of the same dimension len, and the result should be stored at ad2:

这些数字存储在“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

Note: I think the error comes from when borrowing from a cell that contains a zero value...

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

Perhaps someone can correct the algorithm?

也许有人可以纠正算法?

1 个解决方案

#1

Yes, we should keep carry sign when borrowing also. The straightforward solution is just to use D- everywhere:

是的,我们也应该在借款时随身携带标志。直接的解决方案就是在任何地方使用D-:

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

Or some variation (the body of loop):

或者一些变化(循环体):

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

Perhaps, the right way is to use the idea of M+ operation instead.

也许,正确的方法是使用M +操作的想法。

#1