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

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

Bagaimana saya membuat dan menerbitkan perpustakaan JavaScript saya sendiri?Bagaimana saya membuat dan menerbitkan perpustakaan JavaScript saya sendiri?Mar 18, 2025 pm 03:12 PM

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

Bagaimanakah saya mengoptimumkan kod JavaScript untuk prestasi dalam penyemak imbas?Bagaimanakah saya mengoptimumkan kod JavaScript untuk prestasi dalam penyemak imbas?Mar 18, 2025 pm 03:14 PM

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

Bagaimanakah saya boleh debug kod javascript dengan berkesan menggunakan alat pemaju pelayar?Bagaimanakah saya boleh debug kod javascript dengan berkesan menggunakan alat pemaju pelayar?Mar 18, 2025 pm 03:16 PM

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

kesan matriks jQuerykesan matriks jQueryMar 10, 2025 am 12:52 AM

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

Cara Membina Slider JQuery MudahCara Membina Slider JQuery MudahMar 11, 2025 am 12:19 AM

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

Cara memuat naik dan memuat turun fail CSV dengan sudutCara memuat naik dan memuat turun fail CSV dengan sudutMar 10, 2025 am 01:01 AM

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

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.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
3 minggu yang laluBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Tetapan grafik terbaik
3 minggu yang laluBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Cara Memperbaiki Audio Jika anda tidak dapat mendengar sesiapa
3 minggu yang laluBy尊渡假赌尊渡假赌尊渡假赌

Alat panas

VSCode Windows 64-bit Muat Turun

VSCode Windows 64-bit Muat Turun

Editor IDE percuma dan berkuasa yang dilancarkan oleh Microsoft

Versi Mac WebStorm

Versi Mac WebStorm

Alat pembangunan JavaScript yang berguna

DVWA

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

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

Muat turun versi mac editor Atom

Editor sumber terbuka yang paling popular