Jūs esateŽurnalai / Ernestas Kardzys's blog / Multiple Precision Modular Arithmetics. Addition (Fixed)
Multiple Precision Modular Arithmetics. Addition (Fixed)
My fix is connected with fact that is not always necessary to perform a modulo operation.
For example: we have number a = 3, b = 4, modulus = 10. So, the operation would look something like that: (a + b) mod modulus = (3 + 4) mod 10 = 7 mod 10. Because 7 is lower than 10, we do not need the modulus operation.
The structure:
typedef size_t digit_t;
typedef struct {
int neg; /* if TRUE, then negative number */
int sig_digits; /* amount of significant (non-zero) digits */
int all_digits; /* amount of overall digits in array */
digit_t *digits; /* pointer to first limb */
} bignum_t;
The code would look something like that:
/* (x + y) mod base */
void mpa_mod_add(bignum_t *res, const bignum_t *a, const bignum_t *b, const bignum_t *base) {
int i = 0, c = 0;
for (i = 0; i < a->all_digits; i++) {
res->digits[i] = a->digits[i] + b->digits[i];
if (res->digits[i] >= base->digits[i])
res->digits[i] = res->digits[i] - base->digits[i];
}
res->digits[res->all_digits] = c;
}


Skelbti naują komentarą