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 constante. El compilador ha convertido la división en una multiplicación entera y un cambio:, 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 eax
ahora tendrá el valor esperado del y
có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 escalado. Convierte eso en un número de coma flotante y luego lo reduce a , dónde . El paso final y costoso es poner entre corchetes el valor de coma flotante entre dos números racionales , (empezando por 0/1 y 1/1) y repetidamente calcular el mediant hasta que se alcance algún criterio de convergencia. El resultado debería ser la "mejor" aproximación racional al recíproco .
Ahora, si el horquillado se realiza con una búsqueda binaria típica que comienza entre los racionales y y calculando el punto medio , Espero que el algoritmo converja en pasos. Pero, ¿cuál es la complejidad del algoritmo si se usa el mediante?
fuente
Respuestas:
La relación entre el árbol Stern-Brocot y las secuencias de Farey muestra que si0 < p / q< 1 y ( p , q) = 1 (es decir, p / q es una fracción reducida) entonces p / q esta en el q El 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 p / q es 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 q La 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 elq La 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).
fuente