Perkalian dalam

10

Saya mencari di sini , dan saya melihat runtime terbaik untuk perkalian dua angka bit adalah , tetapi saya dapat dengan mudah melihat algoritma yang berjalan di . $n$ $O(n\cdot \log n \cdot 2^{O(\log^* n)}$ $O(n\cdot \log n)$

Bagaimanapun, kita tahu bagaimana mengalikan dua polinomial dari derajat di runtime . Tetapi mengalikan polinomial sama dengan mengalikan dua angka bit. Jadi kami memiliki algoritma untuk mengalikan dua angka bit di . Sekarang satu-satunya masalah yang mungkin terjadi adalah carry, tetapi dalam setiap fase kita dapat memperbaikinya dalam waktu , cukup dengan menggeser bit yang paling kanan dan tetangga kiri, sampai akhir. Artinya, runtime kami akan tetap . $n$ $O(n \log n)$ $n$ $n$ $O(n \log n )$ $O(n)$ $O(n \cdot \log n)$

Jadi, apakah saya membuat penemuan baru (dan cukup jelas)? Atau apakah halaman wikipedia sudah ketinggalan zaman? Atau mungkin saya punya kesalahan?

runtime-analysis TheEmeritus
sumber

Apa cara "kita tahu" "untuk melipatgandakan dua polinomial dari derajat di runtime "?

n

$n$

O (n \log n)

$O(n \log n)$

$\hspace{.46 in}$

8

Seperti yang ditunjukkan oleh @DavidRicherby, kebingungan muncul karena berbagai ukuran kompleksitas semakin tercampur. Tapi saya akan sedikit menguraikan.

Biasanya, ketika mempelajari algoritma untuk perkalian polinomial atas cincin arbitrer, orang tertarik pada jumlah operasi aritmatika dalam cincin yang digunakan algoritma. Secara khusus, mengingat beberapa (komutatif, kesatuan) cincin , dan dua polinomial dengan derajat kurang dari , algoritma Schönhage-Strassen membutuhkan perkalian dan penambahan dalam untuk menghitung oleh, kira-kira, berdampingan akar primitif ke- ke untuk mendapatkan cincin lebih besar dari dan kemudian, menggunakan Fast Fourier Transform over $R$ $f,g \in R[X]$ $n$ $O(n \log{n} \log{\log{n}})$ $R$ $fg \in R[X]$ $n$ $R$ $D \supset R$ $D$ , Komputasi produk di . $D$

Jika cincin Anda berisi akar -th kesatuan, maka ini bisa melesat hingga operasi di dengan menggunakan Fast Fourier Transform langsung di atas . Lebih khusus, lebih dari , Anda dapat melakukan ini menggunakan operasi dering (mengabaikan fakta bahwa ini akan memerlukan aritmatika yang tepat atas angka-angka kompleks). $n$ $O(n \log n)$ $R$ $R$ $\mathbb{Z} \subset \mathbb{C}$ $O(n \log n)$

Ukuran lain yang dapat diperhitungkan adalah kompleksitas bit operasi. Dan inilah yang kami tertarik ketika mengalikan dua bilangan bulat dari panjang bit . Di sini, operasi primitif mengalikan dan menambahkan dua digit (dengan carry). Jadi, ketika mengalikan dua polinomial lebih dari , Anda sebenarnya perlu memperhitungkan fakta bahwa angka yang muncul selama perhitungan tidak dapat dikalikan menggunakan jumlah konstan operasi primitif. Ini dan fakta bahwa tidak memiliki th akar primitif persatuan untuk mencegah Anda dari Appling algoritma. Anda mengatasinya dengan mempertimbangkan $n$ $\mathbb{Z}$ $\mathbb{Z}$ $n$ $n > 2$ $O(n \log n)$ $f,g$ dengan koefisien dari ring , karena koefisien polinomial produk tidak akan melebihi batas ini. Di sana (ketika adalah kekuatan dua), Anda memiliki (kelas kongruensi) sebagai akar ke- persatuan, dan dengan memanggil algoritme secara acak untuk penggandaan koefisien, Anda dapat mencapai total ) operasi primitif (yaitu, bit). Ini kemudian dibawa ke perkalian integer. $\mathbb{Z}/\langle 2^n + 1 \rangle$ $n$ $2$ $n$ $O(n \log n \log \log n)$

