Kennt jemand einen besseren Weg für Modulo auf Bits?

Question

Ich habe 2 große Zahlen, ein etwa 4096 Bits und die anderen 2048 Bits, in einer Struktur gespeichert:

typedef uint32_t word; 
typedef struct BigNumber { 
    word words[128]; 
} BigNumber; 

Ich habe die Modulo die, und nur so machen ich es tun denken kann, ist subtrahiert mehrere Mal, aber das braucht etwas Zeit.

Kennt jemand einen besseren Weg, dies zu tun?

modulus(m, n) { 
    if (m < n) return m 
    elif (m < (n<<1)) return m - n 
    else return modulus((modulus(m>>1, n)<<1 + m&1), n) 
} 

Answer 1

Code basierend auf @caf mit meiner Korrektur. Belassen Sie OP, um die 4 Hilfsfunktionen zu codieren.

void BigNumber_Shift_Right(BigNumber *x); 
void BigNumber_Shift_Left(BigNumber *x); 
int BigNumber_Compare(const BigNumber *a, const BigNumber *b); 
void BigNumber_SubtractEqual(BigNumber *a, const BigNumber *b); 

void BigNumber_ModHalfSizeEqual(BigNumber *A, const BigNumber *B) { 
    BigNumber X = *B; 
    BigNumber AHalf = *A; 
    BigNumber_Shift_Right(&AHalf); 

    while (BigNumber_Compare(&X, &AHalf) <= 0) { 
    BigNumber_Shift_Left(&X); 
    } 

    while (BigNumber_Compare(A, B) >= 0) { 
    if (BigNumber_Compare(A, &X) >= 0) { 
     BigNumber_SubtractEqual(A, &X); 
    } 
    BigNumber_Shift_Right(&X); 
    } 

    // mod is in A 
} 

Answer 2

zu m% n zu berechnen. Subtrahiere nun x von a und du bekommst den Modulus. Mit beliebigen Teilern kommst du nicht um die Division herum. Für große Teiler ist dies möglicherweise schneller als mehrere Subtraktionen, aber Divisionen sind immer noch teuer.

Möglicherweise müssen Sie den Divison-Algorithmus auch manuell für solche großen Zahlen implementieren. Es gibt eine da draußen, die gleichzeitig Qoutient und Rest (Modul) ergibt, aber ich kann mich jetzt nicht an seinen Namen erinnern.

Answer 3

Sie teilen eine von b und eine ganze Zahl x: