理解并实现大数的 Karatsuba 乘法算法-js教程-PHP中文网

Understanding and Implementing the Karatsuba Multiplication Algorithm for Large Numbers

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

传统乘法的问题

标准的“教科书”乘法方法的时间复杂度为

(O (n^{2} ） ） (O(n^2))

(O(n2）），在哪里

(n) (n)

(n) 是被相乘的数字的位数。随着数字变大，这种二次增长在计算上变得昂贵。 Anatolii Karatsuba 于 1960 年提出的 Karatsuba 算法将这种复杂性降低到大约

(O (n^{1.585})) (O(n^{1.585}))

(O(n1.585）），使其成为大输入的更快选择。

Karatsuba 算法的工作原理

该算法依赖于分治策略：

除法：将每个数字分成两半——高部分和低部分。
征服： 递归计算三个关键乘积：这涉及为每个递归步骤计算以下组件：
- $z_{0} = 低1 \times 低2 z_0 = 文本{low1} 乘以文本{low2}$ z0 =低1×低2
- $z_{1} = (低1 高1 ） \times （低2 high2) z_1 = (text{low1} text{high1}) 次 (text{low2} text{high2})$ z1=(low1 高1）×（低2高2）
- $z_{2} = high1 \times high2 z_2 = 文本{high1} 乘以文本{high2}$ z2=high1×high2
组合： 使用公式：
$结果 = z_{2} \cdot 1 0^{2 \cdot m} (z_{1} - z_{2} - z_{0} ） \cdot 1 0^{米} z_{0} text{结果} = z_2 cdot 10^{2 cdot m}(z_1 - z_2 - z_0) cdot 10^m 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

登录后复制

实施的主要特点

基础案例优化：
- 对于12位以内的数字，算法直接使用JavaScript的Number进行高效乘法。
任意精度的字符串操作：
- 该算法使用字符串操作来处理大数而不损失精度。
辅助功能：
- 加法 (addLargeNumbers)： 处理以字符串表示的两个大数字的相加。
- 减法 (subtractLargeNumbers)： 通过借用大数来管理减法。
- 10 次方乘法 (multiplyByPowerOf10)： 通过附加零有效地移位数字。
递归设计：
- 该算法递归地划分每个输入，并使用 Karatsuba 公式组合结果。

性能考虑因素

Karatsuba 算法减少了递归乘法的次数 $(O (n^{2} ）） (O(n^2))$ (O(n2））到大约 $(O (n^{1.585})) (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));

登录后复制

结果是：