如何优化我的 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;
}

我试图用我自己的函数（底部）击败/匹配顶部函数的代码。您对如何优化我的日常工作有什么想法吗？

PS。这只是为了好玩。

Answer 1

我会使用不同的算法进行优化。像你一样线性搜索是非常慢的。事实上，两个自然数的最小公倍数是它们的乘积除以它们的最大公约数的商。您可以使用欧几里得算法快速计算最大公约数。

因此：

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

您需要在其中实现gcd(int, int)。由于欧几里得算法的平均步骤数为O(log n)，我们轻松击败了简单的线性搜索。

对于这个问题还有其他方法。如果您有一种可以快速分解整数的算法（例如量子计算机），那么您也可以像这样解决这个问题。如果将 a 和 b 分别写入其规范素数分解，

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

则 a 和 b 的最小公倍数是通过对 a 和 b 至少其中一个分解中出现的每个质因数取它在 a 分解中出现的最大指数来获得的代码>a或b。例如：

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

所有这些都是为了

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

指出，朴素的方法因其简单性而令人钦佩，但您可以花一整天的时间来优化它们的每一纳秒，但仍然无法击败高级算法。

Answer 2

我假设您想保留相同的算法。这至少应该是一个稍微更有效的实现。主要区别在于循环中的代码仅使用寄存器，而不使用内存。

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

然而，正如 Jason 指出的那样，这确实不是一个非常有效的算法——乘法、求 GCD 和除法通常会更快（除非 a 和 b相当小）。

编辑：还有另一种算法几乎更容易理解，它也应该快得多（比原来的算法——不是乘法，然后除以 GCD）。不要生成连续的数字，直到找到一个能整除 a 和 b 的数字，而是生成一个的连续倍数（最好是较大的数字），直到找到一个能被另一个整除的数字：

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

这仍然很容易理解，但应该比原来有相当大的改进。