


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
-
Penguraian Transformasi Fourier Diskret (DFT):
- DFT ditakrifkan sebagai:
Xk = n=0∑N−1 xn⋅ e−2πi⋅kn /N,di mana N ialah saiz isyarat input.
- Cooley-Tukey FFT memecahkan pengiraan kepada saiz DFT yang lebih kecil
N/2
dengan mengasingkan istilah diindeks genap dan istilah diindeks ganjil:
Xk = n=0∑N/2−1 x2n ⋅e −2πi⋅(2n)k/N n=0∑N/ 2−1x 2n 1⋅ e−2πi⋅(2n 1)k/N.
- Ini dikurangkan kepada:
Xk =DFT sekata syarat Wk⋅DFT syarat ganjil,di mana Wk =e−2πi ⋅k/N .
- DFT ditakrifkan sebagai:
-
Struktur Rekursif:
- Setiap saiz DFT N dibahagikan kepada dua saiz DFT N/2 , membawa kepada struktur rekursif.
- Pembahagian rekursif ini berterusan sehingga kes asas saiz N=1 , di mana DFT hanyalah nilai input.
-
Operasi Rama-rama:
- Algoritma menggabungkan hasil daripada DFT yang lebih kecil menggunakan operasi rama-rama:
a′=u Wk⋅v,b′ =u−Wk⋅v,di mana u dan v adalah hasil daripada DFT yang lebih kecil dan Wk mewakili akar perpaduan.
- Algoritma menggabungkan hasil daripada DFT yang lebih kecil menggunakan operasi rama-rama:
-
Permutasi Pembalikan Bit:
- Susun atur input disusun semula berdasarkan perwakilan binari indeks untuk membolehkan pengiraan di tempat.
-
Kerumitan Masa:
- Pada setiap peringkat rekursi, terdapat N pengiraan yang melibatkan punca perpaduan, dan kedalaman rekursi adalah log2 (N) .
- Ini menghasilkan kerumitan masa O(NlogN) .
FFT songsang
- FFT songsang adalah serupa tetapi digunakan e 2πi⋅kn/N sebagai asas dan skala hasil oleh 1/N .
Memahami Algoritma Pendaraban FFT
Algoritma pendaraban FFT berfungsi melalui beberapa langkah utama:
-
Praproses Nombor
- Tukar nombor input kepada tatasusunan digit
- Kendalikan kedua-dua bahagian integer dan perpuluhan
- Pad tatasusunan kepada kuasa terdekat 2 untuk pengiraan FFT
-
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
-
Pendaraban Domain Kekerapan
- Lakukan pendaraban mengikut unsur bagi tatasusunan yang diubah
- Gunakan operasi nombor kompleks untuk pengiraan yang cekap
-
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!

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

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

Artikel membincangkan membuat, menerbitkan, dan mengekalkan perpustakaan JavaScript, memberi tumpuan kepada perancangan, pembangunan, ujian, dokumentasi, dan strategi promosi.

Artikel ini membincangkan strategi untuk mengoptimumkan prestasi JavaScript dalam pelayar, memberi tumpuan kepada mengurangkan masa pelaksanaan dan meminimumkan kesan pada kelajuan beban halaman.

Artikel ini membincangkan debugging JavaScript yang berkesan menggunakan alat pemaju pelayar, memberi tumpuan kepada menetapkan titik putus, menggunakan konsol, dan menganalisis prestasi.

Bawa kesan filem matriks ke halaman anda! Ini adalah plugin jQuery yang sejuk berdasarkan filem terkenal "The Matrix". Plugin mensimulasikan kesan aksara hijau klasik dalam filem, dan hanya pilih gambar dan plugin akan mengubahnya menjadi gambar gaya matriks yang diisi dengan aksara angka. Datang dan cuba, sangat menarik! Bagaimana ia berfungsi Plugin memuat imej ke kanvas dan membaca nilai piksel dan warna: data = ctx.getimagedata (x, y, settings.grainsize, settings.grainsize) .data Plugin dengan bijak membaca kawasan segi empat tepat gambar dan menggunakan jQuery untuk mengira warna purata setiap kawasan. Kemudian, gunakan

Artikel ini akan membimbing anda untuk membuat karusel gambar mudah menggunakan perpustakaan jQuery. Kami akan menggunakan perpustakaan BXSlider, yang dibina di atas jQuery dan menyediakan banyak pilihan konfigurasi untuk menubuhkan karusel. Pada masa kini, Gambar Carousel telah menjadi ciri yang mesti ada di laman web - satu gambar lebih baik daripada seribu perkataan! Selepas membuat keputusan untuk menggunakan karusel gambar, soalan seterusnya adalah bagaimana untuk menciptanya. Pertama, anda perlu mengumpul gambar-gambar resolusi tinggi yang berkualiti tinggi. Seterusnya, anda perlu membuat karusel gambar menggunakan HTML dan beberapa kod JavaScript. Terdapat banyak perpustakaan di web yang dapat membantu anda membuat karusel dengan cara yang berbeza. Kami akan menggunakan Perpustakaan BXSlider Sumber Terbuka. Perpustakaan BXSlider menyokong reka bentuk responsif, jadi karusel yang dibina dengan perpustakaan ini dapat disesuaikan dengan mana -mana

Set data sangat penting dalam membina model API dan pelbagai proses perniagaan. Inilah sebabnya mengapa mengimport dan mengeksport CSV adalah fungsi yang sering diperlukan. Dalam tutorial ini, anda akan belajar cara memuat turun dan mengimport fail CSV dalam sudut


Alat AI Hot

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool
Gambar buka pakaian secara percuma

Clothoff.io
Penyingkiran pakaian AI

AI Hentai Generator
Menjana ai hentai secara percuma.

Artikel Panas

Alat panas

VSCode Windows 64-bit Muat Turun
Editor IDE percuma dan berkuasa yang dilancarkan oleh Microsoft

Versi Mac WebStorm
Alat pembangunan JavaScript yang berguna

DVWA
Damn Vulnerable Web App (DVWA) ialah aplikasi web PHP/MySQL yang sangat terdedah. Matlamat utamanya adalah untuk menjadi bantuan bagi profesional keselamatan untuk menguji kemahiran dan alatan mereka dalam persekitaran undang-undang, untuk membantu pembangun web lebih memahami proses mengamankan aplikasi web, dan untuk membantu guru/pelajar mengajar/belajar dalam persekitaran bilik darjah Aplikasi web keselamatan. Matlamat DVWA adalah untuk mempraktikkan beberapa kelemahan web yang paling biasa melalui antara muka yang mudah dan mudah, dengan pelbagai tahap kesukaran. Sila ambil perhatian bahawa perisian ini

SecLists
SecLists ialah rakan penguji keselamatan muktamad. Ia ialah koleksi pelbagai jenis senarai yang kerap digunakan semasa penilaian keselamatan, semuanya di satu tempat. SecLists membantu menjadikan ujian keselamatan lebih cekap dan produktif dengan menyediakan semua senarai yang mungkin diperlukan oleh penguji keselamatan dengan mudah. Jenis senarai termasuk nama pengguna, kata laluan, URL, muatan kabur, corak data sensitif, cangkerang web dan banyak lagi. Penguji hanya boleh menarik repositori ini ke mesin ujian baharu dan dia akan mempunyai akses kepada setiap jenis senarai yang dia perlukan.

Muat turun versi mac editor Atom
Editor sumber terbuka yang paling popular