Comprendre et mettre en œuvre l'algorithme de multiplication Karatsuba pour les grands nombres

En mathématiques computationnelles, la multiplication efficace de grands nombres est la pierre angulaire de diverses applications, de la cryptographie au calcul scientifique. L'algorithme de multiplication Karatsuba est une méthode diviser pour régner qui améliore considérablement les performances par rapport à la multiplication longue traditionnelle pour les grands nombres. Dans cet article, nous explorerons une implémentation JavaScript de ce puissant algorithme conçu pour gérer des nombres arbitrairement grands représentés sous forme de chaînes.

---

Le problème de la multiplication traditionnelle

La méthode de multiplication standard « livre scolaire » a une complexité temporelle de $(O(n^2))$(O(n2)) , où $(n)$(n) est le nombre de chiffres dans les nombres multipliés. Cette croissance quadratique devient coûteuse en calcul à mesure que les nombres augmentent. L'algorithme Karatsuba, introduit par Anatolii Karatsuba en 1960, réduit cette complexité à environ $(O(n^{\mathrm{1,585}}))$(O(n1.585)) , ce qui en fait une option beaucoup plus rapide pour les entrées volumineuses.

---

Comment fonctionne l'algorithme Karatsuba

L'algorithme s'appuie sur la stratégie diviser pour régner :

1. Diviser : Divisez chaque nombre en deux moitiés : une partie haute et une partie basse.
2. Conquérir : Calculer trois produits clés de manière récursive : cela implique de calculer les composants suivants pour chaque étape récursive :
   • $z_0=\text{faible1}\times \text{bas2}$z0​ =faible1×faible2
   • $z_1=(\text{faible1}\text{haut1})\times (\text{bas2}\text{haut2})$z1​=(low1 élevé1)×(faible2 élevé2)
   • $z_2=\text{haut1}\times \text{haut2}$z2​=haut1×haut2
3. Combiner : Utilisez la formule :
   $$\text{résultat}=z_2\cdot 10^{2\cdot m}(z_1-z_2-z_0)\cdot 10^m{z}_0$$résultat= z2​⋅102⋅m (z1​ −z2​ −z0​ )⋅10m z0​
   où $(m)$(m) est la moitié du nombre de chiffres dans les nombres d'origine.

Cette approche réduit le nombre de multiplications récursives de quatre à trois, améliorant ainsi l'efficacité.

---

Implémentation JavaScript

Vous trouverez ci-dessous une implémentation robuste de l'algorithme Karatsuba en JavaScript. Cette version prend en charge les entiers arbitrairement grands en les représentant sous forme de chaînes.

multiply.js

/**
 * Karatsuba multiplication algorithm for large numbers.
 * @param {string} num1 - First large number as a string.
 * @param {string} num2 - Second large number as a string.
 * @returns {string} - Product of the two numbers as a string.
 */
