¿Cuál es la complejidad de una búsqueda entre corchetes usando mediantes?

8

Estoy tratando de estimar la complejidad de un algoritmo que he escrito para el descompilador Reko , donde estoy tratando de "deshacer" la transformación realizada por un compilador a una división entera por una constanteX/ /norte. El compilador ha convertido la división en una multiplicación entera y un cambio:(X2β/ /norte)>>β, dónde βes el número de bits de la palabra máquina de la computadora. La multiplicación constante resultante es mucho más rápida que una división en la mayoría de las arquitecturas contemporáneas, pero ya no se parece al código original.

Para ilustrar: la declaración C

y = x / 10;

será compilado por el compilador de Microsoft Visual C ++ al siguiente lenguaje ensamblador

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

El resultado neto es que el registro eaxahora tendrá el valor esperado del ycódigo fuente.

Un descompilador ingenuo descompilará lo anterior para

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

pero Reko tiene como objetivo hacer que la producción resultante sea más legible que eso mediante la recuperación de la constante que se utilizó en la división original.

El algoritmo mencionado anteriormente se basa en la descripción de este artículo en Wikipedia . Primero, el algoritmo trata el multiplicador constante como el recíproco escalado2β/ /norte. Convierte eso en un número de coma flotante2βrF y luego lo reduce 2β a rF, dónde 0.0<rF<1.0. El paso final y costoso es poner entre corchetes el valor de coma flotanterF entre dos números racionales una/ /si, C/ /re(empezando por 0/1 y 1/1) y repetidamente calcular el mediant (una+C)/ /(si+re)hasta que se alcance algún criterio de convergencia. El resultado debería ser la "mejor" aproximación racionalr al recíproco rF.

Ahora, si el horquillado se realiza con una búsqueda binaria típica que comienza entre los racionales 0 0/ /2β y 2β/ /2βy calculando el punto medio (una/ /si+C/ /re)/ /2, Espero que el algoritmo converja en O(β)pasos. Pero, ¿cuál es la complejidad del algoritmo si se usa el mediante?

John Källén
fuente
@DW He editado la pregunta para explicar lo que quiero decir con "deshacer"
John Källén
¡Gracias! No es una respuesta a su pregunta específica, pero ¿está familiarizado con las fracciones continuas? Son otra forma de encontrar una buena aproximación racional a un número de punto flotante dado. Son muy eficientes, y sospecho que podrían funcionar bien en su entorno (ya que encuentran todas las aproximaciones racionales "muy buenas", para una definición adecuada de "muy bueno").
DW
@DW Solo estoy un poco familiarizado con las fracciones continuas. ¿Existe un algoritmo de aproximación que converja en una solución en O (log n)?
John Källén

Respuestas:

4

La relación entre el árbol Stern-Brocot y las secuencias de Farey muestra que si 0 0<pags/ /q<1 y (pags,q)=1 (es decir, pags/ /q es una fracción reducida) entonces pags/ /q esta en el qEl nivel del árbol. Como el término de ejecución de su algoritmo es lineal en el nivel en el que termina, su algoritmo lleva tiempoO(q), dónde pags/ /qes la respuesta; Pero esto no es tan útil.

No ha especificado cuál es su criterio de detención, pero presumiblemente tiene algún umbral de error ϵ. Por lo tanto, la pregunta es para qué secuencia de Farey es el caso de que los términos adyacentes estén a distancia como máximo2ϵ (y así cada punto está a distancia ϵdesde algún punto). Usando el hecho de que la distancia entre fracciones adyacentespags1/ /q1,pags2/ /q2 en una secuencia de Farey es 1/ /(q1q2), no es difícil demostrar que la distancia máxima en el qLa secuencia de Farey es 1/ /q. Por lo tanto, si está apuntando a una distancia deϵ, entonces su algoritmo se ejecutará a tiempo O(1/ /ϵ) En el peor de los casos.

Sin embargo, "la mayoría" de las fracciones adyacentes en el qLa secuencia de Farey está a distancia O(1/ /q2)y, por lo tanto, en promedio, probablemente esperaría un tiempo de ejecución de O(1/ /ϵ) (desafortunadamente, este promedio es con respecto a la entrada en lugar del algoritmo).

Yuval Filmus
fuente
Entonces parece que el punto medio converge como O (log1 / e) mientras que los mediadores convergen como O (sqrt (1 / e)). Que decepcionante.
John Källén