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

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$$(x * \lfloor 2^\beta / n \rfloor) >> \beta$$\beta$

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 $2^\beta / n$$2^\beta r_f$$2^\beta$$r_f$$0.0 < r_f <1.0$$r_f$$a/b$$c/d$ $(a + c)/(b + d)$bis ein Konvergenzkriterium erreicht ist. Das Ergebnis sollte die "beste" rationale Annäherung an den Kehrwert .$r$$r_f$

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^\beta$$2^\beta/2^\beta$ $(a/b + c/d)/2$$O(\beta)$

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 /$0 < p/q < 1$$(p,q) = 1$$p/q$$p/q$$q$$O(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 / ε $\epsilon$$2\epsilon$$\epsilon$$p_1/q_1,p_2/q_2$$1/(q_1q_2)$$q$$1/q$$\epsilon$$O(1/\epsilon)$

"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 ( $q$$O(1/q^2)$$O(\sqrt{1/\epsilon})$