FFT(고속 푸리에 변환)를 사용하여 큰 십진수 곱하기

소개

큰 십진수를 곱하는 것은 계산상 어려울 수 있으며, 특히 자릿수가 많거나 소수 자릿수가 여러 개인 숫자를 처리할 때 더욱 그렇습니다. 전통적인 곱셈 방법은 매우 큰 수에는 비효율적입니다. FFT(고속 푸리에 변환)가 구출되어 놀라운 속도로 많은 수를 곱할 수 있는 강력하고 효율적인 알고리즘을 제공합니다.

곱셈의 응용

• FFT는 숫자를 주파수 영역으로 변환하고 점별 곱셈을 수행한 다음 역 FFT를 적용하여 다항식 또는 큰 정수의 빠른 곱셈을 가능하게 합니다.

큰 수 곱셈의 과제

기존의 곱셈 방법은 O(n²)의 시간 복잡도를 갖습니다. 여기서 n은 자릿수입니다. 매우 큰 숫자의 경우 계산 비용이 많이 듭니다. FFT 기반 곱셈 알고리즘은 이러한 복잡성을 O(n log n)로 줄여 큰 숫자의 경우 훨씬 더 빠르게 만듭니다.

Cooley-Tukey FFT에 대한 증명 개요

1. 이산 푸리에 변환(DFT) 분해:

   • DFT는 다음과 같이 정의됩니다.
     $$X_k=\sum _{n=0}^{n-1}{x}_n\cdot e^{-2\pi 나\cdot kn\mathrm{/}n},$$Xk ​= n=0∑N−1​ xn​⋅ e−2πi⋅kn /N,
     어디 $\mathrm{없음}$없음 입력 신호의 크기입니다.
   • Cooley-Tukey FFT는 계산을 더 작은 DFT 크기로 나눕니다. $\mathrm{없음}\mathrm{/}2$N/2 짝수 색인 용어와 홀수 색인 용어를 분리하여:
     $$X_k=\sum _{n=0}^{N\mathrm{/}2-1}{x}_{2n}\cdot e^{-2\pi i\cdot (2n)k\mathrm{/}N}\sum _{n=0}^{N\mathrm{/}2-1}{x}_{2ㄴ1}\cdot e^{-2\pi i\cdot (2n1)k\mathrm{/}N}\mathrm{.}$$Xk ​= n=0∑N/2−1​ x2n​ ⋅에 −2πi⋅(2n)k/N n=0∑N/ 2−1​x2n 1​⋅ e−2πi⋅(2n 1)k/N.
   • 다음과 같이 줄어듭니다.
     $$X_k=\text{짝수 항의 DFT}{W}_k\cdot \text{홀수항의 DFT},$$Xk​ =짝수 항의 DFT Wk​⋅홀수항의 DFT,
     어디 $W_{ㅋ}=e^{-2\pi i\cdot k\mathrm{/}N}$와k​ =e−2πi ⋅k/N .

2. 재귀 구조:

   • 각 DFT 크기 $\mathrm{없음}$없음 두 개의 DFT 크기로 분할됩니다. $\mathrm{없음}\mathrm{/}2$N/2 , 재귀적 구조로 이어집니다.
   • 이 재귀적 분할은 크기의 기본 사례까지 계속됩니다. $N=1$N=1 , 이 시점에서 DFT는 단순히 입력 값입니다.

3. 나비 작전:

   • 알고리즘은 나비 연산을 사용하여 더 작은 DFT의 결과를 병합합니다.
     $${아}^{\mathrm{\prime }}=유W_k\cdot v,b^{\mathrm{\prime }}=u-W_k\cdot v,$$아′=u Wk​⋅v,b′ =u−Wㅋ​⋅v,
     어디 $유$유 그리고 $v$v 더 작은 DFT의 결과이고 $W_k$Wk​ 화합의 뿌리를 상징합니다.

4. 비트 반전 순열:

   • 입력 배열은 내부 계산이 가능하도록 인덱스의 이진 표현을 기반으로 재정렬됩니다.

5. 시간 복잡성:

   • 각 재귀 수준에는 다음이 있습니다. $\mathrm{없음}$없음 단위근을 포함하는 계산과 재귀의 깊이는 다음과 같습니다. ${\mathrm{로그}}_2(N)$로g2 ​(N) .
   • 이로 인해 다음과 같은 시간 복잡도가 발생합니다. $오(N\mathrm{로그}N)$O(NlogN) .

역 FFT

• 역 FFT는 유사하지만 다음을 사용합니다. $e^{2\pi i\cdot kn\mathrm{/}n}$에 2πi⋅kn/N 기준으로 삼고 결과를 다음과 같이 확장합니다. $1\mathrm{/}N$1/N .

FFT 곱셈 알고리즘 이해

FFT 곱셈 알고리즘은 여러 주요 단계를 통해 작동합니다.

1. 숫자 전처리

   • 입력 숫자를 숫자 배열로 변환
   • 정수 부분과 소수 부분 모두 처리
   • FFT 계산을 위해 가장 가까운 2의 거듭제곱으로 배열을 채웁니다

