在計(jì)算數(shù)學(xué)中，有效地乘以大數(shù)是從密碼學(xué)到??科學(xué)計(jì)算等各種應(yīng)用的基石。 Karatsuba 乘法算法 是一種分而治之的方法，與傳統(tǒng)的大數(shù)長乘法相比，它顯著提高了性能。在本文中，我們將探索這種強(qiáng)大算法的 JavaScript 實(shí)現(xiàn)，該算法旨在處理表示為字符串的任意大數(shù)字。

傳統(tǒng)乘法的問題

標(biāo)準(zhǔn)的“教科書”乘法方法的時(shí)間復(fù)雜度為 $(O(n^2））$(O(n2）） ， 在哪里 $(n)$(n) 是被相乘的數(shù)字的位數(shù)。隨著數(shù)字變大，這種二次增長在計(jì)算上變得昂貴。 Anatolii Karatsuba 于 1960 年提出的 Karatsuba 算法將這種復(fù)雜性降低到大約 $(O(n^{1.585}))$(O(n1.585）） ，使其成為大輸入的更快選擇。

Karatsuba 算法的工作原理

該算法依賴于分治策略：

1. 除法：將每個(gè)數(shù)字分成兩半——高部分和低部分。
2. 征服： 遞歸計(jì)算三個(gè)關(guān)鍵乘積：這涉及為每個(gè)遞歸步驟計(jì)算以下組件：
   • $z_0=\text{低1}\times \text{低2}$z0? =低1×低2
   • $z_1=(\text{低1}\text{高1}）\times （\text{低2}\text{high2})$z1?=(low1 高1）×（低2高2）
   • $z_2=\text{high1}\times \text{high2}$z2?=high1×high2
3. 組合： 使用公式：
   $$\text{結(jié)果}=z_2?10^{2?m}(z_1?z_2?z_0）?10^{米}{z}_0$$結(jié)果= z2??102?m (z1 ? ?z2? ?z0? )?10 米 z0?
   在哪里 $(米)$(m) 是原始數(shù)字位數(shù)的一半。

這種方法將遞歸乘法的次數(shù)從 4 次減少到 3 次，從而提高了效率。

JavaScript 實(shí)現(xiàn)

下面是 JavaScript 中 Karasuba 算法的穩(wěn)健實(shí)現(xiàn)。此版本通過將任意大整數(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

實(shí)施的主要特點(diǎn)

1. 基礎(chǔ)案例優(yōu)化：

   • 對(duì)于12位以內(nèi)的數(shù)字，算法直接使用JavaScript的Number進(jìn)行高效乘法。

2. 任意精度的字符串操作：

   • 該算法使用字符串操作來處理大數(shù)而不損失精度。

3. 輔助功能：

   • 加法 (addLargeNumbers)： 處理以字符串表示的兩個(gè)大數(shù)字的相加。
   • 減法 (subtractLargeNumbers)： 通過借用大數(shù)來管理減法。
   • 10 次方乘法 (multiplyByPowerOf10)： 通過附加零有效地移位數(shù)字。

4. 遞歸設(shè)計(jì)：

   • 該算法遞歸地劃分每個(gè)輸入，并使用 Karatsuba 公式組合結(jié)果。

性能考慮因素

Karatsuba 算法減少了遞歸乘法的次數(shù) $(O(n^2））$(O(n2）） 到大約 $(O(n^{1.585}))$(O(n1.585）） 。這使得它比大輸入的傳統(tǒng)方法要快得多。然而，字符串操作的開銷可能會(huì)影響較小輸入的性能，這就是為什么基本情況優(yōu)化至關(guān)重要。

示例輸出

對(duì)于：

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

結(jié)果是：

node multiply.js

結(jié)論

Karatsuba 乘法算法是一種實(shí)用且高效的大數(shù)乘法解決方案。此實(shí)現(xiàn)在處理 JavaScript 中的任意大輸入時(shí)展示了其強(qiáng)大功能和靈活性。隨著對(duì)高精度運(yùn)算的需求不斷增長，掌握此類算法可以大大增強(qiáng)各種應(yīng)用中的計(jì)算能力。

以上是理解并實(shí)現(xiàn)大數(shù)的 Karatsuba 乘法算法的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！