使用快速傅立葉變換 (FFT) 乘以大十進制數

介紹

將大十進制數相乘可能在計算上具有挑戰性，尤其是在處理具有許多位數或多個小數位的數字時。傳統的乘法方法對於極大的數字來說效率很低。這就是快速傅立葉變換 (FFT) 發揮作用的地方，它提供了一種強大而高效的演算法，可以以驚人的速度進行大數相乘。

乘法中的應用

• FFT 透過將數字轉換到頻域、執行逐點乘法，然後應用逆 FFT 來實現多項式或大整數的快速乘法。

大數乘法的挑戰

傳統乘法方法的時間複雜度為 O(n²)，其中 n 是位數。對於非常大的數字，這在計算上變得昂貴。基於 FFT 的乘法演算法將這種複雜性降低到 O(n log n)，使得處理大數的速度顯著加快。

Cooley-Tukey FFT 的證明大綱

1. 離散傅立葉轉換 (DFT) 的分解:

   • DFT 定義為：
     $$X_k=\underset{n=0}{\overset{N-1}{\Sigma }}{x}_n\cdot e^{-2\pi i\cdot kn\mathrm{/}N}N$$X_k = sum_{n=0}^{N-1} x_n cdot e^{-2pi i cdot kn / N}, Xk = n=0ΣN−1 xn e
     −2πi⋅kn /N, 在哪裡 $N$NN
   • 是輸入訊號的大小。 $Cooley-Tukey\; FFT\; 將計算分解為更小的\; DFT\mathrm{}N\mathrm{}/$N/2 N/2
     透過分離偶數索引和奇數索引項： $${}_{}k\underset{\Sigma n\mathrm{}=}{\overset{0\mathrm{}N\mathrm{}/2\mathrm{}-}{=}}1{}_{\mathrm{x}2}n{\cdot }^{e\mathrm{}-2\pi i\cdot \mathrm{}(2n)\mathrm{}k/}N\underset{\Sigma n\mathrm{}=}{\overset{0\mathrm{}0\mathrm{}0\mathrm{}}{}}{}_{\mathrm{}/2\mathrm{-}}{x}^{n\mathrm{}1\cdot e\mathrm{}-e\mathrm{-}\pi i\mathrm{}\cdot (}2\mathrm{}n$$Xk k k k k k k k > >= n=0ΣN/2−1 xC🎜>> −2πi⋅(2n)k/N
     n=0
   • $${}_{}\text{}{}_{}2n\; 1$$​ ⋅ e。 這減少為： Xk=k=
     => 🎜> Wk⋅DFT 的奇數項>DFT 的奇數項🎜> X_k = text{偶數項的DFT} W_k cdot text{奇數項的DFT}， Xk​ =DFT 的偶數項 k> 🎜>⋅奇數項的DFT, 在哪裡 $W_k=e^{-2\pi i\cdot k\mathrm{/}N}$Wk =e−2πi ⋅k/N
   .

2. 遞歸結構

   :
   • 每個大小的 DFT $N$NN$\mathrm{}\mathrm{N}2$N/2 N/2
   • ，導致遞歸結構。 $\mathrm{N}1$N = 1 N=1
3. ，此時 DFT 只是輸入值。
   • 蝴蝶操作
     : $$此演算法使用蝶形運算合併較小\; DFT\; 的結果：{}^{\mathrm{}}a\prime =\prime {}_{\mathrm{C🎜>}}Wk\cdot v^{\mathrm{,}}b\prime {=}_u-Wk$$v,a' = u W_k cdot v，四邊形 ue - W_b' = u - W_k c u - W_k c ， 一個′=u Wkkk >⋅v,b =u−WW 🎜>k
     ⋅v,⋅v,v, 在哪裡 $u$uuu$v$v v$v{}_v$ 是較小 DFT 的結果， WkW_k Wk

5. 代表團結的根源。

   位元反轉排列: 輸入數組根據索引的二進位表示重新排序，以實現就地計算。 時間複雜度:
   • 在每一層遞迴中，都有 $N$NN $涉及單位根的計算，遞歸的深度是{日誌}_{\mathrm{}}2(N$log_2(N) log2 (N)
   • (N)$\mathrm{(N)}\mathrm{(N)}(N)(N)(N)$ .
   這會產生時間複雜度

• O(${}^{\mathrm{N})\mathrm{O(N\; log\; N)}O(NlogN)\mathrm{}.}逆FFT$ 逆 FFT 類似，但使用 e2π2π ⋅k$n/\mathrm{}N\mathrm{}N$e^{2pi i> kn / N} e

2πi⋅kn/N

1. 作為基礎並對結果進行縮放

2. 1

   /
   • N
   • 1/N

3. 1/N

   • .
   了解 FFT 乘法演算法
FFT 乘法演算法的工作原理有幾個關鍵步驟：

4. 預處理數字 將輸入數字轉換為數字數組 同時處理整數和小數部分 將陣列填入最接近的 2 次方以進行 FFT 計算 快速傅立葉轉換 使用 FFT 將數字數組轉換為頻域 這將乘法問題轉換為頻域中更簡單的逐點乘法 頻域乘法 對轉換後的陣列執行逐元素乘法 利用複數運算進行高效率計算 逆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 log n) 與傳統方法的 O(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中文網其他相關文章！