mehrdeutige vorzeichenlose Subtraktion in C

Question

Ich versuche, multi-precision unsigned Subtraktion über ein endliches Feld (p = 2^191-19) in C zu implementieren, aber ich kann nicht herausfinden, wie mit Borrow-Bit umzugehen! My Operanden werden in radix-2^16 dargestellt als:

typedef unsigned long long T[12]; 

der jedes Element des T-Typ-Array-Einrichtung hat genau 16-Bit-Daten (Radix-2^16-Darstellung). Nun möchte ich zwei Operanden des T-Typs subtrahieren, aber ich weiß nicht, welcher kleiner ist! Wenn das Ergebnis negativ ist, möchte ich das Ergebnis zum Primzahlwert addieren, um positive Ergebnisse in der modularen Arithmetik zu erhalten. Hier ist meine Implementierung auf this Buch Seite-30 (Mehrfachgenaue Subtraktion Algorithmus) basiert:

void bigint192_sub(T r, const T a, const T b){ 
    int i; 
    int borrow; 
    r[0] = a[0] - b[0]; 
    borrow = r[0] >> 16; 
    r[0] &= 0xFFFF; 
    for(i=1;i<12;++i){ 
     r[i] = a[i] - b[i] - borrow; 
     borrow = r[i] >> 16; 
     r[i] &= 0xFFFF; 
    } 
} 

aber ich habe die falsche Antwort!

My inputs: 
a =0x2d7e33e5bba0f6bb87ce04b28e940662db8f3f81aaf94576 
b =0x28afc585dca4a8003b081f7289de11c2d229d5a967081f72 
Myresult=0x4d16e62defd4ebc4cc8e54104b7f4a0096769d843f12604 
Crresult=0x4ce6e5fdefc4ebb4cc5e54004b5f4a0096569d843f12604 

Answer 1

Sie sollten borrow Auswertung beheben, da es 0 oder 1 nur sein kann. So sollten Sie Unterlauf behandeln, als borrow gleich zu 1:

borrow = (r[i] >> 16) != 0; 

Auch ich Funktion in etwas allgemeinerer Form umschreiben würde, da wir zum ersten Mal den Ball behandeln können als wie wir keine borrow haben:

void bigint192_sub(T r, const T a, const T b){ 
    int i; 
    int borrow; 
    for (borrow = 0, i = 0; i < 12; ++i) { 
     r[i] = a[i] - b[i] - borrow; 
     borrow = (r[i] >> 16) != 0; 
     r[i] &= 0xFFFF; 
    } 
}