function karatsubaMultiply(num1, num2) {
  // Remove leading zeros
  num1 = num1.replace(/^0+/, "") || "0";
  num2 = num2.replace(/^0+/, "") || "0";

  // If either number is zero, return "0"
  if (num1 === "0" || num2 === "0") return "0";

  // Base case for small numbers (12), use Number for safe multiplication
  if (num1.length <= 12 && num2.length <= 12) {
    return (Number(num1) * Number(num2)).toString();
  }

  // Ensure even length by padding
  const maxLen = Math.max(num1.length, num2.length);
  const paddedLen = Math.ceil(maxLen / 2) * 2;
  num1 = num1.padStart(paddedLen, "0");
  num2 = num2.padStart(paddedLen, "0");

  const mid = paddedLen / 2;

  // Split the numbers into two halves
  const high1 = num1.slice(0, -mid);
  const low1 = num1.slice(-mid);
  const high2 = num2.slice(0, -mid);
  const low2 = num2.slice(-mid);

  // Helper function for adding large numbers as strings
  function addLargeNumbers(a, b) {
    const maxLength = Math.max(a.length, b.length);
    a = a.padStart(maxLength, "0");
    b = b.padStart(maxLength, "0");

    let result = "";
    let carry = 0;

    for (let i = maxLength - 1; i >= 0; i--) {
      const sum = parseInt(a[i]) + parseInt(b[i]) + carry;
      result = (sum % 10) + result;
      carry = Math.floor(sum / 10);
    }

    if (carry > 0) {
      result = carry + result;
    }

    return result.replace(/^0+/, "") || "0";
  }

  // Helper function to multiply by 10^n
  function multiplyByPowerOf10(num, power) {
    return num === "0" ? "0" : num + "0".repeat(power);
  }

  // Helper function for subtracting large numbers
  function subtractLargeNumbers(a, b) {
    const maxLength = Math.max(a.length, b.length);
    a = a.padStart(maxLength, "0");
    b = b.padStart(maxLength, "0");

    let result = "";
    let borrow = 0;

    for (let i = maxLength - 1; i >= 0; i--) {
      let diff = parseInt(a[i]) - parseInt(b[i]) - borrow;
      if (diff < 0) {
        diff += 10;
        borrow = 1;
      } else {
        borrow = 0;
      }
      result = diff + result;
    }

    return result.replace(/^0+/, "") || "0";
  }

  // Recursive steps
  const z0 = karatsubaMultiply(low1, low2);
  const z1 = karatsubaMultiply(
    addLargeNumbers(low1, high1),
    addLargeNumbers(low2, high2)
  );
  const z2 = karatsubaMultiply(high1, high2);

  // Compute the result using Karatsuba formula
  const z1MinusZ2MinusZ0 = subtractLargeNumbers(
    subtractLargeNumbers(z1, z2),
    z0
  );

  const powerMidTerm = multiplyByPowerOf10(z1MinusZ2MinusZ0, mid);
  const z2Term = multiplyByPowerOf10(z2, 2 * mid);

  // Add all terms
  const term1 = addLargeNumbers(z2Term, powerMidTerm);
  const result = addLargeNumbers(term1, z0);

  return result;
}

// Example Usage
const num1 = "1234567890123456789023454353453454354345435345435435";
const num2 = "98765432109876543210";
console.log("Product:", karatsubaMultiply(num1, num2));

node multiply.js

---

Principales caractéristiques de la mise en œuvre

1. Optimisation du cas de base :

   • Pour les nombres jusqu'à 12 chiffres, l'algorithme utilise directement le nombre JavaScript pour une multiplication efficace.

2. Manipulation de chaînes pour une précision arbitraire :

   • L'algorithme utilise des opérations sur les chaînes pour gérer de grands nombres sans perdre en précision.

3. Fonctions d'assistance :

   • Addition (addLargeNumbers) : Gère l'ajout de deux grands nombres représentés sous forme de chaînes.
   • Soustraction (subtractLargeNumbers) : Gère la soustraction avec emprunt pour les grands nombres.
   • Multiplication de puissance de 10 (multiplyByPowerOf10) : Décale efficacement les nombres en ajoutant des zéros.

4. Conception récursive :

   • L'algorithme divise chaque entrée de manière récursive, combinant les résultats à l'aide de la formule Karatsuba.

---

Considérations relatives aux performances

L'algorithme Karatsuba réduit le nombre de multiplications récursives de $(O(n^2))$(O(n2)) à environ $(O(n^{\mathrm{1,585}}))$(O(n1.585)) . Cela le rend nettement plus rapide que les méthodes traditionnelles pour les gros intrants. Cependant, la surcharge liée aux manipulations de chaînes peut affecter les performances pour les entrées plus petites, c'est pourquoi l'optimisation du cas de base est cruciale.

---

Exemple de sortie

Pour :

/**
 * Karatsuba multiplication algorithm for large numbers.
 * @param {string} num1 - First large number as a string.
 * @param {string} num2 - Second large number as a string.
 * @returns {string} - Product of the two numbers as a string.
 */
