Algoritma FFT-less untuk jumlah berpasangan

Misalkan kita diberi bilangan bulat yang berbeda , sehingga untuk beberapa konstanta , dan untuk semua .a 1 , a 2 , … , a n 0 ≤ a i ≤ $n$$a_1, a_2, \dots, a_n$k > $0 \le a_i \le kn$$k \gt 0$$i$

Kami tertarik untuk menemukan jumlah semua kemungkinan jumlah berpasangan . ( diizinkan).$S_{ij} = a_i + a_j$$i = j$

Salah satu algoritma adalah untuk membangun polinomial derajat , dan menghitung kuadratnya menggunakan metode transformasi Fourier dan membaca kekuatan dengan mereka koefisien dalam polinomial yang dihasilkan. Ini adalah algoritma waktu . ≤ k $P(x) = \sum_{j=1}^{n} x^{a_j}$$\le kn$$O(n \log n)$

Saya punya dua pertanyaan:

• Apakah ada algoritma yang tidak menggunakan FFT?$O(n \log n)$

• Apakah algoritma yang lebih baik diketahui (yaitu )? (FFT diizinkan).$o(n \log n)$

Tampaknya masalah ini setara dengan bilangan bulat / polinomial:

1. Diketahui bahwa perkalian polinomial sama dengan perkalian bilangan bulat .

2. Jelas, Anda sudah mengurangi masalah menjadi polinomial / bilangan bulat kuadrat; oleh karena itu masalah ini paling sulit seperti kuadrat.

Sekarang saya akan mengurangi bilangan bulat kuadrat untuk masalah ini:

Misalkan Anda memiliki algoritma:

$$F(\mathbf{\vec a})\rightarrow P^2(x),\\ \text{where } P(x)=\sum_{a_i \in \mathbf{\vec a}} x^{a_i}$$

Algoritma ini pada dasarnya adalah algoritma yang Anda minta dalam pertanyaan Anda. Jadi, jika saya memiliki algoritma ajaib yang dapat melakukan ini, saya dapat membuat suatu fungsi, yang akan mengkuadratkan bilangan bulat y ( oh ya, saya memang suka mathjax: P ):${\rm S{\small QUARE}}\left(y\right)$$y$

$$\begin{array}{rlr}\hline &\mathbf{\text{Algorithm 1}} \text{ Squaring}&\hspace{2em}&\\ \hline {\tiny 1.:}&\mathbf {\text{procedure }} {\rm S{\small QUARE}}\left(y\right):\\ {\tiny 2.:}&\hspace{2em}\mathbf {\vec a} \leftarrow () &&\triangleright~\mathbf {\vec a}\text{ starts as empty polynomial sequence}\\ {\tiny 3.:}&\hspace{2em}i \leftarrow 0\\ {\tiny 4.:}&\hspace{2em}\mathbf{while}~y\ne0~\mathbf{do} &&\triangleright~\text{break }y\text{ down into a polynomial of base }2\\ {\tiny 5.:}&\hspace{4em}\mathbf{if}~y~\&~1~\mathbf{then} &&\triangleright~\text{if lsb of }y\text{ is set}\\ {\tiny 6.:}&\hspace{6em}\mathbf{\vec a} \leftarrow \mathbf{\vec a}i &&\triangleright~\text{append }i\text{ to }\mathbf{\vec a}~\text{(appending }x^i\text{)}\\ {\tiny 7.:}&\hspace{4em}\mathbf{end~if}\\ {\tiny 8.:}&\hspace{4em}i \leftarrow i + 1\\ {\tiny 9.:}&\hspace{4em}y \leftarrow y \gg 1 &&\triangleright~\text{shift }y\text{ right by one}\\ {\tiny 10.:}&\hspace{2em}\mathbf{end~while}\\ {\tiny 11.:}&\hspace{2em}P^2(x) \leftarrow F\left(\mathbf{\vec a}\right) &&\triangleright~\text{obtain the squared polynomial via } F\left(\mathbf{\vec a}\right)\\ {\tiny 12.:}&\hspace{2em}\mathbf{return}~P^2(2) &&\triangleright~\text{simply sum up the polynomial}\\ {\tiny 13.:}&\mathbf {\text{end procedure}}\\ \hline &\end{array}$$

Python ( uji dengan codepad ):

#/cs//q/11418/2755

def F(a):
    n = len(a)
    for i in range(n):
        assert a[i] >= 0

    # (r) => coefficient
    # coefficient \cdot x^{r}
    S = {}
    for ai in a:
        for aj in a:
            r = ai + aj

            if r not in S:
                S[r] = 0

            S[r] += 1

    return list(S.items())

def SQUARE(x):
    x = int(x)

    a = []
    i = 0
    while x != 0:
        if x & 1 == 1:
            a += [i]
        x >>= 1
        i += 1

    print 'a:',a
    P2 = F(a)

    print 'P^2:',P2

    s = 0
    for e,c in P2:
        s += (1 << e)*c
    return s

3. Jadi, mengkuadratkan paling keras seperti masalah ini.

4. Oleh karena itu, bilangan bulat integer setara dengan masalah ini. (mereka masing-masing paling keras seperti satu sama lain, karena ( 2 , 3 , 1 ))

Sekarang tidak diketahui apakah bilangan bulat / polinomial mengakui batas lebih baik daripada ; sebenarnya algoritma multiplikasi terbaik saat ini semuanya menggunakan FFT dan memiliki waktu-berjalan seperti O ( n log n log log n ) ( Algoritma Schönhage-Strassen ) dan O ( n log $\mathcal O(n\log n)$$\mathcal O(n \log n \log \log n)$ (Algoritma Fürer's). Arnold Schönhage dan Volker Strassen menduga batas bawahΩ ( n log n ) , dan sejauh ini tampaknya masih berlaku.$\mathcal O\left(n \log n\,2^{\mathcal O(\log^* n)}\right)$$\Omega\left(n \log n\right)$

Ini tidak berarti penggunaan FFT Anda lebih cepat; untuk FFT adalah jumlah operasi (saya pikir), bukan kompleksitas bit; karenanya ia mengabaikan beberapa faktor perkalian yang lebih kecil; ketika digunakan secara rekursif, itu akan menjadi lebih dekat dengan algoritma multiplikasi FFT yang tercantum di atas (lihat Di mana kesalahan dalam algoritma multiplikasi yang tampaknya-O (n lg n) ini? ).$\mathcal O\left(n\log n\right)$

5. Sekarang, masalah Anda bukan multiplikasi, melainkan kuadrat. Jadi, apakah mengkuadratkan lebih mudah? Yah, ini adalah masalah terbuka (tidak untuk saat ini) : kuadrat tidak diketahui memiliki algoritma yang lebih cepat daripada perkalian. Jika Anda bisa menemukan algoritma yang lebih baik untuk masalah Anda daripada menggunakan perkalian; maka ini kemungkinan akan menjadi terobosan.

$\mathcal O(n\log n)$$\mathcal O(n\log n)$$\mathcal O(n \log n)$$\mathcal O(n\log n)$ baik, karena algoritma multiplikasi terbaik hanya mendekati kompleksitas itu.