Was ist die Komplexität einer Suche in Klammern mit Medianten?

8

Ich versuche, die Komplexität eines Algorithmus abzuschätzen, den ich für den Reko-Dekompiler geschrieben habe , wobei ich versuche, die von einem Compiler vorgenommene Umwandlung in eine ganzzahlige Division durch eine Konstante "rückgängig zu machen" . Der Compiler die Aufteilung in eine Ganzzahl umgewandelt Multiplikation und eine Verschiebung: ( x * 2 β / n ) > > β , wobei die Anzahl der Bits des Maschinenwort des Computers ist. Die resultierende konstante Multiplikation ist in den meisten zeitgenössischen Architekturen viel schneller als eine Division, ähnelt jedoch nicht mehr dem ursprünglichen Code.x/n(x2β/n)>>ββ

Zur Veranschaulichung: die C-Anweisung

y = x / 10;

wird vom Microsoft Visual C ++ - Compiler in die folgende Assemblersprache kompiliert

mov edx,1999999Ah  ; load 1/10 * 2^32 
imul eax           ; edx:eax = dividend / 10 * 2 ^32 
mov eax,edx        ; eax = dividend / 10

Das Nettoergebnis ist, dass das Register eaxjetzt den erwarteten Wert yaus dem Quellcode hat.

Ein naiver Dekompiler dekompiliert das Obige zu

eax = ((long)eax * 0x1999999A) >> 32;

Reko zielt jedoch darauf ab, die resultierende Ausgabe lesbarer zu machen, indem die Konstante wiederhergestellt wird, die in der ursprünglichen Division verwendet wurde.

Der oben angedeutete Algorithmus basiert auf der Beschreibung dieses Artikels in Wikipedia . Erstens behandelt der Algorithmus den konstanten Multiplikator als den skalierten Kehrwert . Es konvertiert das in eine Gleitkommazahl und skaliert es dann um auf , wobei . Der letzte, teure Schritt besteht darin, den Gleitkommawert zwischen zwei rationalen Zahlen , (beginnend mit 0/1 und 1/1) zu klammern und den Medianten ) wiederholt zu berechnen2 & bgr; r f 2 & bgr; r f 0,0 < r f < 1,0 r f a / b c / d ( a + c ) / ( b + d ) r r f2β/n2βrf2βrf0.0<rf<1.0rfa/bc/d (a+c)/(b+d)bis ein Konvergenzkriterium erreicht ist. Das Ergebnis sollte die "beste" rationale Annäherung an den Kehrwert .rrf

Wenn nun die Belichtungsreihe mit einer typischen binären Suche durchgeführt wurde, die zwischen den Rationalen und beginnt und den Mittelpunkt berechnet , Ich erwarte, dass der Algorithmus in -Schritten konvergiert . Aber wie komplex ist der Algorithmus, wenn stattdessen der Mediant verwendet wird?2 β / 2 β ( a / b + c / d ) / 2 O ( β )0/2β2β/2β (a/b+c/d)/2O(β)

John Källén
quelle
@ DW Ich habe die Frage bearbeitet, um zu erklären, was ich mit "Rückgängig" meine
John Källén
Vielen Dank! Es ist keine Antwort auf Ihre spezifische Frage, aber kennen Sie fortgesetzte Brüche? Sie sind ein weiterer Weg, um eine gute rationale Annäherung an eine gegebene Gleitkommazahl zu finden. Sie sind sehr effizient, und ich vermute, dass sie in Ihrer Umgebung gut funktionieren (da sie alle "sehr guten" rationalen Näherungen für eine geeignete Definition von "sehr gut" finden).
DW
@ DW Ich bin nur wenig mit fortgesetzten Brüchen vertraut. Gibt es einen Approximationsalgorithmus, der auf eine Lösung in O (log n) konvergiert?
John Källén

Antworten:

4

Die Beziehung zwischen dem Stern-Brocot-Baum und den Farey-Sequenzen zeigt, dass wenn und (dh ist ein reduzierter Bruch), auf dem ten Niveau liegt des Baumes. Da der laufende Term Ihres Algorithmus auf der Ebene, auf der Sie beenden, linear ist, benötigt Ihr Algorithmus die Zeit , wobei die Antwort ist. aber das ist nicht so hilfreich.( p , q ) = 1 p / q p / q q O ( q ) p / q0<p/q<1(p,q)=1p/qp/qqO(q)p/q

Sie haben Ihr Stoppkriterium nicht angegeben, aber vermutlich haben Sie eine Fehlerschwelle . Die Frage ist daher, für welche Farey-Sequenz benachbarte Terme höchstens (und somit jeder Punkt von einem Punkt entfernt ist). Unter Verwendung der Tatsache, dass der Abstand zwischen benachbarten Brüchen in einer Farey-Sequenz , ist es nicht schwer zu zeigen, dass der maximale Abstand bei der ten Farey-Sequenz beträgt . Wenn Sie also eine Entfernung von anstreben , wird Ihr Algorithmus im schlimmsten Fall in der Zeit .2 ε ε p 1 / q 1 , p 2 / q 2 1 / ( q 1 q 2 ) q 1 / q ε O ( 1 / ε )ϵ2ϵϵp1/q1,p2/q21/(q1q2)q1/qϵO(1/ϵ)

"Die meisten" benachbarten Brüche in der ten Farey-Sequenz befinden sich jedoch im Abstand , sodass Sie im Durchschnitt wahrscheinlich eine Laufzeit von erwarten würden (leider) Dieser Durchschnitt bezieht sich eher auf die Eingabe als auf den Algorithmus.O ( 1 / q 2 ) O ( qO(1/q2)O(1/ϵ)

Yuval Filmus
quelle
Es scheint also, dass der Mittelpunkt als O (log1 / e) konvergiert, während Medianten als O (sqrt (1 / e)) konvergieren. Wie enttäuschend.
John Källén