FFT-loser

14

Angenommen, wir haben n verschiedene ganze Zahlen a1,a2,,an , so dass 0aikn für eine Konstante k>0 und für alle .i

Wir sind daran interessiert, die Anzahl aller möglichen paarweisen Summen . ( i = j ist erlaubt).Sij=ai+aji=j

Ein Algorithmus ist das Polynom zu konstruieren , vom Grad k n und berechnen dessen Quadrat unter Verwendung der Fourier - Transformationsverfahren und die Kräfte mit ihren Koeffizienten in dem resultierenden Polynoms abgelesen. Dies ist ein O ( n log n ) -Zeitalgorithmus.P(x)=j=1nxajknO(nlogn)

Ich habe zwei Fragen:

  • Gibt es einen -Algorithmus, der keine FFT verwendet?O(nlogn)

  • Sind bessere Algorithmen bekannt (dh )? (FFT erlaubt).o(nlogn)

Aryabhata
quelle
Warum ist es wichtig, FFT nicht zu verwenden? Es hört sich so an, als hätten Sie bereits eine gute Lösung für Ihr Problem. Woher kommt die Anforderung, FFT nicht zu verwenden? Das klingt für mich nach einer ziemlich unnatürlichen Forderung.
DW
@DW: Da gibt es dann keine Frage zu stellen? :-) Ich bin nur gespannt, ob es einen anderen Ansatz gibt.
Aryabhata
OK habe es! Ich gebe zu, ich bin auch neugierig. :-) Danke für die interessante Frage.
DW
@ DW: Gern geschehen :-)
Aryabhata

Antworten:

8

Es scheint, dass dieses Problem der Quadratur von Ganzzahlen / Polynomen entspricht:

1. Es ist bekannt, dass die Polynommultiplikation der ganzzahligen Multiplikation entspricht .

2. Offensichtlich haben Sie das Problem bereits auf Polynom / Integer-Quadratur reduziert.Daher ist dieses Problem höchstens so schwer wie das Quadrieren.

Jetzt werde ich die Quadratur von ganzen Zahlen auf dieses Problem reduzieren:

Angenommen, Sie hatten einen Algorithmus:

F(a)P2(x),where P(x)=aiaxai

Dieser Algorithmus ist im Wesentlichen der Algorithmus, den Sie in Ihrer Frage anfordern. Wenn ich also einen magischen Algorithmus hätte, der dies kann, könnte ich eine Funktion erstellen , , die die ganze Zahl y quadriert ( oh ja, ich liebe mathjax: P ):SQUARE(y)y

Algorithm 1 Squaring1.:procedure SQUARE(y):2.:a() a starts as empty polynomial sequence3.:i04.:while y0 do break y down into a polynomial of base 25.:if y & 1 then if lsb of y is set6.:aai append i to a (appending xi)7.:end if8.:ii+19.:yy1 shift y right by one10.:end while11.:P2(x)F(a) obtain the squared polynomial via F(a)12.:return P2(2) simply sum up the polynomial13.:end procedure

Python (test with 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. Thus, squaring is at most as hard as this problem.

4. Therefore, integer squaring is equivalent to this problem. (they are each at most as hard as each-other, due to (2,3,1))

Now it is unknown if integer/polynomial multiplication admits bounds better than O(nlogn); in fact the best multiplication algorithms currently all use FFT and have run-times like O(nlognloglogn) (Schönhage-Strassen algorithm) and O(nlogn2O(logn)) (Fürer's algorithm). Arnold Schönhage and Volker Strassen conjectured a lower bound of Ω(nlogn), and so far this seems to be holding.

This doesn't mean your use of FFT is quicker; O(nlogn) for FFT is the number of operations (I think), not the bit complexity; hence it ignores some factors of smaller multiplications; when used recursively, it would become closer to the FFT multiplication algorithms listed above (see Where is the mistake in this apparently-O(n lg n) multiplication algorithm?).

5. Now, your problem is not exactly multiplication, it is squaring. So is squaring easier? Well, it is an open problem (no for now): squaring is not known to have a faster algorithm than multiplication. If you could find a better algorithm for your problem than using multiplication; then this would likely be a breakthrough.

So as of now, the answer to both your questions is: no, as of now, all the ~O(nlogn) multiplication algorithms use FFT; and as of now squaring is as hard as multiplication. And no, unless a faster algorithm for squaring is found, or multiplication breaks the O(nlogn) barrier, your problem cannot be solved faster than O(nlogn); in fact, it cannot currently be solved in O(nlogn) either, as the best multiplication algorithm only approaches that complexity.

Realz Slaw
quelle