大きな数に対するカラツバ乗算アルゴリズムの理解と実装

計算数学では、大きな数を効率的に乗算することは、暗号学から科学計算に至るまで、さまざまなアプリケーションの基礎です。 カラツバ乗算アルゴリズムは、大きな数に対する従来の長い乗算よりもパフォーマンスを大幅に向上させる分割統治法です。この記事では、文字列として表現される任意の大きな数値を処理するように設計されたこの強力なアルゴリズムの JavaScript 実装について説明します。

---

従来の掛け算の問題

標準的な「教科書」乗算方法の時間計算量は $(O(n^2))$(O(n2)) 、 どこ $(n)$(n) 乗算される数値の桁数です。この二次関数の増加は、数値が大きくなるにつれて計算コストが高くなります。 1960 年に Anatolii Karatsuba によって導入された Karatsuba アルゴリズムは、この複雑さを約 $(O(n^{\mathrm{}}))(O(n^\{1.585\}))$(O(n1.585)) これにより、大規模な入力に対してより高速なオプションになります。

---

Karatsuba アルゴリズムの仕組み

アルゴリズムは分割統治戦略に依存しています:

1. 除算: 各数値を 2 つの半分 (高い部分と低い部分) に分割します。
2. 征服: 3 つの主要な積を再帰的に計算します。これには、各再帰ステップで次のコンポーネントを計算することが含まれます。
   • $z_0=\text{low1}\times \text{low2}$z0 =low1×low2
   • $z_1=(\text{低1}\text{high1})\times (\text{low2}\text{high2})$z1=(low1 高1)×(低2 高2)
   • $z_2=\text{高 1}\times \text{高 2}$z2=高 1×高 2
3. 結合: 次の式を使用します:
   $$\text{結果}=z_2\cdot 10^{2\cdot m}(z_1-z_2-z_0)\cdot 10^m{z}_0$$結果= z2⋅102⋅分 (z1 −z2 −z0 )⋅10 m z0
   どこ $(m)$(男) 元の数値の桁数の半分です。

このアプローチにより、再帰乗算の数が 4 から 3 に減り、効率が向上します。

---

JavaScript の実装

以下は、JavaScript での Karatsuba アルゴリズムの堅牢な実装です。このバージョンでは、文字列として表すことにより、任意の大きな整数をサポートします。

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

---

実装の主な機能

1. ベースケースの最適化:

   • 最大 12 桁の数値の場合、アルゴリズムは効率的な乗算のために JavaScript の Number を直接使用します。

2. 任意精度のための文字列操作:

   • アルゴリズムは文字列演算を使用して、精度を損なうことなく大きな数値を処理します。

3. ヘルパー関数:

   • 加算 (addLargeNumbers): 文字列として表される 2 つの大きな数値の加算を処理します。
   • 減算 (subtractLargeNumbers): 大きな数値を借用して減算を管理します。
   • 10 のべき乗乗算 (multiplyByPowerOf10): ゼロを追加することで数値を効率的にシフトします。

4. 再帰的デザイン:

   • アルゴリズムは各入力を再帰的に分割し、カラツバ式を使用して結果を結合します。

---

パフォーマンスに関する考慮事項

Karatsuba アルゴリズムは、再帰的な乗算の数を削減します。 $(O(n^2))$(O(n2)) およそに $(O(n^{\mathrm{}}))(O(n^\{1.585\}))$(O(n1.585)) 。これにより、大規模な入力に対して従来の方法よりも大幅に高速になります。ただし、文字列操作のオーバーヘッドは、入力が小さい場合のパフォーマンスに影響を与える可能性があるため、基本ケースの最適化が重要です。

---

出力例

対象:

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

---

結論

Karatsuba 乗算アルゴリズムは、大きな数を乗算するための実用的で効率的なソリューションです。この実装は、JavaScript で任意に大きな入力を処理する際のその能力と柔軟性を実証します。高精度の演算に対するニーズが高まる中、このようなアルゴリズムを習得することで、さまざまなアプリケーションの計算能力を大幅に向上させることができます。

以上が大きな数に対するカラツバ乗算アルゴリズムの理解と実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。