


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(n2)) , où (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)) , 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 :
- Diviser : Divisez chaque nombre en deux moitiés : une partie haute et une partie basse.
-
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×faible2
- z1=(low1 élevé1)×(faible2 élevé2)
- z2=haut1×haut2
-
Combiner : Utilisez la formule :
résultat= z2⋅102⋅m (z1 −z2 −z0 )⋅10m z0où (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
-
Optimisation du cas de base :
- Pour les nombres jusqu'à 12 chiffres, l'algorithme utilise directement le nombre JavaScript pour une multiplication efficace.
-
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.
-
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.
-
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)) à environ (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!

Outils d'IA chauds

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

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

Undress AI Tool
Images de déshabillage gratuites

Clothoff.io
Dissolvant de vêtements AI

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

Outils chauds

Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise
Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP

Dreamweaver CS6
Outils de développement Web visuel

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

Sujets chauds











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.

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.

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.

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 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 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.

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.

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.