function karatsubaMultiply(num1, num2) {
  // Remove leading zeros
  num1 = num1.replace(/^0+/, "") || "0";
  num2 = num2.replace(/^0+/, "") || "0";

  // If either number is zero, return "0"
  if (num1 === "0" || num2 === "0") return "0";

  // Base case for small numbers (12), use Number for safe multiplication
  if (num1.length <= 12 && num2.length <= 12) {
    return (Number(num1) * Number(num2)).toString();
  }

  // Ensure even length by padding
  const maxLen = Math.max(num1.length, num2.length);
  const paddedLen = Math.ceil(maxLen / 2) * 2;
  num1 = num1.padStart(paddedLen, "0");
  num2 = num2.padStart(paddedLen, "0");

  const mid = paddedLen / 2;

  // Split the numbers into two halves
  const high1 = num1.slice(0, -mid);
  const low1 = num1.slice(-mid);
  const high2 = num2.slice(0, -mid);
  const low2 = num2.slice(-mid);

  // Helper function for adding large numbers as strings
  function addLargeNumbers(a, b) {
    const maxLength = Math.max(a.length, b.length);
    a = a.padStart(maxLength, "0");
    b = b.padStart(maxLength, "0");

    let result = "";
    let carry = 0;

    for (let i = maxLength - 1; i >= 0; i--) {
      const sum = parseInt(a[i]) + parseInt(b[i]) + carry;
      result = (sum % 10) + result;
      carry = Math.floor(sum / 10);
    }

    if (carry > 0) {
      result = carry + result;
    }

    return result.replace(/^0+/, "") || "0";
  }

  // Helper function to multiply by 10^n
  function multiplyByPowerOf10(num, power) {
    return num === "0" ? "0" : num + "0".repeat(power);
  }

  // Helper function for subtracting large numbers
  function subtractLargeNumbers(a, b) {
    const maxLength = Math.max(a.length, b.length);
    a = a.padStart(maxLength, "0");
    b = b.padStart(maxLength, "0");

    let result = "";
    let borrow = 0;

    for (let i = maxLength - 1; i >= 0; i--) {
      let diff = parseInt(a[i]) - parseInt(b[i]) - borrow;
      if (diff < 0) {
        diff += 10;
        borrow = 1;
      } else {
        borrow = 0;
      }
      result = diff + result;
    }

    return result.replace(/^0+/, "") || "0";
  }

  // Recursive steps
  const z0 = karatsubaMultiply(low1, low2);
  const z1 = karatsubaMultiply(
    addLargeNumbers(low1, high1),
    addLargeNumbers(low2, high2)
  );
  const z2 = karatsubaMultiply(high1, high2);

  // Compute the result using Karatsuba formula
  const z1MinusZ2MinusZ0 = subtractLargeNumbers(
    subtractLargeNumbers(z1, z2),
    z0
  );

  const powerMidTerm = multiplyByPowerOf10(z1MinusZ2MinusZ0, mid);
  const z2Term = multiplyByPowerOf10(z2, 2 * mid);

  // Add all terms
  const term1 = addLargeNumbers(z2Term, powerMidTerm);
  const result = addLargeNumbers(term1, z0);

  return result;
}

// Example Usage
const num1 = "1234567890123456789023454353453454354345435345435435";
const num2 = "98765432109876543210";
console.log("Product:", karatsubaMultiply(num1, num2));

Le résultat est :

node multiply.js

---

Conclusion

L'algorithme de multiplication Karatsuba est une solution pratique et efficace pour multiplier de grands nombres. Cette implémentation démontre sa puissance et sa flexibilité lors de la gestion d'entrées arbitrairement volumineuses en JavaScript. Avec le besoin croissant d'arithmétique de haute précision, la maîtrise de tels algorithmes peut considérablement améliorer les capacités de calcul dans diverses applications.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!