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

---

従來の掛け算の問題

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

---

Karatsuba アルゴリズムの仕組み

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

1. 除算: 各數(shù)値を 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?10^{2?m}(z_1?z_2?z_0)?10^m{z}_0$$結果= z2?102?分 (z1 ?z2 ?z0 )?10 m z0
   どこ $(m)$(男) 元の數(shù)値の桁數(shù)の半分です。

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

---

JavaScript の実裝

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

乗算.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 桁の數(shù)値の場合、アルゴリズムは効率的な乗算のために JavaScript の Number を直接使用します。

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

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

3. ヘルパー関數(shù):

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

4. 再帰的デザイン:

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

---

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

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

---

出力例

対象:

/**
 * 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 乗算アルゴリズムは、大きな數(shù)を乗算するための実用的で効率的なソリューションです。この実裝は、JavaScript で任意に大きな入力を処理する際のその能力と柔軟性を実証します。高精度の演算に対するニーズが高まる中、このようなアルゴリズムを習得することで、さまざまなアプリケーションの計算能力を大幅に向上させることができます。

以上が大きな數(shù)に対するカラツバ乗算アルゴリズムの理解と実裝の詳細內容です。詳細については、PHP 中國語 Web サイトの他の関連記事を參照してください。