Algoritma integer square root integer presisi sembarang?

9

Apakah ada algoritma subquadratic yang diketahui untuk menghitung lantai akar kuadrat dari ninteger bit?

Algoritma naif akan menjadi sesuatu seperti

def sqrt(x):
    r = 0
    i = x.bit_length() // 2
    while i >= 0:
        inc = (r << (i+1)) + (1 << (i*2))
        if inc <= x:
            x -= inc
            r += 1 << i
        i -= 1
    return r

Ini membutuhkan O(n)iterasi, masing-masing melibatkan penambahan yang merupakan O(n)waktu, jadi ini adalah O(n^2)waktu keseluruhan. Adakah yang lebih cepat? Saya tahu bahwa untuk kasus perkalian ada algoritma khusus yang melakukan lebih baik daripada waktu kuadratik, tetapi saya tidak dapat menemukan apa pun untuk akar kuadrat.

Antimon
sumber
Jawaban saya untuk sesuatu yang terkait mungkin membantu cs.stackexchange.com/a/37338/12052 . Satu-satunya masalah adalah, bagian dari persamaan yang diperlukan Anda perlu menemukan secara empiris untuk menyesuaikan akurasinya.
Francesco Gramano
@ FrancescoGramano: Maaf, saya rasa itu tidak membantu.
Aryabhata
btw, apakah persyaratan sub-kuadrat ini merupakan masalah yang lebih besar? Karena perbedaan antara sub-kuadratik kuadratik dan rumit mungkin tidak begitu besar dalam praktiknya. Atau itu hanya kepentingan teoretis?
Aryabhata
@Aryabhata Maaf saya tidak melihat komentar Anda sebelumnya. Tidak, itu bukan bagian dari masalah yang lebih besar, hanya rasa ingin tahu.
Antimony

Jawaban:

5

Anda dapat menggunakan metode Newton atau salah satu dari sejumlah metode lain untuk menemukan pendekatan ke akar polinomial .p(x)=x2c

Tingkat konvergensi untuk metode Newton akan kuadrat, yang berarti bahwa jumlah bit yang benar berlipat ganda di setiap iterasi. Ini berarti iterasi metode Newton sudah cukup.O(lgn)

Setiap iterasi dari metode Newton menghitung

xj+1=xj(xj2c)/(2xj)=0.5xj+c2xj.

Kompleksitas bit dari perkalian adalah O ( b lg b ) , untuk mengalikan dua b- bit integer (mengabaikan faktor lg lg b ). Kompleksitas bit untuk pembagian (ke b bit presisi) adalah sama. Oleh karena itu, setiap iterasi dapat dihitung dalam . Mengalikan dengan iterasi , kami menemukan bahwa keseluruhan waktu berjalan untuk menghitung akar kuadrat menjadi bit presisi adalah . Ini sub-kuadratik.O (blgb)blglgbbO (nlgn)O(lgn)nO (n(lgn)2)

Saya pikir analisis yang lebih cermat menunjukkan bahwa ini dapat ditingkatkan menjadi waktu berjalan (dengan mempertimbangkan bahwa kita hanya perlu mengetahui setiap untuk mengetahui tentang bit presisi, daripada bit presisi). Namun, bahkan analisis yang lebih mendasar sudah menunjukkan waktu berjalan yang jelas subquadratic.xjjnO (nlgn)xjjn

DW
sumber
Dalam satu biner juga memiliki dugaan awal yang besar menggunakan identitas . Alih-alih menghitung log, seseorang dapat memperkirakan log 2 x sebagai jumlah digit dalam x . Misalnya, log 2 101011 6 . x1/2=21/2log2xlog2xxlog21010116
Nick Alger
@ WD: Tapi bukankah kita mencari akar kuadrat integer? Jika Anda melakukan iterasi metode newton hanya menggunakan bilangan bulat aritmatika, maka kita perlu beberapa pembenaran tambahan untuk klaim , bukan? Kalau tidak, kita mengasumsikan presisi yang cukup besar sudah ... Maaf jika saya kehilangan sesuatu yang jelas. O(logn)
Aryabhata
@DW: "Tingkat konvergensi untuk metode Newton" tidak akan kuadrat jika , dan saya tidak tahu apa yang terjadi untuk nilai yang bukan real-negatif. Perkiraan Anda untuk kompleksitas penggandaan bit lebih ketat dari yang disarankan komentar Anda berikut . Juga, kita "perlu mengetahui masing-masing untuk mengetahui tentang" "bit of precision". cc=0c2xj2j
@Aryabhata:Kami tidak cukup "mencari akar kuadrat integer"; kami sedang mencari "lantai akar kuadrat". Anda benar tentang masalah aritmatika integer, meskipun kompleksitas bit yang sama berlaku untuk operasi floating-point.
1
@ RickyDemer, ya, adalah kasus khusus, karena kemudian akar memiliki multiplisitas 2, tetapi ketika , root memiliki multiplisitas 1 sehingga metode Newton memang memiliki konvergensi kuadratik. Saya berasumsi tidak ada yang akan menggunakan metode Newton untuk menghitung akar kuadrat dari (karena akar kuadrat dari nol jelas nol). Jadi, apa yang ingin Anda katakan? Apakah komentar Anda adalah komentar sepele yang ditujukan dengan menambahkan sesuatu ke jawaban saya yang mengatakan "kasus khusus akar kuadrat dari nol", atau ada sesuatu yang lebih dalam di sini yang saya lewatkan? p ( x ) c > 0 c = 0c=0p(x)c>0c=0
DW
6

