


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

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

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

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

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

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

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

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


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

Dreamweaver Mac版
Alat pembangunan web visual

SublimeText3 Linux versi baharu
SublimeText3 Linux versi terkini

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

SublimeText3 versi Inggeris
Disyorkan: Versi Win, menyokong gesaan kod!

ZendStudio 13.5.1 Mac
Persekitaran pembangunan bersepadu PHP yang berkuasa
