Ein fehlerhafter Algorithmus für die Subtraktion von großen Ganzzahlen in Forth

Question

Ich habe einen mysteriösen Fehler mit einem Algorithmus für die Subtraktion von vorzeichenlosen Ganzzahlen verschiedener Länge. Es funktioniert für fast jedes Zahlenpaar, aber wenn n nicht kleiner als die Anzahl der Bits in einer Zelle ist, dann (2^n +1)-(2^n - 1) <> 2. Ich kann nicht verstehen, warum der Algorithmus nicht funktioniert.

Die Nummern werden in Arrays im "cellimal" -System (Base = 2^Bits) gespeichert, wobei die niedrigstwertigen Zellen in Lowmem sind. Das Array an ad1 ist aus dem Array bei ad2 abgezogen werden, die beide derselben Dimension len, und das Ergebnis sollte bei ad2 gespeichert werden:

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 

Anmerkung: Ich denke, der Fehler kommt, wenn sie von einer Zelle zu leihen das enthält einen Nullwert ...

Vielleicht kann jemand den Algorithmus korrigieren?

Answer 1

Ja, wir sollten das Zeichen beim Ausleihen behalten. Die einfache Lösung ist nur D- überall zu verwenden:

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

oder eine Variation (der Körper der Schleife):

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

Vielleicht ist der richtige Weg, um die Idee von M+ operation stattdessen zu verwenden.