Un algoritmo errato per la sottrazione di interi grandi in Forth

Question

Ho un errore misterioso con un algoritmo per la sottrazione di interi senza segno di varie lunghezze. Funziona per quasi ogni coppia di numeri, ma se n non è inferiore al numero di bit in una cella, quindi (2^n +1)-(2^n - 1) <> 2. Non riesco a capire perché l'algoritmo non funzioni.

I numeri sono memorizzati in array nel sistema "cellimal" (base = 2^bit), con le celle meno significative in lowmem. La matrice a AD1 deve essere sottratta dalla matrice a AD2, sia dello stesso len dimensione, e il risultato deve essere conservato a 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 

Nota: Credo l'errore viene da quando prestito da una cella che contiene un valore zero ...

Forse qualcuno può correggere l'algoritmo?

Answer 1

Sì, dovremmo tenere il segno di trasporto anche quando prendiamo in prestito. La soluzione semplice è solo quello di usare D- ovunque:

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

o qualche variazione (il corpo del ciclo):

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

Forse, il modo giusto è quello di utilizzare l'idea di M+ operation invece.