Comment puis-je optimiser mon code 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;
}

Je suis en train de battre / correspondre au code de la fonction supérieure avec ma propre fonction (en bas). Avez-vous des idées comment je peux optimiser ma routine?

PS. Ceci est juste pour le plaisir.

Answer 1

Je vais supposer que vous voulez garder le même algorithme. Cela devrait au moins être une mise en œuvre un peu plus efficace de celui-ci. La principale différence est que le code dans la boucle utilise uniquement les registres, pas de mémoire.

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

Comme Jason a souligné, cependant, ce qui est vraiment pas un algorithme très efficace -. Multiplier, trouver le GCD, et la division sera normalement plus rapide (à moins a et b sont assez petites)

Edit: il y a un autre algorithme qui est presque plus simple à comprendre, qui devrait aussi être beaucoup plus rapide (que l'original - pas de multiplication, division puis par GCD). Au lieu de générer des numéros consécutifs jusqu'à ce que vous trouviez celui qui divise les deux a et b, générer des multiples consécutifs d'un (de préférence la plus grande) jusqu'à ce que vous trouviez un qui divise de façon uniforme par l'autre:

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

Il reste mort simple à comprendre, mais devrait donner une amélioration considérable par rapport à l'original.

Answer 2

J'optimiser à l'aide d'un algorithme différent. La recherche linéaire comme vous faites est super lent. Il est un fait que les moins mulitple communs de deux nombres naturels est le quotient de leur produit divisé par leur plus grand commun diviseur. Vous pouvez calculer le plus grand commun diviseur rapidement en utilisant le euclidienne algorithme .

Ainsi:

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

où vous devez mettre en œuvre gcd(int, int). Comme le nombre moyen d'étapes de l'algorithme d'Euclide est O(log n), nous avons battu les mains naïves de recherche linéaire vers le bas.

Il existe d'autres approches de ce problème. Si vous aviez un algorithme qui pourrait rapidement factoriser des nombres entiers (par exemple un quantique ordinateur ), vous pouvez aussi résoudre ce problème comme si. Si vous écrivez chacun a et b dans sa factorisation canonique

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

alors le plus petit multiple commun de a et b est l'obtenue en prenant pour chaque facteur premier apparaissant dans au moins l'un des factorisations de a et b, prenant avec l'exposant maximum qu'il apparaît dans la factorisation de a ou b . Par exemple:

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

de sorte que

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

Tout cela est à souligner que les approches naïves sont admirables dans leur simplicité, mais vous pouvez passer toute la journée d'optimiser tous les derniers nanoseconde d'eux et toujours pas battre un algorithme supérieur.