Salah satu masalah dengan metode Newton adalah bahwa ia membutuhkan operasi divisi di setiap iterasi, yang merupakan operasi integer dasar paling lambat.

Metode Newton untuk akar kuadrat resiprokal tidak. Jika adalah angka yang ingin Anda temukan 1x , iterate:1x

ri+1=12ri(3xri2)

Ini sering dinyatakan sebagai:

d i = 1 - w i x r i + 1 = r i + r i d i

wi=ri2
di=1wix
ri+1=ri+ridi2

Itu tiga operasi multiplikasi. Pembagian dengan dua dapat diimplementasikan sebagai shift-right.

Sekarang masalahnya adalah bahwa bukan bilangan bulat. Namun, Anda dapat memanipulasinya dengan menerapkan floating-point secara manual, dan melakukan banyak operasi shift untuk mengkompensasi bila perlu.r

Pertama, mari kita skala ulang :x

x=22ex

di mana kita ingin lebih besar dari, tetapi mendekati, 1 . Jika kita menjalankan algoritma di atas pada x bukannya x , kita menemukan r = 1x1xx. Lalu,r=1x.x=2erx

Sekarang mari kita bagi menjadi mantissa dan eksponen:r

ri=2eiri

di mana adalah bilangan bulat. Secara intuitif, e i mewakili ketepatan jawaban.riei

Kita tahu bahwa metode Newton secara kasar menggandakan jumlah digit signifikan yang akurat. Jadi kita dapat memilih:

ei+1=2ei

Dengan sedikit manipulasi, kami menemukan:

w i = r i 2 x i = x

ei+1=2ei
wi=ri2
di=2ei+1-wi xi
xi=x22eei+1
ri + 1 =2eiri -ri di
di=2ei+1wixi2ei+1
ri+1=2eiriridi2ei+1

Di setiap iterasi:

xrix2e+ei

Sebagai contoh, mari kita coba menghitung akar kuadrat dari . Kami kebetulan tahu bahwa jawabannya adalah 2 31 x=263 . Akar kuadrat resiprokal adalah 12312, jadi kita akan menetapkane=31(ini adalah skala masalah) dan untuk tebakan awal kita akan memilihr0=3dane0=2. (Yaitu, kami memilih312231e=31r0=3e0=2 untuk estimasi awal kami ke134 )12

Kemudian:

e2=8,r2 =180e3=16,r3 =46338e4=32,r4 =3037000481

e1=4,r1=11
e2=8,r2=180
e3=16,r3=46338
e4=32,r4=3037000481

Kita bisa mengetahui kapan harus berhenti iterasi dengan membandingkan ke e ; jika saya telah menghitung dengan benar, e i > 2 e harus cukup baik. Kami akan berhenti di sini, dan menemukan:eieei>2e

2633037000481×263231+32=3037000481

3037000499ei

Untuk menganalisis kompleksitas metode ini, perhatikan bahwa mengalikan dua bO(blogb)ri<2eiwieiei+1ei+12ei+1nomor-bit.

O(eilogei)O(loge)O(2elog2e)O(elog2e)x

Namun, analisis ini menyembunyikan prinsip penting yang harus diingat oleh semua orang yang bekerja dengan bilangan bulat besar: karena perkalian adalah superlinear dalam jumlah bit, setiap operasi penggandaan hanya boleh dilakukan pada bilangan bulat yang kira-kira besarnya presisi saat ini (dan , Saya dapat menambahkan, Anda harus mencoba untuk mengalikan angka-angka yang memiliki urutan yang sama besarnya). Menggunakan bilangan bulat lebih besar dari itu adalah usaha yang sia-sia. Faktor konstan penting, dan untuk bilangan bulat besar, mereka penting.

ab2cabc

Nama samaran
sumber
Ini barang bagus. Namun satu komentar: Bukankah kompleksitas bit dari pembelahan asimtotis kira-kira sama dengan kompleksitas bit dari perkalian? Jadi, Anda berbicara tentang sesuatu yang memberikan peningkatan faktor konstan, bukan peningkatan asimptotik, bukan? Itu tidak sepenuhnya jelas dari jawaban Anda.
DW
bO(blgb)O(blgb(lglgb)O(1))
1
@DW: bO(blogb)Kata "bit" hanya muncul sekali di situ; kalau tidak, saya sudah menunjukkan itu.
Ini adalah faktor faktor konstan, ya. Algoritma pembagian integer besar terbaik menggunakan teknik yang sangat mirip dengan algoritma keseluruhan, seperti iterasi Newton-Raphson dan menggandakan presisi efektif pada setiap iterasi. Sebuah loop Newton-Raphson di dalam loop Newton-Raphson menumpuk pada faktor-faktor konstan! Ricky Demer benar; Saya sedang berpikir dalam model RAM kata. Saya mungkin harus menyebutkan ini.
Nama samaran