Berechnen Sie die Quadratwurzel mit (Bit-) Additionen und Verschiebungen als Grundelemente

8

Frage: Wie kann man bei einer natürlichen Bit-Zahl nur mit (Bit) und berechnen ?N nNO(n)NO(n)

Der Tipp ist die binäre Suche. Ich konnte jedoch die erforderliche Komplexität nicht erreichen (ich habe ).O(n2)


Was bedeutet es mit using only $O(n)$ (bit) additions and shifts:

Dies ist eine Übung in einem Algorithmusbuch.
Meiner Meinung nach bedeutet dies, dass das Addieren von zwei natürlichen Zahlen , beispielsweise Bit, kostet und das Verschieben einer natürlichen Zahl von beispielsweise Bit ebenfalls kostet . Dann dürfen wir solche -Operationen nur -mal verwenden. Die Vergleichskosten werden nicht erwähnt. Ich denke, wir können es ignorieren oder davon ausgehen, dass der Vergleich von zwei natürlichen Zahlen , beispielsweise Bit, ebenfalls kostet .O ( 1 ) n O ( 1 ) , O ( 1 ) , O ( n ) n O ( 1 )nO(1)nO(1)O(1)O(n)
nO(1)


Mein -AlgorithmusO(n2) :

  1. Bestimmen Sie den Bereich der Anzahl der Bits von : Daher ist t_1 \ triangleq \ lfloor \ frac {n-1} {2} \ rfloor + 1 \ le t \ le \ lceil \ frac {n} {2} \ rceil + 1 \ triangleq t_2.t2 n - 1Nt1n-1
    2n12N2n22n12N2n2
    t1n12+1tn2+1t2.
  2. Binäre Suche: Finden Sie N zwischen 2t1 und 2t2 mithilfe der binären Suche. Für jede Zahl x , zu berechnen x2 Additionen und Verschiebungen als Primitive verwendet und vergleicht ihn mit N .

Die Komplexität ist somit für Zeiten der binären Suche und Berechnung von , von denen jede wiederum Additionen und Verschiebungen benötigt.O ( n ) × 2 O ( n )O(n×n)=O(n2)O(n)x2O(n)

Hengxin
quelle

Antworten:

7

Ein iterativer Algorithmus scheint zu funktionieren.

Sei . Angenommen, wir wissen, dass die ganzzahlige Annäherung an , dh , und nehmen an, dass wir den Wert von (der zuvor erhalten wurde).x M=N/4x x=Mx2x=Mx2

Jetzt wollen wir . Was sind die möglichen Werte von ? Ich bin mir ziemlich sicher, dass die einzig möglichen Werte oder . Und es ist einfach, beide auszuprobieren und herauszufinden, welche richtig ist. Insbesondere für haben wir , was aus durch zwei Linksverschiebungen ( -Zeit) erhalten werden kann; für haben wir , was aus und mit vier Linksverschiebungen und zwei Additionen ( -Zeit) erhalten werden kann. Vergleichen Sie nun einfach diese beiden Werte mityy=2y=Nyyy=2xy = 2 x y 2 = 4 x 2 x 2 O ( 1 ) y = 2 x + 1 y 2 = 4 x 2 + 4 x + 1 x 2 x O. ( 1 ) N.y=2x+1y=2xy2=4x2x2O(1)y=2x+1y2=4x2+4x+1x2xO(1)N um zu sehen, welches richtig ist.

Auf diese Weise erhalten wir einen iterativen Algorithmus, bei dem wir Iterationen durchführen und bei dem jede Iteration Zeit benötigt. Die Gesamtlaufzeit beträgt je nach Bedarf .O ( 1 ) O ( n )n/2O(1)O(n)

Mir ist klar, dass dies keine binäre Suche verwendet hat. Naja.

