Maison interface Web js tutoriel Comprendre et mettre en œuvre l'algorithme de multiplication Karatsuba pour les grands nombres

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

Dec 14, 2024 am 12:27 AM

Understanding and Implementing the Karatsuba Multiplication Algorithm for Large Numbers

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(n2))(O(n^2)) (O(n2)) , où (n)(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(n1,585))(O(n^{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 :
    • z0=faible1×bas2z_0 = texte{low1} fois texte{low2} z0 =faible1×faible2
    • z1=(faible1 haut1)×(bas2 haut2)z_1 = (text{low1} texte{high1}) fois (text{low2} texte{high2}) z1=(low1 élevé1(faible2 élevé2)
    • z2=haut1×haut2z_2 = texte{high1} fois texte{high2} z2=haut1×haut2
  3. Combiner : Utilisez la formule :
    résultat=z2102m (z1z 2 z0)10m z0texte{result} = z_2 cdot 10^{2 cdot m}(z_1 - z_2 - z_0) cdot 10^m z_0 résultat= z2102⋅m (z1 z2 z0 )⋅10m z0
    (m)(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));
Copier après la connexion
Copier après la connexion
node multiply.js
Copier après la connexion
Copier après la connexion

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(n2))(O(n^2)) (O(n2)) à environ (O(n1,585))(O(n^{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));
Copier après la connexion
Copier après la connexion

Le résultat est :

node multiply.js
Copier après la connexion
Copier après la connexion

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

Video Face Swap

Video Face Swap

Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Que dois-je faire si je rencontre l'impression de code brouillé pour les reçus en papier thermique frontal? Que dois-je faire si je rencontre l'impression de code brouillé pour les reçus en papier thermique frontal? Apr 04, 2025 pm 02:42 PM

Des questions et des solutions fréquemment posées pour l'impression de billets thermiques frontaux pour le développement frontal, l'impression de billets est une exigence commune. Cependant, de nombreux développeurs mettent en œuvre ...

Démystifier javascript: ce qu'il fait et pourquoi c'est important Démystifier javascript: ce qu'il fait et pourquoi c'est important Apr 09, 2025 am 12:07 AM

JavaScript est la pierre angulaire du développement Web moderne, et ses principales fonctions incluent la programmation axée sur les événements, la génération de contenu dynamique et la programmation asynchrone. 1) La programmation axée sur les événements permet aux pages Web de changer dynamiquement en fonction des opérations utilisateur. 2) La génération de contenu dynamique permet d'ajuster le contenu de la page en fonction des conditions. 3) La programmation asynchrone garantit que l'interface utilisateur n'est pas bloquée. JavaScript est largement utilisé dans l'interaction Web, les applications à une page et le développement côté serveur, améliorant considérablement la flexibilité de l'expérience utilisateur et du développement multiplateforme.

Qui est payé plus de python ou de javascript? Qui est payé plus de python ou de javascript? Apr 04, 2025 am 12:09 AM

Il n'y a pas de salaire absolu pour les développeurs Python et JavaScript, selon les compétences et les besoins de l'industrie. 1. Python peut être davantage payé en science des données et en apprentissage automatique. 2. JavaScript a une grande demande dans le développement frontal et complet, et son salaire est également considérable. 3. Les facteurs d'influence comprennent l'expérience, la localisation géographique, la taille de l'entreprise et les compétences spécifiques.

Comment réaliser des effets de défilement de parallaxe et d'animation des éléments, comme le site officiel de Shiseido?
ou:
Comment pouvons-nous réaliser l'effet d'animation accompagné d'un défilement de page comme le site officiel de Shiseido? Comment réaliser des effets de défilement de parallaxe et d'animation des éléments, comme le site officiel de Shiseido? ou: Comment pouvons-nous réaliser l'effet d'animation accompagné d'un défilement de page comme le site officiel de Shiseido? Apr 04, 2025 pm 05:36 PM

La discussion sur la réalisation des effets de défilement de parallaxe et d'animation des éléments dans cet article explorera comment réaliser le site officiel de Shiseido (https://www.shiseido.co.jp/sb/wonderland/) ...

JavaScript est-il difficile à apprendre? JavaScript est-il difficile à apprendre? Apr 03, 2025 am 12:20 AM

Apprendre JavaScript n'est pas difficile, mais c'est difficile. 1) Comprendre les concepts de base tels que les variables, les types de données, les fonctions, etc. 2) Master la programmation asynchrone et les implémenter via des boucles d'événements. 3) Utilisez les opérations DOM et promettez de gérer les demandes asynchrones. 4) Évitez les erreurs courantes et utilisez des techniques de débogage. 5) Optimiser les performances et suivre les meilleures pratiques.

L'évolution de JavaScript: tendances actuelles et perspectives d'avenir L'évolution de JavaScript: tendances actuelles et perspectives d'avenir Apr 10, 2025 am 09:33 AM

Les dernières tendances de JavaScript incluent la montée en puissance de TypeScript, la popularité des frameworks et bibliothèques modernes et l'application de WebAssembly. Les prospects futurs couvrent des systèmes de type plus puissants, le développement du JavaScript côté serveur, l'expansion de l'intelligence artificielle et de l'apprentissage automatique, et le potentiel de l'informatique IoT et Edge.

Comment fusionner les éléments du tableau avec le même ID dans un seul objet en utilisant JavaScript? Comment fusionner les éléments du tableau avec le même ID dans un seul objet en utilisant JavaScript? Apr 04, 2025 pm 05:09 PM

Comment fusionner les éléments du tableau avec le même ID dans un seul objet en JavaScript? Lors du traitement des données, nous rencontrons souvent la nécessité d'avoir le même ID ...

Zustand Asynchronous Operation: Comment assurer le dernier État obtenu par Usestore? Zustand Asynchronous Operation: Comment assurer le dernier État obtenu par Usestore? Apr 04, 2025 pm 02:09 PM

Problèmes de mise à jour des données dans les opérations asynchrones de Zustand. Lorsque vous utilisez la bibliothèque de gestion de l'État de Zustand, vous rencontrez souvent le problème des mises à jour de données qui entraînent des opérations asynchrones prématurées. � ...

See all articles