큰 숫자에 대한 Karatsuba 곱셈 알고리즘 이해 및 구현

계산 수학에서 큰 수를 효율적으로 곱하는 것은 암호화에서 과학 컴퓨팅에 이르기까지 다양한 응용 분야의 초석입니다. Karatsuba 곱셈 알고리즘은 큰 수에 대한 전통적인 긴 곱셈에 비해 성능을 크게 향상시키는 분할 정복 방법입니다. 이 기사에서는 문자열로 표현되는 임의의 큰 숫자를 처리하도록 설계된 이 강력한 알고리즘의 JavaScript 구현을 살펴보겠습니다.

---

전통적인 곱셈의 문제점

표준적인 "교과서" 곱셈 방법의 시간 복잡도는 $(오(n^2))$(O(n2)) , 어디 $(n)$(n) 곱해지는 숫자의 자릿수입니다. 이 2차 성장은 숫자가 커질수록 계산 비용이 많이 듭니다. 1960년 Anatolii Karatsuba가 도입한 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​=(낮음1 하이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⋅m (z1 ​ −z2​ −z0​ )⋅10 엠 z0​
   어디 $(m)$(m) 원래 숫자의 절반 자릿수입니다.

이 접근 방식은 재귀 곱셈 횟수를 4에서 3으로 줄여 효율성을 높입니다.

---

자바스크립트 구현

아래는 JavaScript에서 Karatsuba 알고리즘을 강력하게 구현한 것입니다. 이 버전은 문자열로 표현하여 임의의 큰 정수를 지원합니다.

multiply.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의 숫자를 직접 사용합니다.

2. 임의 정밀도를 위한 문자열 조작:

   • 알고리즘은 문자열 연산을 사용하여 정밀도를 잃지 않고 큰 숫자를 처리합니다.

3. 도우미 기능:

   • 덧셈(addLargeNumbers): 문자열로 표현된 두 개의 큰 숫자의 더하기를 처리합니다.
   • 뺄셈(subtractLargeNumbers): 큰 수를 빌려 빼기를 관리합니다.
   • 10의 거듭제곱(multiplyByPowerOf10): 0을 추가하여 숫자를 효율적으로 이동합니다.

4. 재귀적 디자인:

   • 알고리즘은 각 입력을 재귀적으로 나누고 Karatsuba 공식을 사용하여 결과를 결합합니다.

---

성능 고려 사항

Karatsuba 알고리즘은 다음과 같은 재귀 곱셈 횟수를 줄입니다. $(오(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 중국어 웹사이트의 기타 관련 기사를 참조하세요!