2. 고속 푸리에 변환

   • FFT를 사용하여 숫자 배열을 주파수 영역으로 변환
   • 이것은 곱셈 문제를 주파수 영역에서 더 간단한 점별 곱셈으로 변환합니다

3. 주파수 영역 곱셈

   • 변환된 배열의 요소별 곱셈 수행
   • 효율적인 계산을 위해 복소수 연산 활용

4. 역 FFT 및 결과 처리

   • 곱해진 배열을 다시 시간 영역으로 변환
   • 숫자 캐리 처리
   • 마지막 십진수 재구성

구현의 주요 구성요소

복소수 표현

class Complex {
  constructor(re = 0, im = 0) {
    this.re = re;  // Real part
    this.im = im;  // Imaginary part
  }

  // Static methods for complex number operations
  static add(a, b) { /* ... */ }
  static subtract(a, b) { /* ... */ }
  static multiply(a, b) { /* ... */ }
}

Complex 클래스는 FFT 연산을 수행하는 데 매우 중요하며 실수 영역과 허수 영역 모두에서 숫자를 조작할 수 있게 해줍니다.

고속 푸리에 변환 기능

function fft(a, invert = false) {
  // Bit reversal preprocessing
  // Butterfly operations in frequency domain
  // Optional inverse transformation
}

FFT 기능은 시간 영역과 주파수 영역 사이의 숫자를 효율적으로 변환하는 알고리즘의 핵심입니다.

소수 처리

구현에는 십진수 처리를 위한 정교한 논리가 포함됩니다.

• 정수와 소수 부분 분리
• 총 소수점 이하 자릿수 추적
• 올바른 소수점 배치로 결과 재구성

사용 사례 예시

// Multiplying large integers
fftMultiply("12345678901234567890", "98765432109876543210")

// Multiplying very large different size integers
fftMultiply("12345678901234567890786238746872364872364987293795843790587345", "9876543210987654321087634875782369487239874023894")

// Multiplying decimal numbers
fftMultiply("123.456", "987.654")

// Handling different decimal places
fftMultiply("1.23", "45.6789")

// Handling different decimal places with large numbers
fftMultiply("1234567890123456789078623874687236487236498.7293795843790587345", "98765432109876543210876348757823694.87239874023894")

성능상의 이점

• 시간 복잡도: 기존 방법의 O(n²) 대비 O(n log n)
• 정밀도: 소수점 이하 자릿수가 여러 개인 매우 큰 숫자를 처리합니다
• 효율성: 큰 수의 곱셈에서 훨씬 더 빠릅니다

제한 사항 및 고려 사항

• 복소수 표현을 위해 추가 메모리 필요
• 정밀도는 부동 소수점 연산의 영향을 받을 수 있습니다
• 기존 곱셈에 비해 더 복잡한 구현

결론

FFT 곱셈 알고리즘은 큰 수를 효율적으로 곱하는 강력한 접근 방식을 나타냅니다. 주파수 영역 변환을 활용하면 놀라운 속도와 정밀도로 복잡한 수학 연산을 수행할 수 있습니다.

실제 응용

• 과학컴퓨팅
• 재무계산
• 암호화
• 대규모 수치 시뮬레이션

추가 자료

• Cooley-Tukey FFT 알고리즘
• 수론
• 계산수학

암호

완전한 구현은 고속 푸리에 변환 접근 방식을 사용하여 큰 십진수를 곱하기 위한 강력한 솔루션을 제공하는 것입니다.

/**
 * Fast Fourier Transform (FFT) implementation for decimal multiplication
 * @param {number[]} a - Input array of real numbers
 * @param {boolean} invert - Whether to perform inverse FFT
 * @returns {Complex[]} - Transformed array of complex numbers
 */
class Complex {
  constructor(re = 0, im = 0) {
    this.re = re;
    this.im = im;
  }

  static add(a, b) {
    return new Complex(a.re + b.re, a.im + b.im);
  }

  static subtract(a, b) {
    return new Complex(a.re - b.re, a.im - b.im);
  }

  static multiply(a, b) {
    return new Complex(a.re * b.re - a.im * b.im, a.re * b.im + a.im * b.re);
  }
}

function fft(a, invert = false) {
  let n = 1;
  while (n < a.length) n <<= 1;
  a = a.slice(0);
  a.length = n;

  const angle = ((2 * Math.PI) / n) * (invert ? -1 : 1);
  const roots = new Array(n);
  for (let i = 0; i < n; i++) {
    roots[i] = new Complex(Math.cos(angle * i), Math.sin(angle * i));
  }

  // Bit reversal
  for (let i = 1, j = 0; i < n; i++) {
    let bit = n >> 1;
    for (; j & bit; bit >>= 1) {
      j ^= bit;
    }
    j ^= bit;
    if (i < j) {
      [a[i], a[j]] = [a[j], a[i]];
    }
  }

  // Butterfly operations
  for (let len = 2; len <= n; len <<= 1) {
    const halfLen = len >> 1;
    for (let i = 0; i < n; i += len) {
      for (let j = 0; j < halfLen; j++) {
        const u = a[i + j];
        const v = Complex.multiply(a[i + j + halfLen], roots[(n / len) * j]);
        a[i + j] = Complex.add(u, v);
        a[i + j + halfLen] = Complex.subtract(u, v);
      }
    }
  }

  if (invert) {
    for (let i = 0; i < n; i++) {
      a[i].re /= n;
      a[i].im /= n;
    }
  }

  return a;
}

