Hitung root kuadrat menggunakan penambahan (bit) dan bergeser sebagai primitif

8

Pertanyaan: Diberi alami bit , bagaimana cara menghitung hanya menggunakan penambahan dan pergeseran (bit)?nNNO(n)

Kiatnya adalah menggunakan pencarian biner. Namun, saya tidak dapat mencapai kompleksitas yang diperlukan (saya mendapat ).O(n2)


Apa yang dimaksud dengan using only $O(n)$ (bit) additions and shifts:

Ini adalah latihan dalam buku algoritma.
Menurut pendapat saya, itu berarti menambahkan dua, katakanlah bit, bilangan alami biaya dan menggeser, katakanlah bit, bilangan alami juga biaya . Maka kita hanya diperbolehkan menggunakan operasi kali. Tidak disebutkan biaya perbandingan. Saya kira kita dapat mengabaikannya atau berasumsi bahwa membandingkan dua, katakanlah bit, bilangan alami juga berharga .nO(1)nO(1)O(1)O(n)
nO(1)


Saya algoritmaO(n2) :

  1. Tentukan kisaran jumlah bit dari : Oleh karena itu, t_1 \ triangleq \ lfloor \ frac {n-1} {2} \ rfloor + 1 \ le t \ le \ lceil \ frac {n} {2} \ rceil + 1 \ triangleq t_2.tN
    2n12N2n22n12N2n2
    t1n12+1tn2+1t2.
  2. Pencarian biner: Temukan N antara 2t1 dan 2t2 menggunakan pencarian biner. Untuk setiap nomor x , untuk menghitung x2 menggunakan penambahan dan pergeseran sebagai primitif dan membandingkannya dengan N .

Kompleksitasnya adalah untuk kali pencarian biner dan komputasi , yang masing-masing membutuhkan penambahan dan pergeseran.O(n×n)=O(n2)O(n)x2O(n)

Hengxin
sumber

Jawaban:

7

Algoritma iteratif sepertinya harus bekerja.

Biarkan . Misalkan kita tahu bahwa adalah pendekatan bilangan bulat ke , yaitu , dan anggaplah kita tahu nilai (diperoleh sebelumnya).M=N/4xMx=Mx2

Sekarang kita ingin menemukan . Apa nilai yang mungkin dari ? Saya cukup yakin satu-satunya nilai yang mungkin adalah atau . Dan, mudah untuk mencoba keduanya dan melihat mana yang benar. Secara khusus, untuk , kita memiliki , yang dapat diperoleh dari dengan dua shift kiri ( waktu); untuk , kita memiliki , yang dapat diperoleh dari dan dengan empat shift kiri dan dua tambahan ( waktu). Sekarang, bandingkan saja kedua nilai itu dengany=Nyy=2xy=2x+1y=2xy2=4x2x2O(1)y=2x+1y2=4x2+4x+1x2xO(1)N untuk melihat mana yang benar.

Dengan cara ini, kita mendapatkan algoritma iteratif di mana kita melakukan iterasi , dan di mana setiap iterasi mengambil waktu. Total waktu berjalan adalah , sesuai kebutuhan.n/2O(1)O(n)

Saya menyadari ini tidak menggunakan pencarian biner. Baiklah.

DW
sumber
Bagus! Terima kasih. Tidak apa-apa untuk tidak menggunakan pencarian biner. A nitpicking: Mengambil , kita memiliki , , dan . Namun, . Karena itu, mungkin atau . Selain itu, gagasan utama penggunaan kembali saat menghitung dalam algoritme Anda mungkin juga berlaku untuk langkah kedua dalam algoritma . Saya akan membiarkan ini terbuka untuk satu atau dua hari. N=9y=N=3M=N/4=2x=M=2y=2x1y=2xy=2x±1x2y2O(n2)
hengxin
3

Apakah kita berbicara bilangan bulat di sini? Di mana N adalah n bit panjang?

A = 2(n/2), B = A  and C = A2
Step: B = B/2
     If C > N,  
         C = C - 2AB + B2    // too high - make smaller
         A = A - B
     Else 
         C = C + 2AB + B2   // keep this bit
         A = A + B                 
Repeat until B = 0                  // =1 on last loop

Loop dilakukan n / 2 kali, yang seharusnya memberi Anda O (n) kinerja

