multiplication modulaire de grands nombres en c ++

Compte tenu de votre formule et de la variation suivante:

 (A + B) mod C = ((A mod C) + (B mod C)) mod C 

Vous pouvez utiliser l’approche diviser pour conquérir pour développer un algorithme simple et rapide:

 #include  long bigMod(long a, long b, long c) { if (a == 0 || b == 0) { return 0; } if (a == 1) { return b; } if (b == 1) { return a; } // Returns: (a * b/2) mod c long a2 = bigMod(a, b / 2, c); // Even factor if ((b & 1) == 0) { // [((a * b/2) mod c) + ((a * b/2) mod c)] mod c return (a2 + a2) % c; } else { // Odd exponent // [(a mod c) + ((a * b/2) mod c) + ((a * b/2) mod c)] mod c return ((a % c) + (a2 + a2)) % c; } } int main() { // Use the min(a, b) as the second parameter // This prints: 27 std::cout << bigMod(64545, 58971, 144) << std::endl; return 0; } 

Quel est O(log N)

Vous pouvez résoudre ceci en utilisant la méthode de Schrage . Cela vous permet de multiplier deux nombres signés a et z tous deux avec un certain module m sans générer un nombre intermédiaire supérieur à celui.

Il est basé sur une factorisation approximative du module m ,

 m = aq + r 

c’est à dire

 q = [m / a] 

et

 r = m mod a 

où [] désigne la partie entière. Si r < q et 0 < z < m − 1 , alors a(z mod q) et r[z / q] sont compris dans la plage 0,...,m − 1 et

 az mod m = a(z mod q) − r[z / q] 

Si cela est négatif, alors ajoutez m .

[Cette technique est fréquemment utilisée dans les générateurs de nombres aléatoires congruentiels linéaires].

UPDATED: Correction d’une erreur lorsque le bit haut d’ a % c est défini. (Astuce: Kevin Hopps)

Si vous recherchez simple et rapide , vous pouvez utiliser les éléments suivants:

 typedef unsigned long long u64; u64 multiplyModulo(u64 a, u64 b, u64 c) { u64 result = 0; a %= c; b %= c; while(b) { if(b & 0x1) { result += a; result %= c; } b >>= 1; if(a < c - a) { a <<= 1; } else { a -= (c - a); } } return result; } 

Désolé, mais l’algorithme de godel9 produira un résultat incorrect lorsque la variable “a” contient une valeur dont le bit fort est défini. En effet, “a << = 1" perd des informations. Voici un algorithme corrigé qui fonctionne pour tout type entier, signé ou non.

 template  IntType add(IntType a, IntType b, IntType c) { assert(c > 0 && 0 <= a && a < c && 0 <= b && b < c); IntType room = (c - 1) - a; if (b <= room) a += b; else a = b - room - 1; return a; } template  IntType mod(IntType a, IntType c) { assert(c > 0); IntType q = a / c; // q may be negative a -= q * c; // now -c < a && a < c if (a < 0) a += c; return a; } template  IntType multiplyModulo(IntType a, IntType b, IntType c) { IntType result = 0; a = mod(a, c); b = mod(b, c); if (b > a) std::swap(a, b); while (b) { if (b & 0x1) result = add(result, a, c); a = add(a, a, c); b >>= 1; } return result; } 

Dans ce cas, A et B sont des nombres de 40 bits et C est un nombre de 50 bits, ce qui n’est pas un problème en mode 64 bits si vous avez un code insortingnsèque ou pouvez écrire du code assembleur pour utiliser une multiplication de 64 bits par 64 bits. qui produit un résultat de 128 bits (le produit est en réalité de 80 bits), après quoi vous divisez un dividende de 128 bits par un diviseur de 50 bits pour produire un rest de 50 bits (le modulo).

Selon le processeur, il peut être plus rapide d’appliquer la constante de division par 50 bits en la multipliant par une constante de 81 bits (ou moins). Toujours en supposant un processeur 64 bits, il faudra 4 multiplications et quelques additions suivies d’un décalage des bits supérieurs du produit 4 multiplications pour produire un quotient. Ensuite, une multiplication de quotient fois le nombre modulo 50 bits et la soustraction (du produit 80 bits) est utilisée pour produire un rest 50 bits.