/**
 * Multiply two decimal numbers using FFT
 * @param {string} num1 - First number as a string
 * @param {string} num2 - Second number as a string
 * @returns {string} - Product of the two numbers
 */
function fftMultiply(num1, num2) {
  // Handle zero cases
  if (num1 === "0" || num2 === "0") return "0";

  // Parse and separate integer and decimal parts
  const parseNumber = (numStr) => {
    const [intPart, decPart] = numStr.split(".");
    return {
      intPart: intPart || "0",
      decPart: decPart || "",
      totalDecimalPlaces: (decPart || "").length,
    };
  };

  const parsed1 = parseNumber(num1);
  const parsed2 = parseNumber(num2);

  // Combine numbers removing decimal point
  const combinedNum1 = parsed1.intPart + parsed1.decPart;
  const combinedNum2 = parsed2.intPart + parsed2.decPart;

  // Total decimal places
  const totalDecimalPlaces =
    parsed1.totalDecimalPlaces + parsed2.totalDecimalPlaces;

  // Convert to digit arrays (least significant first)
  const a = combinedNum1.split("").map(Number).reverse();
  const b = combinedNum2.split("").map(Number).reverse();

  // Determine result size and pad
  const resultSize = a.length + b.length;
  const fftSize = 1 << Math.ceil(Math.log2(resultSize));

  // Pad input arrays
  while (a.length < fftSize) a.push(0);
  while (b.length < fftSize) b.push(0);

  // Convert to complex arrays
  const complexA = a.map((x) => new Complex(x, 0));
  const complexB = b.map((x) => new Complex(x, 0));

  // Perform FFT
  const fftA = fft(complexA);
  const fftB = fft(complexB);

  // Pointwise multiplication in frequency domain
  const fftProduct = new Array(fftSize);
  for (let i = 0; i < fftSize; i++) {
    fftProduct[i] = Complex.multiply(fftA[i], fftB[i]);
  }

  // Inverse FFT
  const product = fft(fftProduct, true);

  // Convert back to integer representation
  const result = new Array(resultSize).fill(0);
  for (let i = 0; i < resultSize; i++) {
    result[i] = Math.round(product[i].re);
  }

  // Handle carries
  for (let i = 0; i < result.length - 1; i++) {
    if (result[i] >= 10) {
      result[i + 1] += Math.floor(result[i] / 10);
      result[i] %= 10;
    }
  }

  // Remove leading zeros and convert to string
  while (result.length > 1 && result[result.length - 1] === 0) {
    result.pop();
  }

  // Insert decimal point
  const resultStr = result.reverse().join("");
  if (totalDecimalPlaces === 0) {
    return resultStr;
  }

  // Handle case where result might be shorter than decimal places
  if (resultStr.length <= totalDecimalPlaces) {
    return "0." + "0".repeat(totalDecimalPlaces - resultStr.length) + resultStr;
  }

  // Insert decimal point
  return (
    resultStr.slice(0, -totalDecimalPlaces) +
    "." +
    resultStr.slice(-totalDecimalPlaces).replace(/0+$/, "")
  );
}

산출

// Example Usage - Self verify using Python
console.log(
  "Product of integers:",
  fftMultiply("12345678901234567890", "98765432109876543210")
);
console.log("Product of decimals:", fftMultiply("123.456", "987.654"));
console.log("Product of mixed decimals:", fftMultiply("12.34", "56.78"));
console.log(
  "Product with different decimal places:",
  fftMultiply("1.23", "45.6789")
);
console.log(
  "Product with large integers:",
  fftMultiply(
    "12345678901234567890786238746872364872364987293795843790587345",
    "9876543210987654321087634875782369487239874023894"
  )
);
const num1 = "1234567890123456789078623874687236487236498.7293795843790587345";
const num2 = "98765432109876543210876348757823694.87239874023894";
console.log("Product:", fftMultiply(num1, num2));

Product of integers: 1219326311370217952237463801111263526900
Product of decimals: 121931.812224
Product of mixed decimals: 700.6652
Product with different decimal places: 56.185047
Product with large integers: 121932631137021795232593613105722759976860134207381319681901040774443113318245930967231822167723255326824021430
Product: 121932631137021795232593613105722759976860134207381319681901040774443113318245.93096723182216772325532682402143

위 내용은 FFT(고속 푸리에 변환)를 사용하여 큰 십진수 곱하기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!