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 !

Article chaud

<🎜>: Grow A Garden - Guide de mutation complet
3 Il y a quelques semaines By DDD
<🎜>: Bubble Gum Simulator Infinity - Comment obtenir et utiliser les clés royales
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Nordhold: Système de fusion, expliqué
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Mandragora: Whispers of the Witch Tree - Comment déverrouiller le grappin
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌

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)

Sujets chauds

Tutoriel Java
1670
14
Tutoriel PHP
1276
29
Tutoriel C#
1256
24
Python vs JavaScript: la courbe d'apprentissage et la facilité d'utilisation Python vs JavaScript: la courbe d'apprentissage et la facilité d'utilisation Apr 16, 2025 am 12:12 AM

Python convient plus aux débutants, avec une courbe d'apprentissage en douceur et une syntaxe concise; JavaScript convient au développement frontal, avec une courbe d'apprentissage abrupte et une syntaxe flexible. 1. La syntaxe Python est intuitive et adaptée à la science des données et au développement back-end. 2. JavaScript est flexible et largement utilisé dans la programmation frontale et côté serveur.

De C / C à JavaScript: comment tout cela fonctionne De C / C à JavaScript: comment tout cela fonctionne Apr 14, 2025 am 12:05 AM

Le passage de C / C à JavaScript nécessite de s'adapter à la frappe dynamique, à la collecte des ordures et à la programmation asynchrone. 1) C / C est un langage dactylographié statiquement qui nécessite une gestion manuelle de la mémoire, tandis que JavaScript est dynamiquement typé et que la collecte des déchets est automatiquement traitée. 2) C / C doit être compilé en code machine, tandis que JavaScript est une langue interprétée. 3) JavaScript introduit des concepts tels que les fermetures, les chaînes de prototypes et la promesse, ce qui améliore la flexibilité et les capacités de programmation asynchrones.

Javascript et le web: fonctionnalité de base et cas d'utilisation Javascript et le web: fonctionnalité de base et cas d'utilisation Apr 18, 2025 am 12:19 AM

Les principales utilisations de JavaScript dans le développement Web incluent l'interaction client, la vérification du formulaire et la communication asynchrone. 1) Mise à jour du contenu dynamique et interaction utilisateur via les opérations DOM; 2) La vérification du client est effectuée avant que l'utilisateur ne soumette les données pour améliorer l'expérience utilisateur; 3) La communication de rafraîchissement avec le serveur est réalisée via la technologie AJAX.

JavaScript en action: Exemples et projets du monde réel JavaScript en action: Exemples et projets du monde réel Apr 19, 2025 am 12:13 AM

L'application de JavaScript dans le monde réel comprend un développement frontal et back-end. 1) Afficher les applications frontales en créant une application de liste TODO, impliquant les opérations DOM et le traitement des événements. 2) Construisez RestulAPI via Node.js et Express pour démontrer les applications back-end.

Comprendre le moteur JavaScript: détails de l'implémentation Comprendre le moteur JavaScript: détails de l'implémentation Apr 17, 2025 am 12:05 AM

Comprendre le fonctionnement du moteur JavaScript en interne est important pour les développeurs car il aide à écrire du code plus efficace et à comprendre les goulots d'étranglement des performances et les stratégies d'optimisation. 1) Le flux de travail du moteur comprend trois étapes: analyse, compilation et exécution; 2) Pendant le processus d'exécution, le moteur effectuera une optimisation dynamique, comme le cache en ligne et les classes cachées; 3) Les meilleures pratiques comprennent l'évitement des variables globales, l'optimisation des boucles, l'utilisation de const et de locations et d'éviter une utilisation excessive des fermetures.

Python vs JavaScript: communauté, bibliothèques et ressources Python vs JavaScript: communauté, bibliothèques et ressources Apr 15, 2025 am 12:16 AM

Python et JavaScript ont leurs propres avantages et inconvénients en termes de communauté, de bibliothèques et de ressources. 1) La communauté Python est amicale et adaptée aux débutants, mais les ressources de développement frontal ne sont pas aussi riches que JavaScript. 2) Python est puissant dans les bibliothèques de science des données et d'apprentissage automatique, tandis que JavaScript est meilleur dans les bibliothèques et les cadres de développement frontaux. 3) Les deux ont des ressources d'apprentissage riches, mais Python convient pour commencer par des documents officiels, tandis que JavaScript est meilleur avec MDNWEBDOCS. Le choix doit être basé sur les besoins du projet et les intérêts personnels.

Python vs JavaScript: environnements et outils de développement Python vs JavaScript: environnements et outils de développement Apr 26, 2025 am 12:09 AM

Les choix de Python et JavaScript dans les environnements de développement sont importants. 1) L'environnement de développement de Python comprend Pycharm, Jupyternotebook et Anaconda, qui conviennent à la science des données et au prototypage rapide. 2) L'environnement de développement de JavaScript comprend Node.js, VScode et WebPack, qui conviennent au développement frontal et back-end. Le choix des bons outils en fonction des besoins du projet peut améliorer l'efficacité du développement et le taux de réussite du projet.

Le rôle de C / C dans les interprètes et compilateurs JavaScript Le rôle de C / C dans les interprètes et compilateurs JavaScript Apr 20, 2025 am 12:01 AM

C et C jouent un rôle essentiel dans le moteur JavaScript, principalement utilisé pour implémenter des interprètes et des compilateurs JIT. 1) C est utilisé pour analyser le code source JavaScript et générer une arborescence de syntaxe abstraite. 2) C est responsable de la génération et de l'exécution de bytecode. 3) C met en œuvre le compilateur JIT, optimise et compile le code de point chaud à l'exécution et améliore considérablement l'efficacité d'exécution de JavaScript.

See all articles