¿Cómo puedo optimizar mi código C / X86?

Question

int lcm_old(int a, int b) {
    int n;
    for(n=1;;n++)
        if(n%a == 0 && n%b == 0)
            return n;  
}

int lcm(int a,int b)  {
    int n = 0;
    __asm {
lstart:
        inc n;
        mov eax, n;
        mov edx, 0;
        idiv a;
        mov eax, 0;
        cmp eax, edx;
        jne lstart;
        mov eax, n;
        mov edx, 0;
        idiv b;
        mov eax, 0;
        cmp eax, edx;
        jnz lstart;
    }
    return n;
}

Estoy tratando de vencer/combinar el código para la función superior con mi propia función (abajo). ¿Tienes alguna idea de cómo puedo optimizar mi rutina?

PD. Esto es sólo por diversión.

Answer 1

Voy a asumir que quieres mantener el mismo algoritmo. Esto debería ser al menos una implementación un poco más eficiente de la misma. La principal diferencia es que el código en el bucle solo usa registros, no de memoria.

int lcm(int a,int b)  {
    __asm {
        xor ecx, ecx
        mov esi, a
        mov edi, b
lstart:
        inc ecx
        mov eax, ecx
        xor edx, edx
        idiv esi
        test edx, edx
        jne lstart
        mov eax, ecx;
        idiv edi
        test edx, edx
        jnz lstart
        mov eax, ecx
        leave
        ret
    }
}

Sin embargo, como señaló Jason, este realmente no es un algoritmo muy eficiente: multiplicar, encontrar el GCD y dividir normalmente será más rápido (a menos que a y b son bastante pequeños).

Editar: hay otro algoritmo que es casi más simple de entender, que también debería ser mucho más rápido (que el original, no que multiplicarse, luego dividir por GCD). En lugar de generar números consecutivos hasta que encuentre uno que divida ambos a y b, genere múltiplos consecutivos de uno (preferiblemente el más grande) hasta que encuentre uno que se divida uniformemente por el otro:

int lcm2(int a, int b) { 
    __asm { 
        xor ecx, ecx
        mov esi, a
        mov edi, b
    lstart:
        add ecx, esi
        mov eax, ecx
        xor edx, edx
        idiv edi
        test edx, edx
        jnz lstart
        mov eax, ecx
        leave
        ret
    }
}

Esto sigue siendo simple de entender, pero debería dar una mejora considerable sobre el original.

Answer 2

Optimizaría usando un algoritmo diferente. Buscar linealmente como estás haciendo es súper lento. Es un hecho que el mulitple menos común de dos números naturales es el cociente de su producto dividido por su mayor divisor común. Puedes calcular el mayor divisor común rápidamente usando el Algoritmo euclidiano.

De este modo:

int lcm(int a, int b) {
    int p = a * b;
    return p / gcd(a, b);
}

donde necesitas implementar gcd(int, int). Como el número promedio de pasos en el algoritmo euclidiano es O(log n), vencimos a la ingenua búsqueda lineal.

Hay otros enfoques para este problema. Si tuviera un algoritmo que podría tener en cuenta rápidamente los enteros (digamos un computadora cuántica) Entonces también puedes resolver este problema como así. Si escribes cada uno de a y b en su factorización principal canónica

a = p_a0^e_a0 * p_a1^e_a1 * ... * p_am^e_am
b = p_b0^e_b0 * p_b1^e_b1 * ... * p_bn^e_bn

entonces el múltiplo menos común de a y b es el obtenido tomando para cada factor principal que aparece en al menos una de las factorizaciones de a y b, tomándolo con el exponente máximo que aparece en la factorización de a o b. Por ejemplo:

28 = 2^2 * 7
312 = 2^3 * 39

de modo que

lcm(28, 312) = 2^3 * 7 * 39 = 2184

Todo esto es para señalar que los enfoques ingenuos son admirables en su simplicidad, pero puede pasar todo el día optimizando hasta el último nanosegundo de ellos y aún no vence un algoritmo superior.