Den Karatsuba-Multiplikationsalgorithmus für große Zahlen verstehen und implementieren

In der Computermathematik ist die effiziente Multiplikation großer Zahlen ein Eckpfeiler verschiedener Anwendungen, von der Kryptographie bis zum wissenschaftlichen Rechnen. Der Karatsuba-Multiplikationsalgorithmus ist eine Divide-and-Conquer-Methode, die die Leistung gegenüber der herkömmlichen langen Multiplikation für große Zahlen erheblich verbessert. In diesem Artikel untersuchen wir eine JavaScript-Implementierung dieses leistungsstarken Algorithmus, der für die Verarbeitung beliebig großer Zahlen entwickelt wurde, die als Zeichenfolgen dargestellt werden.

---

Das Problem mit der traditionellen Multiplikation

Die Standard-Multiplikationsmethode „Schulbuch“ hat eine Zeitkomplexität von $(O(n^2))$(O(n2)) , Wo $(n)$(n) ist die Anzahl der Ziffern in den Zahlen, die multipliziert werden. Dieses quadratische Wachstum wird rechenintensiv, je größer die Zahlen werden. Der 1960 von Anatolii Karatsuba eingeführte Karatsuba-Algorithmus reduziert diese Komplexität auf ungefähr $(O(n^{1.585}))$(O(n1,585)) , was es zu einer viel schnelleren Option für große Eingaben macht.

---

Wie der Karatsuba-Algorithmus funktioniert

Der Algorithmus basiert auf der Divide-and-Conquer-Strategie:

1. Teilen: Teilen Sie jede Zahl in zwei Hälften – einen oberen und einen unteren Teil.
2. Erobern: Berechnen Sie drei Schlüsselprodukte rekursiv: Dies beinhaltet die Berechnung der folgenden Komponenten für jeden rekursiven Schritt:
   • $z_0=\text{low1}\times \text{low2}$z0​ =niedrig1×niedrig2
   • $z_1=(\text{niedrig1}\text{hoch1})\times (\text{tief2}\text{hoch2})$z1​=(low1 hoch1)×(tief2 hoch2)
   • $z_2=\text{high1}\times \text{high2}$z2​=hoch1×hoch2
3. Kombinieren: Verwenden Sie die Formel:
   $$\text{Ergebnis}=z_2\cdot 10^{2\cdot m}(z_1-z_2-z_0)\cdot 10^m{z}_0$$Ergebnis= z2​⋅102⋅m (z1​ −z2​ −z0​ )⋅10m z0>
   Wo $(m)$(m) ist die Hälfte der Ziffern der ursprünglichen Zahlen.

Dieser Ansatz reduziert die Anzahl der rekursiven Multiplikationen von vier auf drei und verbessert so die Effizienz.

---

JavaScript-Implementierung

Unten finden Sie eine robuste Implementierung des Karatsuba-Algorithmus in JavaScript. Diese Version unterstützt beliebig große Ganzzahlen, indem sie sie als Zeichenfolgen darstellt.

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

---

Hauptmerkmale der Implementierung

1. Basisfalloptimierung:

   • Für Zahlen mit bis zu 12 Ziffern verwendet der Algorithmus direkt die Zahl von JavaScript für eine effiziente Multiplikation.

2. String-Manipulation für willkürliche Präzision:

   • Der Algorithmus verwendet String-Operationen, um große Zahlen zu verarbeiten, ohne an Präzision zu verlieren.

3. Hilfsfunktionen:

   • Addition (addLargeNumbers): Behandelt die Addition zweier großer Zahlen, die als Zeichenfolgen dargestellt werden.
   • Subtraktion (subtractLargeNumbers): Verwaltet die Subtraktion mit Kreditaufnahme für große Zahlen.
   • Potenz von 10 Multiplikation (multiplyByPowerOf10): Verschiebt Zahlen effizient durch Anhängen von Nullen.

4. Rekursives Design:

   • Der Algorithmus teilt jede Eingabe rekursiv und kombiniert die Ergebnisse mithilfe der Karatsuba-Formel.

---

Leistungsüberlegungen

Der Karatsuba-Algorithmus reduziert die Anzahl der rekursiven Multiplikationen von $(O(n^2))$(O(n2)) bis ca $(O(n^{1.585}))$(O(n1,585)) . Dies macht es deutlich schneller als herkömmliche Methoden für große Eingaben. Der Overhead von String-Manipulationen kann jedoch die Leistung bei kleineren Eingaben beeinträchtigen, weshalb die Basisfalloptimierung von entscheidender Bedeutung ist.

---

Beispielausgabe

Für:

/**
 * 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));

Das Ergebnis ist:

node multiply.js

---

Fazit

Der Karatsuba-Multiplikationsalgorithmus ist eine praktische und effiziente Lösung zum Multiplizieren großer Zahlen. Diese Implementierung demonstriert ihre Leistungsfähigkeit und Flexibilität bei der Verarbeitung beliebig großer Eingaben in JavaScript. Angesichts des wachsenden Bedarfs an hochpräziser Arithmetik kann die Beherrschung solcher Algorithmen die Rechenfähigkeiten in verschiedenen Anwendungen erheblich verbessern.

Das obige ist der detaillierte Inhalt vonDen Karatsuba-Multiplikationsalgorithmus für große Zahlen verstehen und implementieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!