FFT moins algorithme pour les montants par paires

Supposons que l'on nous donne entiers distincts , tels que pour une constante , et pour tout .a 1 , a 2 , … , a n 0 ≤ a i ≤ k n k > 0 $n$$a_1, a_2, \dots, a_n$$0 \le a_i \le kn$$k \gt 0$$i$

Nous souhaitons trouver les dénombrements de toutes les sommes par paire possibles . ( est autorisé). i = $S_{ij} = a_i + a_j$$i = j$

Un algorithme consiste à construire le polynôme de degré , et à calculer son carré en utilisant la méthode de transformée de Fourier et à lire les puissances avec leur coefficients dans le polynôme résultant. Il s'agit d'un algorithme de temps . ≤ k n O ( n log n $P(x) = \sum_{j=1}^{n} x^{a_j}$$\le kn$$O(n \log n)$

J'ai deux questions:

• Existe-t-il un algorithme qui n'utilise pas la FFT?$O(n \log n)$

• De meilleurs algorithmes sont-ils connus (c'est-à-dire )? (FFT autorisé).$o(n \log n)$

Il semblerait que ce problème soit équivalent à la quadrature entière / polynomiale:

1. On sait que la multiplication polynomiale est équivalente à la multiplication entière .

2. De toute évidence, vous avez déjà réduit le problème à la quadrature polynomiale / entière; ce problème est donc tout au plus aussi difficile que la quadrature.

Maintenant, je vais réduire la quadrature entière à ce problème:

Supposons que vous disposiez d'un algorithme:

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

Cet algorithme est essentiellement l'algorithme que vous demandez dans votre question. Ainsi, si j'avais un algorithme magique qui peut le faire, je peux créer une fonction, qui mettra au carré l'entier ( oh oui, j'adore 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 ( test avec 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. Ainsi, la quadrature est au plus aussi difficile que ce problème.

4. Par conséquent, la mise au carré des nombres entiers équivaut à ce problème. (ils sont chacun aussi durs les uns que les autres, en raison de ( 2 , 3 , 1 ))

Maintenant, on ne sait pas si la multiplication entier / polynomial admet mieux les bornes que ; en fait, les meilleurs algorithmes de multiplication utilisent actuellement la FFT et ont des temps d'exécution comme ( algorithme de Schönhage-Strassen ) et ( algorithme de Fürer ). Arnold Schönhage et Volker Strassen ont conjecturé une limite inférieure de , et jusqu'à présent, cela semble tenir.$\mathcal O(n\log n)$$\mathcal O(n \log n \log \log n)$$\mathcal O\left(n \log n\,2^{\mathcal O(\log^* n)}\right)$$\Omega\left(n \log n\right)$

Cela ne signifie pas que votre utilisation de la FFT est plus rapide; pour FFT est le nombre d'opérations (je pense), pas la complexité des bits; il ignore donc certains facteurs de multiplications plus petites; utilisé de manière récursive, il se rapprocherait des algorithmes de multiplication FFT énumérés ci-dessus (voir Où est l'erreur dans cet algorithme de multiplication apparemment O (n lg n)? ).$\mathcal O\left(n\log n\right)$

5. Maintenant, votre problème n'est pas exactement la multiplication, c'est la quadrature. La quadrature est-elle donc plus facile? Eh bien, c'est un problème ouvert (non pour l'instant) : la quadrature n'est pas connue pour avoir un algorithme plus rapide que la multiplication. Si vous pouviez trouver un meilleur algorithme pour votre problème que d'utiliser la multiplication; alors ce serait probablement une percée.

Donc, à partir de maintenant, la réponse à vos deux questions est: non , à partir de maintenant, tous les algorithmes de multiplication ~ utilisent la FFT; et à partir de maintenant la quadrature est aussi difficile que la multiplication. Et non , à moins qu'un algorithme de mise au carré plus rapide ne soit trouvé ou que la multiplication ne brise la barrière , votre problème ne peut pas être résolu plus rapidement que ; en fait, il ne peut pas non plus être résolu actuellement dans , car le meilleur algorithme de multiplication ne se rapproche que de cette complexité.$\mathcal O(n\log n)$$\mathcal O(n\log n)$$\mathcal O(n \log n)$$\mathcal O(n\log n)$