Algoritma FFT-less untuk jumlah berpasangan

14

Misalkan kita diberi bilangan bulat yang berbeda , sehingga untuk beberapa konstanta , dan untuk semua .a 1 , a 2 , , a n 0 a iknSebuah1,Sebuah2,...,Sebuahnk > 00Sebuahsayaknk>0saya

Kami tertarik untuk menemukan jumlah semua kemungkinan jumlah berpasangan . ( diizinkan).Ssayaj=Sebuahsaya+Sebuahji=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 nP(x)=j=1nxajknO(nlogn)

Saya punya dua pertanyaan:

  • Apakah ada algoritma yang tidak menggunakan FFT?O(nlogn)

  • Apakah algoritma yang lebih baik diketahui (yaitu )? (FFT diizinkan).o(nlogn)

Aryabhata
sumber
Mengapa penting untuk tidak menggunakan FFT? Sepertinya Anda sudah memiliki solusi yang bagus untuk masalah Anda. Dari mana datangnya persyaratan untuk tidak menggunakan FFT? Bagi saya itu kedengarannya seperti persyaratan yang agak tidak wajar untuk diterapkan.
DW
@ WD: Karena dengan begitu tidak akan ada pertanyaan untuk ditanyakan? :-) Saya hanya ingin tahu apakah ada pendekatan yang berbeda.
Aryabhata
OK mengerti! Saya akui saya juga penasaran. :-) Terima kasih atas pertanyaan yang menarik.
DW
@DW: Sama-sama :-)
Aryabhata

Jawaban:

8

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(Sebuah)P2(x),dimana P(x)=SebuahsayaSebuahxSebuahsaya

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 ):SQUSEBUAHRE(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 ( 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 nO(nlogn)O(nlognloglogn) (Algoritma Fürer's). Arnold Schönhage dan Volker Strassen menduga batas bawahΩ ( n log n ) , dan sejauh ini tampaknya masih berlaku.O(nlogn2O(logn))Ω(nlogn)

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? ).O(nlogn)

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.

O(nlogn)O(nlogn)O(nlogn)O(nlogn) baik, karena algoritma multiplikasi terbaik hanya mendekati kompleksitas itu.

Realz Slaw
sumber