理解并实现大数的 Karatsuba 乘法算法

在计算数学中，有效地乘以大数是从密码学到​​科学计算等各种应用的基石。 Karatsuba 乘法算法 是一种分而治之的方法，与传统的大数长乘法相比，它显着提高了性能。在本文中，我们将探索这种强大算法的 JavaScript 实现，该算法旨在处理表示为字符串的任意大数字。

---

传统乘法的问题

标准的“教科书”乘法方法的时间复杂度为 $(O(n^2））$(O(n2）） ， 在哪里 $(n)$(n) 是被相乘的数字的位数。随着数字变大，这种二次增长在计算上变得昂贵。 Anatolii Karatsuba 于 1960 年提出的 Karatsuba 算法将这种复杂性降低到大约 $(O(n^{1.585}))$(O(n1.585）） ，使其成为大输入的更快选择。

---

Karatsuba 算法的工作原理

该算法依赖于分治策略：

1. 除法：将每个数字分成两半——高部分和低部分。
2. 征服： 递归计算三个关键乘积：这涉及为每个递归步骤计算以下组件：
   • $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{结果}=z_2\cdot 10^{2\cdot m}(z_1-z_2-z_0）\cdot 10^{米}{z}_0$$结果= z2​⋅102⋅m (z1 ​ −z2​ −z0​ )⋅10 米 z0​
   在哪里 $(米)$(m) 是原始数字位数的一半。

这种方法将递归乘法的次数从 4 次减少到 3 次，从而提高了效率。

---

JavaScript 实现

下面是 JavaScript 中 Karasuba 算法的稳健实现。此版本通过将任意大整数表示为字符串来支持它们。

乘法.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)： 处理以字符串表示的两个大数字的相加。
   • 减法 (subtractLargeNumbers)： 通过借用大数来管理减法。
   • 10 次方乘法 (multiplyByPowerOf10)： 通过附加零有效地移位数字。

4. 递归设计：

   • 该算法递归地划分每个输入，并使用 Karatsuba 公式组合结果。

---

性能考虑因素

Karatsuba 算法减少了递归乘法的次数 $(O(n^2））$(O(n2）） 到大约 $(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 中的任意大输入时展示了其强大功能和灵活性。随着对高精度运算的需求不断增长，掌握此类算法可以大大增强各种应用中的计算能力。

以上是理解并实现大数的 Karatsuba 乘法算法的详细内容。更多信息请关注PHP中文网其他相关文章！