Algoritma integer square root integer presisi sembarang?

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.

Anda dapat menggunakan metode Newton atau salah satu dari sejumlah metode lain untuk menemukan pendekatan ke akar polinomial .$p(x) = x^2 -c$

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(\lg n)$

Setiap iterasi dari metode Newton menghitung

$$x_{j+1} = x_j - (x_j^2 -c)/(2x_j) = 0.5 x_j + \frac{c}{2x_j}.$$

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.$\stackrel{~}{O}(b \lg b)$$b$$\lg \lg b$$b$$\stackrel{~}{O}(n \lg n)$$O(\lg n)$$n$$\stackrel{~}{O}(n (\lg n)^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.xjj$\stackrel{~}{O}(n \lg n)$$x_j$$j$$n$

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 $x$ , iterate:$\frac{1}{\sqrt x}$

$$r_{i+1} = \frac{1}{2} r_i (3 - x r_i^2)$$

Ini sering dinyatakan sebagai:

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

$$w_i = r_i^2$$ $$d_i = 1 - w_i x$$ $$r_{i+1} = r_i + \frac{r_i d_i}{2}$$

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' = 2^{-2e} x$$

di mana kita ingin lebih besar dari, tetapi mendekati, 1 . Jika kita menjalankan algoritma di atas pada x ′ bukannya x , kita menemukan r = $x'$$1$$x'$$x$. Lalu,$r = \frac{1}{\sqrt x'}$.$\sqrt{x} = 2^e r x'$

Sekarang mari kita bagi menjadi mantissa dan eksponen:$r$

$$r_i = 2^{-e_i} r'_i$$

di mana adalah bilangan bulat. Secara intuitif, e i mewakili ketepatan jawaban.$r'_i$$e_i$

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

$$e_{i+1} = 2e_i$$

Dengan sedikit manipulasi, kami menemukan:

w i = r ′ i 2 x ′ i =

$$e_{i+1} = 2e_i$$ $$w_i = {r'_i}^2$$ di=2ei+1-w ′ i x ′ $$x'_i = \frac{x}{2^{2e - e_{i+1}}}$$ r ′ i + 1 =2eir ′ i -r ′ i d $$d_i = 2^{e_{i+1}} - \frac{w_i' x'_i}{2^{e_{i+1}}}$$ $$r'_{i+1} = 2^{e_i} r'_i - \frac{r'_i d_i}{2^{e_i + 1}}$$

Di setiap iterasi:

$$\sqrt{x} \approx \frac{r'_i x}{2^{e + e_i}}$$

Sebagai contoh, mari kita coba menghitung akar kuadrat dari . Kami kebetulan tahu bahwa jawabannya adalah 2 31 $x = 2^{63}$ . Akar kuadrat resiprokal adalah$2^{31}\sqrt{2}$, jadi kita akan menetapkane=31(ini adalah skala masalah) dan untuk tebakan awal kita akan memilihr′0=3dane0=2. (Yaitu, kami memilih$\frac{1}{\sqrt{2}} 2^{-31}$$e = 31$$r'_0 = 3$$e_0 = 2$ untuk estimasi awal kami ke$\frac{3}{4}$ )$\frac{1}{\sqrt{2}}$

Kemudian:

e2=8,r ′ 2 =180e3=16,r ′ 3 =46338e4=32,r ′ 4 =

$$e_1 = 4, r'_1 = 11$$ $$e_2 = 8, r'_2 = 180$$ $$e_3 = 16, r'_3 = 46338$$ $$e_4 = 32, r'_4 = 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:$e_i$$e$$e_i > 2e$

$$\sqrt{2^{63}} \approx \frac{3037000481 \times 2^{63}}{2^{31+32}} = 3037000481$$

$3037000499$$e_i$

Untuk menganalisis kompleksitas metode ini, perhatikan bahwa mengalikan dua $b$$O(b \log b)$$r'_i < 2^{e_i}$$w_i$$e_i$$e_{i+1}$$e_{i+1}$$2e_{i+1}$nomor-bit.

$O(e_i \log e_i)$$O(\log e)$$O(2e \log 2e)$$O(e \log^2 e)$$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.

$\frac{ab}{2^c}$$ab$$c$