Cours sur l’algorithme de Karatsuba
Sommaire :
- Introduction à la multiplication
- L'algorithme de Karatsuba : une solution plus rapide
- Décomposition des nombres dans Karatsuba
- Étapes détaillées de l'algorithme de Karatsuba
- Comment divise-t-on les nombres dans Karatsuba ?
- Complexité de l'algorithme de Karatsuba
- Implémentation en langage C
- Implémentation en Java
- Implémentation en JavaScript
- Conclusion
1. Introduction à la multiplication
La multiplication est une opération fondamentale en mathématiques. Le processus traditionnel pour multiplier deux grands nombres consiste à utiliser la méthode classique (dite "de l'école"). Cette méthode fonctionne bien pour les petits nombres mais devient inefficace pour des nombres de plusieurs dizaines de chiffres. La méthode classique a une complexité en \( O(n^2) \), ce qui signifie que le temps nécessaire pour effectuer la multiplication augmente rapidement avec la taille des nombres.
2. L'algorithme de Karatsuba : une solution plus rapide
L'algorithme de Karatsuba, inventé en 1960, permet de multiplier des grands nombres plus efficacement que la méthode traditionnelle. Il utilise une approche "diviser pour régner", qui permet de réduire le nombre de multiplications nécessaires en utilisant des opérations plus simples sur des sous-parties des nombres.
Complexité : L'algorithme de Karatsuba a une complexité en \( O(n^{1.585}) \), ce qui est bien meilleur que la méthode classique pour de très grands nombres.
3. Décomposition des nombres dans Karatsuba
Karatsuba repose sur l'idée de découper les nombres en deux parties, que l'on multiplie séparément. Supposons que nous avons deux nombres \( x \) et \( y \), de \( n \) chiffres chacun.
- On "coupe" chaque nombre en deux : \[ x = x_1 \times 10^m + x_0 \] \[ y = y_1 \times 10^m + y_0 \]
- On calcule les trois produits intermédiaires suivants : \[ P_1 = x_1 \times y_1 \] \[ P_2 = x_0 \times y_0 \] \[ P_3 = (x_1 + x_0) \times (y_1 + y_0) \]
- Ensuite, le produit total est donné par : \[ Produit\ final = P_1 \times 10^{2m} + (P_3 - P_1 - P_2) \times 10^m + P_2 \]
4. Étapes détaillées de l'algorithme de Karatsuba
Étape 1 : Base de la récursion
Si les nombres sont petits (par exemple à un seul chiffre), on utilise la multiplication normale.
Étape 2 : Diviser les nombres
On coupe les nombres en deux. Cela se fait en divisant le nombre en fonction de sa longueur \( n \), en choisissant \( m = n / 2 \).
Étape 3 : Calcul des produits intermédiaires
Nous devons calculer :
- \( P_1 = x_1 \times y_1 \)
- \( P_2 = x_0 \times y_0 \)
- \( P_3 = (x_1 + x_0) \times (y_1 + y_0) \)
Étape 4 : Combiner les résultats
Le produit final est obtenu en combinant les trois résultats de la manière suivante :
\[ Produit\ final = P_1 \times 10^{2m} + (P_3 - P_1 - P_2) \times 10^m + P_2 \]
Pour diviser les nombres, nous devons couper \( x \) et \( y \) en deux. Ces divisions se font en fonction de la longueur des nombres.
- Condition : Pour que la division fonctionne correctement, les deux nombres doivent avoir une longueur \( n \), et \( m = n / 2 \), où \( m \) est la moitié de cette longueur. Si la longueur de \( n \) est impaire, on prend la moitié arrondie.
- Que signifie \( 10^{2m} \) et \( 10^m \) ? :
- \( 10^{2m} \) correspond à un décalage de deux blocs de chiffres, ou deux "puissances de dix". Cela permet de "déplacer" le résultat du produit \( P_1 \) vers la gauche.
- \( 10^m \) est utilisé pour "déplacer" le résultat du terme intermédiaire \( (P_3 - P_1 - P_2) \) vers la gauche d'un bloc.
- Comment trouve-t-on \( m \) ? :
- \( m \) est trouvé en divisant la longueur \( n \) du plus grand des deux nombres par 2. Par exemple, si \( x \) a 4 chiffres, alors \( m = 4/2 = 2 \).
6. Complexité de l'algorithme de Karatsuba
Complexité temporelle :
La méthode classique de multiplication a une complexité de \( O(n^2) \) car elle effectue \( n \) multiplications. L'algorithme de Karatsuba, quant à lui, réduit cette complexité à \( O(n^{1.585}) \).
7. Implémentation en langage C
#include
#include
// Fonction pour calculer la longueur d'un nombre
int getLength(int num) {
return (int)log10(num) + 1;
}
// Algorithme de Karatsuba
int karatsuba(int x, int y) {
if (x < 10 || y < 10) {
return x * y;
}
int n = fmax(getLength(x), getLength(y));
int m = n / 2;
int high1 = x / (int)pow(10, m);
int low1 = x % (int)pow(10, m);
int high2 = y / (int)pow(10, m);
int low2 = y % (int)pow(10, m);
int P1 = karatsuba(high1, high2);
int P2 = karatsuba(low1, low2);
int P3 = karatsuba(high1 + low1, high2 + low2);
return P1 * (int)pow(10, 2 * m) + (P3 - P1 - P2) * (int)pow(10, m) + P2;
}
int main() {
int x = 1234;
int y = 5678;
printf("Multiplication de %d et %d = %d\n", x, y, karatsuba(x, y));
return 0;
}
8. Implémentation en Java
public class Karatsuba {
// Fonction pour calculer la longueur d'un nombre
public static int getLength(int num) {
return String.valueOf(num).length();
}
// Algorithme de Karatsuba
public static int karatsuba(int x, int y) {
if (x < 10 || y < 10) {
return x * y;
}
int n = Math.max(getLength(x), getLength(y));
int m = n / 2;
int high1 = x / (int)Math.pow(10, m);
int low1 = x % (int)Math.pow(10, m);
int high2 = y / (int)Math.pow(10, m);
int low2 = y % (int)Math.pow(10, m);
int P1 = karatsuba(high1, high2);
int P2 = karatsuba(low1, low2);
int P3 = karatsuba(high1 + low1, high2 + low2);
return P1 * (int)Math.pow(10, 2 * m) + (P3 - P1 - P2) * (int)Math.pow(10, m) + P2;
}
public static void main(String[] args) {
int x = 1234;
int y = 5678;
System.out.println("Multiplication de " + x + " et " + y + " = " + karatsuba(x, y));
}
}
9. Implémentation en JavaScript
function karatsuba(x, y) {
if (x < 10 || y < 10) {
return x * y;
}
const n = Math.max(x.toString().length, y.toString().length);
const m = Math.floor(n / 2);
const high1 = Math.floor(x / Math.pow(10, m));
const low1 = x % Math.pow(10, m);
const high2 = Math.floor(y / Math.pow(10, m));
const low2 = y % Math.pow(10, m);
const P1 = karatsuba(high1, high2);
const P2 = karatsuba(low1, low2);
const P3 = karatsuba(high1 + low1, high2 + low2);
return P1 * Math.pow(10, 2 * m) + (P3 - P1 - P2) * Math.pow(10, m) + P2;
}
const x = 1234;
const y = 5678;
console.log(`Multiplication de ${x} et ${y} = ${karatsuba(x, y)}`);
10. Conclusion
L'algorithme de Karatsuba est une solution efficace pour multiplier de grands nombres. Grâce à son approche basée sur "diviser pour régner", il permet de réduire le nombre d'opérations nécessaires, rendant la multiplication plus rapide pour des nombres de grande taille. Ses implémentations en C, Java, et JavaScript démontrent qu'il peut être utilisé dans divers environnements et langages de programmation.