Como posso otimizar meu 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;
}

Estou tentando superar/combinar o código da função superior com minha própria função (inferior).Você tem alguma ideia de como posso otimizar minha rotina?

PS.Isto é apenas para diversão.

Answer 1

Vou assumir que você deseja manter o mesmo algoritmo. Isso deve ser pelo menos uma implementação um pouco mais eficiente dela. A principal diferença é que o código no loop usa apenas registros, não a memória.

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
    }
}

Como Jason apontou, no entanto, esse realmente não é um algoritmo muito eficiente - multiplicando, encontrar o GCD e dividir normalmente será mais rápido (a menos que a e b são muito pequenos).

EDIT: Há outro algoritmo que é quase mais simples de entender, que também deve ser muito mais rápido (do que o original - não do que se multiplicar e depois dividir pelo GCD). Em vez de gerar números consecutivos até encontrar um que divida os dois a e b, gerar múltiplos consecutivos de um (de preferência o maior) até encontrar um que se divida uniformemente pelo outro:

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
    }
}

Isso permanece morto simples de entender, mas deve dar uma melhoria considerável em relação ao original.

Answer 2

Eu otimizaria usando um algoritmo diferente.Pesquisar linearmente como você está fazendo é muito lento.É um facto que o mínimo múltiplo comum de dois números naturais é o quociente do seu produto dividido pelo seu máximo divisor comum.Você pode calcular o máximo divisor comum rapidamente usando o Algoritmo euclidiano.

Por isso:

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

onde você precisa implementar gcd(int, int).Como o número médio de etapas no algoritmo euclidiano é O(log n), vencemos a ingênua busca linear.

Existem outras abordagens para este problema.Se você tivesse um algoritmo que pudesse fatorar números inteiros rapidamente (digamos, um computador quântico), então você também pode resolver esse problema assim.Se você escrever cada um a e b em sua fatoração 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

então o mínimo múltiplo comum de a e b é o obtido tomando para cada fator primo que aparece em pelo menos uma das fatorações de a e b, tomando-o com o expoente máximo que aparece na fatoração de a ou b.Por exemplo:

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

para que

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

Tudo isso é para ressaltar que abordagens ingênuas são admiráveis ​​em sua simplicidade, mas você pode passar o dia todo otimizando até o último nanossegundo delas e ainda assim não superar um algoritmo superior.