Sunting: Bagaimana cara kerjanya, & mengapa?
Ini adalah versi Perkiraan Berturutan, yang juga digunakan dalam algoritma CORDIC.
Dimulai dengan bit tunggal terbesar yang mungkin (dengan kuadrat kurang dari N) Anda menetapkan satu bit pada suatu waktu, dan menghitung kuadrat baru.
Jika kuadrat baru masih kurang dari N, pertahankan bit sesuai set.
Jika kotak baru terlalu besar, bersihkan bitnya, batalkan efek menambahkannya, dan lanjutkan ke bit berikutnya.

Contoh: N = 441 (1 1011 1001 biner), n = 9

Start:  A = 24 = 16 (1 0000)  B = 16 C = 256 (100 0000)

1   B = 8 (1000) C = 256 + 2(16)(8) + (8)(8) = 576 (10 0100 0000) {high}
    A = 16 + 8 = 24
2   B = 4  (100) C = 576 - 2(16)(4) + (4)(4) = 400 (1 1001 0000) {low}
    A = 24 - 4 = 20
3   B = 2   (10) C = 400 + 2(20)(2) + (2)(2) = 484  (1 1110 0100) {high}
    A = 20 + 2 = 22
4   B = 1    (1) C = 484 - 2(20)(1) + (1)(1) = 441  (1 1011 1001) {keep this}
    A = 22 - 1 = 21
5   B = 1/2 or 0 in integer math; end
Alan Campbell
sumber
Selamat Datang di Ilmu Komputer ! Perhatikan bahwa Anda dapat menggunakan LaTeX di sini untuk mengeset matematika dengan cara yang lebih mudah dibaca. Lihat di sini untuk pengantar singkat.
FrankW
Penjelasan, mengapa (dan bagaimana) algoritma ini bekerja akan lebih baik.
FrankW
0

Metode utama adalah untuk mengisi bit dari kiri ke kanan sambil menjaga perkiraan kami di bawah ini, atau lebih tepatnya persegi perkiraan kami di bawah . Setiap bit adalah kekuatan 2, jadi mengkuadratkan atau mengalikan angka lain dengan selalu sedikit bergeser. NNbb

Jika perkiraan saat ini adalah , , dan kita sudah tahu , kita mendapatkan , dan kita dapat menulis ulang istilah kedua dan ketiga sebagai dan . Kami kemudian tambahkan semuanya dan tes (saya asumsikan Anda dapat melakukan ) dan set menggigit jika alun-alun masih di bawah .ab=2ia2(a+b)2=a2+2ab+b2a<<(i+1)1<<(i<<1)<iN

Kita memulai loop di dan menghitung mundur ke nol, menjaga dan saat kita pergi. Ini semacam pencarian biner, tetapi di mana batas memetakan perbedaan bit-tunggal.i=n/2=n>>1aa2

KWillets
sumber
-3

Saya suka jawaban Alan Campbell : dengan melacak dugaan sebelumnya dengan hati-hati, pengurangan baru itu mudah setiap kali, dan akar kuadrat-dan-tambah biner kira-kira sama cepatnya dengan pembagian-dan-tambah biner.

Tetapi dimungkinkan untuk lebih cepat, dengan alih-alih membuat tebakan Anda berikutnya satu digit biner, alih-alih menggunakan algoritma "Ab" x "Ab", dan membuat tebakan Anda berikutnya rata-rata dari tebakan Anda sebelumnya, dan angka asli dibagi oleh tebakan sebelumnya. Kedengarannya seperti itu akan memakan waktu lebih lama, bukan lebih pendek. Namun, pembagian itu tidak harus tepat. Jadi jika pembagian hanya berjalan ke akar kuadrat dari jumlah digit yang tersisa untuk ditemukan, maka Anda mungkin sebenarnya menghemat waktu. Selain itu, jika untuk divisi Anda, Anda menggunakan metode Prancis, divisi singkatan, maka Anda mungkin benar-benar memecahkan beberapa kecepatan dalam perhitungan Anda untuk pembagian yang sangat besar.

Sekarang, jika kita menambahkan perhitungan secara paralel yang menghasilkan hasil awal yang dapat diperbaiki sebelum jawabannya ditemukan ... maka kita mungkin menemukan sesuatu.

Michael Rudmin
sumber
1
Semua ini terdengar sangat spekulatif. Apakah Anda memiliki jawaban yang lebih pasti?
Yuval Filmus
Ini berbunyi seperti komentar panjang.
Raphael
@ Raphael Yah, itu jawaban parsial. Bukan yang baik, karena ini sangat spekulatif, tetapi lebih dari kritik atas jawaban Alan.
Gilles 'SO- berhenti bersikap jahat'