


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

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

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.

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.

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

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.

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 JavaScript? Lors du traitement des données, nous rencontrons souvent la nécessité d'avoir le même ID ...

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