Untuk contoh yang menyoroti pentingnya perbedaan antara operasi cincin dan operasi primitif, pertimbangkan dua metode untuk mengevaluasi polinomial: metode Horner dan metode Estrin. Metode Horner mengevaluasi polinomial di beberapa dengan mengeksploitasi identitas sementara metode Estrin membagi menjadi dua bagian dan yaitu, berisi ketentuan derajat dan persyaratan derajat $f = \sum_{i=0}^n f_i X^i$ $x \in \mathbb{Z}$

f (x) = (\dots (f_{n} x + f_{n - 1}) x + \dots + \dots) + f_{0}

$f(x) = (\ldots (f_n x + f_{n-1})x + \ldots + \ldots) + f_0$

f

$f$

H = \sum_{i = 1}^{n / 2} f_{n / 2 + i} X^{i}

$H = \sum_{i=1}^{n/2} f_{n/2+i} X^i$

L = \sum_{i = 0}^{n / 2} f_{i} X^{i}

$L = \sum_{i=0}^{n/2} f_{i} X^i$

H

$H$

> n / 2

$>n/2$

L

$L$

\leq n / 2

$\leq n/2$ (anggap adalah kekuatan dua, untuk kesederhanaan).

n

$n$

Kemudian, kita dapat menghitung menggunakan dan menerapkan algoritma secara rekursif. $f(x)$

f (x) = H (x) x^{n / 2} + L (x)

$f(x) = H(x)x^{n/2} + L(x)$

Yang pertama, menggunakan penambahan dan perkalian, terbukti optimal dengan jumlah penambahan dan perkalian (yaitu, operasi cincin), yang terakhir membutuhkan lebih banyak (setidaknya ). $n$ $n + \log n$

Tetapi, pada tingkat operasi bit, seseorang dapat (dengan mudah) menunjukkan bahwa dalam kasus terburuk, metode Horner melakukan penggandaan jumlah ukuran setidaknya , yang mengarah ke banyak bit operasi (ini berlaku bahkan jika kita mengasumsikan bahwa dua angka bit dapat dikalikan dalam waktu ), sedangkan skema Estrin menggunakan operasi untuk beberapa , yang sejauh ini, secara asimptotik lebih cepat. $n/2$ $n/2$ $\Omega(n^2)$ $n$ $O(n)$ $O(n \log^c n) = \tilde{O}(n)$ $c > 0$

Cornelius Brand
sumber

9

Mengatakan bahwa Anda dapat mengalikan dua polinomial derajat dalam waktu menyiratkan bahwa, khususnya, Anda dapat melipatgandakan polinomial derajat-nol, yaitu konstanta, dalam waktu konstan. Jelas, oleh karena itu, klaim "mengalikan angka-angka membutuhkan waktu " dan "mengalikan derajat- polinomial membutuhkan waktu " relatif untuk model komputasi yang berbeda sehingga tidak dapat dibandingkan secara langsung. $n$ $O(n\log n)$ $n$ $O(2^{\log^*n}n\log n)$ $n$ $O(n\log n)$

David Richerby
sumber

5

Saya tidak berpikir ini masalahnya. Jika kita menganggap angka sebagai polinomial yang "x" -nya adalah basis, misalnya 2, maka biasanya kita dapat mengalikan polinomial derajat-nol (angka lebih kecil dari basis) dalam waktu konstan. Saya kira masalahnya adalah bahwa algoritma O (n * log n) menggunakan FFT dan angka asimptotik yang lebih besar dapat muncul di dalam algoritma FFT.

jkff

Perkalian dalam

Jawaban: