Est-ce que quelqu'un connaît un meilleur moyen de modulo sur bits?

Question

J'ai 2 grands nombres, l'un sur 4096 bits et les autres 2048 bits, stockés dans une structure:

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

Je dois faire le modulo de ceux-ci et seule façon que je peux penser à le faire est Soustraire multiple fois, mais cela prend du temps.

Est-ce que quelqu'un sait une meilleure façon de le faire?

Answer 1

Le code basé sur @caf avec ma correction. Laissez OP pour coder les 4 fonctions auxiliaires.

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

Pour calculer m% n:

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 3

Vous pouvez diviser a par b et obtenir un x nombre entier. Maintenant, soustrayez x de a et vous obtenez le module. Avec des diviseurs arbitraires, vous ne pourrez pas contourner la division. Pour les grands diviseurs, cela peut être plus rapide que les soustractions multiples, mais les divisions restent coûteuses.

Vous devrez peut-être également implémenter manuellement l'algorithme de divison pour ces grands nombres. Il y en a un là-bas, qui aboutit à qoutient et reste (module) en même temps, mais je ne peux pas me souvenir de son nom maintenant.