DW
quelle
Nett! Vielen Dank. Es ist in Ordnung, keine binäre Suche zu verwenden. Ein Nitpicking: Wenn wir , haben wir y = N=9,M=N/4=2und. Jedoch. Daher kann esoder. Darüber hinaus kann die Schlüsselidee der Wiederverwendung vonbei der Berechnung vonin Ihrem Algorithmus auch für den zweiten Schritt in meinem-Algorithmus angewendet werden. Ich werde dies für ein oder zwei Tage offen lassen. y=N=3M=N/4=2y=2x-1y=2xy=2x±1x2y2O(n2)x=M=2y=2x1y=2xy=2x±1x2y2O(n2)
Hengxin
3

Sprechen wir hier über ganze Zahlen? Wo ist N n Bits lang?

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

Die Schleife wird n / 2 Mal ausgeführt, was zu einer O (n) -Leistung führen sollte

Edit: Wie funktioniert es und warum?
Dies ist eine Version von Successive Approximation, die auch in CORDIC-Algorithmen verwendet wird.
Beginnend mit dem größtmöglichen Einzelbit (mit einem Quadrat kleiner als N) setzen Sie jeweils ein Bit und berechnen das neue Quadrat.
Wenn das neue Quadrat immer noch kleiner als N ist, behalten Sie das gesetzte Bit bei.
Wenn das neue Quadrat zu groß ist, löschen Sie das Bit, machen Sie den Effekt des Hinzufügens rückgängig und fahren Sie mit dem nächsten Bit fort.

Beispiel: N = 441 (1 1011 1001 binär), 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
quelle
Willkommen in der Informatik ! Beachten Sie, dass Sie hier LaTeX verwenden können, um die Mathematik besser lesbar zu setzen. Sehen Sie hier eine kurze Einführung.
FrankW
Eine Erklärung, warum (und wie) dieser Algorithmus funktioniert, wäre schön.
FrankW
0

Die Hauptmethode besteht darin, die Bits von auszufüllenNNbb

ab=2ia2(a+b)2=a2+2ab+b2a<<(i+1)1<<(i<<1)<iN

i=n/2=n>>1aa2

KWillets
quelle
-3

Ich mag die Antwort von Alan Campbell : Durch sorgfältiges Verfolgen früherer Vermutungen ist die neue Subtraktion jedes Mal einfach, und die binäre Quadratwurzel zum Verschieben und Hinzufügen ist ungefähr so ​​schnell wie eine binäre Teilung zum Verschieben und Hinzufügen.

Es kann jedoch möglich sein, schneller zu gehen, indem Sie Ihre nächste Schätzung nicht zu einer einzelnen Binärziffer machen, sondern stattdessen einen "Ab" x "Ab" -Algorithmus verwenden und Ihre nächste Schätzung zum Durchschnitt Ihrer vorherigen Schätzung und zur geteilten ursprünglichen Zahl machen durch die vorherige Vermutung. Das klingt so, als würde es länger dauern, nicht kürzer. Die Aufteilung muss jedoch nicht genau sein. Wenn die Division also nur bis zur Quadratwurzel der Anzahl der zu findenden Stellen läuft, sparen Sie möglicherweise Zeit. Wenn Sie für Ihre Division die französische Methode der Kurzschriftdivision verwenden, können Sie außerdem tatsächlich eine gewisse Geschwindigkeit in Ihrer Berechnung für wirklich große Divisionen brechen.

Wenn wir nun parallel Berechnungen hinzufügen, die vorläufige korrigierbare Ergebnisse liefern, bevor die Antwort gefunden wird, dann sind wir vielleicht auf etwas fixiert.

Michael Rudmin
quelle
1
All dies klingt sehr spekulativ. Haben Sie eine genauere Antwort?
Yuval Filmus
Dies liest sich wie ein Kommentar in Langform.
Raphael
@ Raphael Nun, es ist eine teilweise Antwort. Nicht gut, weil es extrem spekulativ ist, aber es ist mehr als eine Kritik an Alans Antwort.
Gilles 'SO - hör auf böse zu sein'