cari
Rumahhujung hadapan webtutorial jsMendarab Nombor Perpuluhan Besar Menggunakan Transformasi Fourier Pantas (FFT)

Multiplying Large Decimal Numbers Using Fast Fourier Transform (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:
      Xk=n=0N1 xne2π ikn/N,X_k = jumlah_{n=0}^{N-1} x_n cdot e^{-2pi i cdot kn / N}, Xk = n=0N−1 xne−2πi⋅kn /N,
      di mana NN N ialah saiz isyarat input.
    • Cooley-Tukey FFT memecahkan pengiraan kepada saiz DFT yang lebih kecil N/2N/2 N/2 dengan mengasingkan istilah diindeks genap dan istilah diindeks ganjil:
      Xk=n=0N/2 1x2ne2πi (2n )k/N n=0N / 21x2 n 1e2 πi(2n 1)k/N.X_k = jumlah_{n=0}^{N/2-1} x_{2n} cdot e^{-2pi i cdot (2n)k / N} sum_{n=0}^{N/2-1} x_{2n 1} cdot e^{-2pi i cdot (2n 1)k / N}. Xk = n=0N/2−1x2n e −2πi⋅(2n)k/N n=0N/ 2−1x 2n 1e−2πi⋅(2n 1)k/N.
    • Ini dikurangkan kepada:
      Xk=DFT dari sekata syarat WkDFT dari syarat ganjil, X_k = teks{DFT istilah genap} W_k teks cdot{DFT ganjil syarat}, Xk =DFT sekata syarat WkDFT syarat ganjil,
      di mana Wk=e2πik/N W_k = e^{-2pi i cdot k / N} Wk =e−2πi ⋅k/N .
  2. Struktur Rekursif:

    • Setiap saiz DFT NN N dibahagikan kepada dua saiz DFT N/2N/2 N/2 , membawa kepada struktur rekursif.
    • Pembahagian rekursif ini berterusan sehingga kes asas saiz N=1N = 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=u Wkv ,b=uWkv,a' = u W_k cdot v, quad b' = u - W_k cdot v, a=u Wkv,b =u−Wkv,
      di mana uu u dan vv v adalah hasil daripada DFT yang lebih kecil dan WkW_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 NN N pengiraan yang melibatkan punca perpaduan, dan kedalaman rekursi adalah log2(N)log_2(N) log2 (N) .
    • Ini menghasilkan kerumitan masa O(N logN)O(N log N) O(NlogN) .

FFT songsang

  • FFT songsang adalah serupa tetapi digunakan e2πi kn/Ne^{2pi i cdot kn / N} e 2πi⋅kn/N sebagai asas dan skala hasil oleh 1/N1/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 > 1;
    for (; j & bit; bit >>= 1) {
      j ^= bit;
    }
    j ^= bit;
    if (i > 1;
    for (let i = 0; i  {
    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  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 = 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 



<h3>
  
  
  Keluaran
</h3>



<pre class="brush:php;toolbar:false">// 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!

Kenyataan
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Ganti aksara rentetan dalam javascriptGanti aksara rentetan dalam javascriptMar 11, 2025 am 12:07 AM

Penjelasan terperinci mengenai kaedah penggantian rentetan javascript dan Soalan Lazim Artikel ini akan meneroka dua cara untuk menggantikan watak rentetan dalam JavaScript: Kod JavaScript dalaman dan HTML dalaman untuk laman web. Ganti rentetan di dalam kod JavaScript Cara yang paling langsung ialah menggunakan kaedah pengganti (): str = str.replace ("cari", "ganti"); Kaedah ini hanya menggantikan perlawanan pertama. Untuk menggantikan semua perlawanan, gunakan ungkapan biasa dan tambahkan bendera global g: str = str.replace (/fi

Tutorial Persediaan API Carian Google CustomTutorial Persediaan API Carian Google CustomMar 04, 2025 am 01:06 AM

Tutorial ini menunjukkan kepada anda bagaimana untuk mengintegrasikan API carian Google tersuai ke dalam blog atau laman web anda, menawarkan pengalaman carian yang lebih halus daripada fungsi carian tema WordPress standard. Ia menghairankan mudah! Anda akan dapat menyekat carian ke y

Bina Aplikasi Web Ajax anda sendiriBina Aplikasi Web Ajax anda sendiriMar 09, 2025 am 12:11 AM

Jadi di sini anda, bersedia untuk mempelajari semua perkara ini yang dipanggil Ajax. Tetapi, apa sebenarnya? Istilah Ajax merujuk kepada kumpulan teknologi longgar yang digunakan untuk membuat kandungan web yang dinamik dan interaktif. Istilah Ajax, yang asalnya dicipta oleh Jesse J

Contoh warna json failContoh warna json failMar 03, 2025 am 12:35 AM

Siri artikel ini ditulis semula pada pertengahan 2017 dengan maklumat terkini dan contoh segar. Dalam contoh JSON ini, kita akan melihat bagaimana kita dapat menyimpan nilai mudah dalam fail menggunakan format JSON. Menggunakan notasi pasangan nilai utama, kami boleh menyimpan apa-apa jenis

8 plugin susun atur halaman jquery yang menakjubkan8 plugin susun atur halaman jquery yang menakjubkanMar 06, 2025 am 12:48 AM

Leverage JQuery untuk Layouts Laman Web yang mudah: 8 Plugin Essential JQuery memudahkan susun atur laman web dengan ketara. Artikel ini menyoroti lapan plugin jQuery yang kuat yang menyelaraskan proses, terutamanya berguna untuk penciptaan laman web manual

Apa itu ' ini ' Dalam JavaScript?Apa itu ' ini ' Dalam JavaScript?Mar 04, 2025 am 01:15 AM

Mata teras Ini dalam JavaScript biasanya merujuk kepada objek yang "memiliki" kaedah, tetapi ia bergantung kepada bagaimana fungsi dipanggil. Apabila tidak ada objek semasa, ini merujuk kepada objek global. Dalam penyemak imbas web, ia diwakili oleh tetingkap. Apabila memanggil fungsi, ini mengekalkan objek global; tetapi apabila memanggil pembina objek atau mana -mana kaedahnya, ini merujuk kepada contoh objek. Anda boleh mengubah konteks ini menggunakan kaedah seperti panggilan (), memohon (), dan mengikat (). Kaedah ini memanggil fungsi menggunakan nilai dan parameter yang diberikan. JavaScript adalah bahasa pengaturcaraan yang sangat baik. Beberapa tahun yang lalu, ayat ini

Tingkatkan pengetahuan jQuery anda dengan penonton sumberTingkatkan pengetahuan jQuery anda dengan penonton sumberMar 05, 2025 am 12:54 AM

JQuery adalah rangka kerja JavaScript yang hebat. Walau bagaimanapun, seperti mana -mana perpustakaan, kadang -kadang perlu untuk mendapatkan di bawah tudung untuk mengetahui apa yang sedang berlaku. Mungkin kerana anda mengesan bug atau hanya ingin tahu tentang bagaimana jQuery mencapai UI tertentu

10 helaian cheat mudah alih untuk pembangunan mudah alih10 helaian cheat mudah alih untuk pembangunan mudah alihMar 05, 2025 am 12:43 AM

Siaran ini menyusun helaian cheat berguna, panduan rujukan, resipi cepat, dan coretan kod untuk perkembangan aplikasi Android, BlackBerry, dan iPhone. Tiada pemaju harus tanpa mereka! Panduan Rujukan Gesture Touch (PDF) Sumber yang berharga untuk desig

See all articles

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Alat panas

Dreamweaver Mac版

Dreamweaver Mac版

Alat pembangunan web visual

SublimeText3 Linux versi baharu

SublimeText3 Linux versi baharu

SublimeText3 Linux versi terkini

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

SublimeText3 versi Inggeris

SublimeText3 versi Inggeris

Disyorkan: Versi Win, menyokong gesaan kod!

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Persekitaran pembangunan bersepadu PHP yang berkuasa