Mendarab Nombor Perpuluhan Besar Menggunakan Transformasi Fourier Pantas (FFT)

pengenalan

Mendarab nombor perpuluhan yang besar boleh menjadi mencabar dari segi pengiraan, terutamanya apabila berurusan dengan nombor yang mempunyai banyak digit atau berbilang tempat perpuluhan. Kaedah pendaraban tradisional menjadi tidak cekap untuk nombor yang sangat besar. Di sinilah Fast Fourier Transform (FFT) datang untuk menyelamatkan, menyediakan algoritma yang berkuasa dan cekap untuk mendarab nombor besar dengan kelajuan yang luar biasa.

Aplikasi dalam Pendaraban

• FFT mendayakan pendaraban pantas polinomial atau integer besar dengan menukar nombor kepada domain kekerapan, melakukan pendaraban mengikut arah dan kemudian menggunakan FFT songsang.

Cabaran Pendaraban Nombor Besar

Kaedah pendaraban tradisional mempunyai kerumitan masa O(n²), dengan n ialah bilangan digit. Untuk nombor yang sangat besar, ini menjadi mahal dari segi pengiraan. Algoritma pendaraban berasaskan FFT mengurangkan kerumitan ini kepada O(n log n), menjadikannya lebih pantas dengan ketara untuk nombor yang besar.

Garis Besar Bukti untuk Cooley-Tukey FFT

1. Penguraian Transformasi Fourier Diskret (DFT):

   • DFT ditakrifkan sebagai:
     $$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,
     di mana $N$N ialah saiz isyarat input.
   • Cooley-Tukey FFT memecahkan pengiraan kepada saiz DFT yang lebih kecil $N\mathrm{/}2$N/2 dengan mengasingkan istilah diindeks genap dan istilah diindeks ganjil:
     $$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−1​x 2n 1​⋅ e−2πi⋅(2n 1)k/N.
   • Ini dikurangkan kepada:
     $$X_k=\text{DFT dari sekata syarat}{W}_k\cdot \text{DFT dari syarat ganjil},$$Xk​ =DFT sekata syarat Wk​⋅DFT syarat ganjil,
     di mana $W_k=e^{-2\pi i\cdot k\mathrm{/}N}$Wk​ =e−2πi ⋅k/N .

2. Struktur Rekursif:

   • Setiap saiz DFT $N$N dibahagikan kepada dua saiz DFT $N\mathrm{/}2$N/2 , membawa kepada struktur rekursif.
   • Pembahagian rekursif ini berterusan sehingga kes asas saiz $N=1$N=1 , di mana DFT hanyalah nilai input.

3. Operasi Rama-rama:

   • Algoritma menggabungkan hasil daripada DFT yang lebih kecil menggunakan operasi rama-rama:
     $$a^{\mathrm{\prime }}=u{W}_k\cdot v,b^{\mathrm{\prime }}=u-W_k\cdot v,$$a′=u Wk​⋅v,b′ =u−Wk​⋅v,
     di mana $u$u dan $v$v adalah hasil daripada DFT yang lebih kecil dan $W_k$Wk​ mewakili akar perpaduan.

4. Permutasi Pembalikan Bit:

   • Susun atur input disusun semula berdasarkan perwakilan binari indeks untuk membolehkan pengiraan di tempat.

5. Kerumitan Masa:

   • Pada setiap peringkat rekursi, terdapat $N$N pengiraan yang melibatkan punca perpaduan, dan kedalaman rekursi adalah ${\log }_2(N)$log2 ​(N) .
   • Ini menghasilkan kerumitan masa $O(N\log N)$O(NlogN) .

FFT songsang

• FFT songsang adalah serupa tetapi digunakan $e^{2\pi i\cdot kn\mathrm{/}N}$e 2πi⋅kn/N sebagai asas dan skala hasil oleh $1\mathrm{/}N$1/N .

Memahami Algoritma Pendaraban FFT

Algoritma pendaraban FFT berfungsi melalui beberapa langkah utama:

1. Praproses Nombor

   • Tukar nombor input kepada tatasusunan digit
   • Kendalikan kedua-dua bahagian integer dan perpuluhan
   • Pad tatasusunan kepada kuasa terdekat 2 untuk pengiraan FFT

2. Transformasi Fourier Pantas

   • Tukar tatasusunan nombor ke dalam domain kekerapan menggunakan FFT
   • Ini mengubah masalah pendaraban menjadi pendaraban mengikut arah yang lebih mudah dalam domain kekerapan

3. Pendaraban Domain Kekerapan

   • Lakukan pendaraban mengikut unsur bagi tatasusunan yang diubah
   • Gunakan operasi nombor kompleks untuk pengiraan yang cekap

4. FFT Songsang dan Pemprosesan Hasil

   • Ubah tatasusunan berganda kembali kepada domain masa
   • Pembawa digit pemegang
   • Bina semula nombor perpuluhan akhir

Komponen Utama Pelaksanaan

Perwakilan Nombor Kompleks

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) { /* ... */ }
}

Kelas Kompleks adalah penting untuk melaksanakan operasi FFT, membolehkan kami memanipulasi nombor dalam kedua-dua domain sebenar dan khayalan.

Fungsi Transformasi Fourier Pantas

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

Fungsi FFT ialah teras algoritma, menukar nombor antara domain masa dan kekerapan dengan cekap.

Mengendalikan Nombor Perpuluhan

Pelaksanaan termasuk logik yang canggih untuk mengendalikan nombor perpuluhan:

• Memisahkan bahagian integer dan perpuluhan
• Menjejak jumlah tempat perpuluhan
• Membina semula hasil dengan peletakan titik perpuluhan yang betul

Contoh Kes Penggunaan

// 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")

Kelebihan Prestasi

• Kerumitan Masa: O(n log n) berbanding O(n²) kaedah tradisional
• Ketepatan: Mengendalikan nombor yang sangat besar dengan berbilang tempat perpuluhan
• Kecekapan: Jauh lebih cepat untuk pendaraban nombor besar

Had dan Pertimbangan

• Memerlukan memori tambahan untuk perwakilan nombor kompleks
• Ketepatan boleh dipengaruhi oleh aritmetik titik terapung
• Pelaksanaan yang lebih kompleks berbanding pendaraban tradisional

Kesimpulan

Algoritma pendaraban FFT mewakili pendekatan yang berkuasa untuk mendarab nombor besar dengan cekap. Dengan memanfaatkan transformasi domain frekuensi, kami boleh melakukan operasi matematik yang kompleks dengan kelajuan dan ketepatan yang luar biasa.

Aplikasi Praktikal

• Pengkomputeran saintifik
• Pengiraan kewangan
• Kriptografi
• Simulasi berangka berskala besar

Bacaan Selanjutnya

• Algoritma FFT Cooley-Tukey
• Teori Nombor
• Matematik Pengiraan

Kod

Pelaksanaan lengkap menyusul, menyediakan penyelesaian yang mantap untuk mendarab nombor perpuluhan besar menggunakan pendekatan Fast Fourier Transform.

/**
 * 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+$/, "")
  );
}

Keluaran

// 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

Atas ialah kandungan terperinci Mendarab Nombor Perpuluhan Besar Menggunakan Transformasi Fourier Pantas (FFT). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!