高速フーリエ変換 (FFT) を使用した大きな 10 進数の乗算

導入

大きな 10 進数の乗算は、特に桁数や小数点以下の桁数が多い数値を扱う場合、計算が困難になることがあります。従来の乗算方法は、数値が非常に大きい場合には非効率的になります。ここで高速フーリエ変換 (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 i\cdot kn\mathrm{/}N},$$Xk = n=0∑N−1 xn⋅ e−2πi⋅kn /N、
     どこ $N$N は入力信号のサイズです。
   • Cooley-Tukey FFT は、計算をより小さなサイズの DFT に分割します。 $N\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}_{2n1}\cdot e^{-2\pi i\cdot (2n1)k\mathrm{/}N}\mathrm{.}$$Xk = n=0∑N/2−1 x2n ⋅e −2πi⋅(2n)k/N n=0∑N/ 2−1x2n 1⋅ e−2πi⋅(2n 1)k/N.
   • これは次のようになります。
     $$X_k=\text{偶数項の DFT}{W}_k\cdot \text{奇数項の DFT}、$$Xk =偶数項の DFT Wk⋅奇数項の DFT、
     どこ $W_k=e^{-2\pi i\cdot k\mathrm{/}N}$Wk =e−2πi ⋅k/N .

2. 再帰構造:

   • サイズの各 DFT $N$N サイズが異なる 2 つの DFT に分割されます。 $N\mathrm{/}2$N/2 、再帰的な構造につながります。
   • この再帰的な除算は、サイズの基本ケースが得られるまで継続されます。 $N=1$N=1 この時点では、DFT は単なる入力値です。

3. バタフライオペレーション:

   • アルゴリズムは、バタフライ演算を使用して、より小さな DFT からの結果をマージします。
     $$a^{\mathrm{\text{'}}}=u{W}_k\cdot v、b^{\mathrm{\text{'}}}=u-W_k\cdot v,$$a'=u Wk⋅v,b' =u−Wk⋅v,
     どこ $u$u そして $v$v はより小さな DFT の結果であり、 $W_k$Wk 団結の根源を表します。

4. ビット反転順列:

   • 入力配列は、インプレース計算を可能にするために、インデックスのバイナリ表現に基づいて並べ替えられます。

5. 時間計算量:

   • 再帰の各レベルには、 $N$N 単一根を含む計算、再帰の深さは次のとおりです。 ${\mathrm{ログ}}_2(N)$log2 (N) .
   • これにより、時間計算量は次のようになります。 $O(N\mathrm{ログ}N)$O(NlogN) .

逆FFT

• 逆 FFT は似ていますが、以下を使用します。 $e^{2\pi i\cdot kn\mathrm{/}N}$e 2πi⋅kn/N を基準として結果をスケールします $1\mathrm{/}N$1/N .

FFT乗算アルゴリズムを理解する

FFT 乗算アルゴリズムは、いくつかの重要なステップを通じて機能します。

1. 数値の前処理

   • 入力数値を数字の配列に変換します
   • 整数部分と小数部分の両方を処理します
   • FFT 計算のために配列を最も近い 2 のべき乗にパディングします

2. 高速フーリエ変換

   • FFT を使用して数値配列を周波数領域に変換します
   • これにより、乗算の問題が周波数領域でのより単純な点ごとの乗算に変換されます

3. 周波数領域の乗算

   • 変換された配列の要素ごとの乗算を実行します
   • 効率的な計算のために複素数演算を利用する

4. 逆 FFT と結果処理

   • 乗算された配列を時間領域に変換して戻します
   • ハンドル桁桁
   • 最後の 10 進数を再構築します

実装の主要なコンポーネント

複素数表現

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 関数はアルゴリズムの中核であり、時間領域と周波数領域の間で数値を効率的に変換します。

10 進数の処理

実装には、10 進数を処理するための高度なロジックが含まれています。

• 整数部分と小数部分の分離
• 小数点以下の合計桁数の追跡
• 正しい小数点の位置で結果を再構築する

使用例の例

// 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 アルゴリズム
• 整数論
• 計算数学

コード

完全な実装は次のとおりで、高速フーリエ変換アプローチを使用して大きな 10 進数を乗算するための堅牢なソリューションを提供します。

/**
 * 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) を使用した大きな 10 進数の乗算の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。