如何优化我的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)  {
    __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
    }
}

正如杰森指出，然而，这确实是不是一个非常高效的算法 - 相乘，找到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
    }
}

这仍然是死的简单理解，但应该给比原先有了很大的改进。

Answer 2

我将通过使用不同的算法进行优化。搜索线性喜欢你做的是超慢。这是一个事实，即两个自然数的最小公倍数多张是他们的产品通过自己的最大公约数商。你可以计算最大公约数快速使用欧几里德算法。

因此：

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或b的因式分解的最大指数服用得到。例如：

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

，使得

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

这一切是指出天真的方法是在其简单令人钦佩的，但你可以整天每一个最后的纳秒优化了出来，但仍不能打了一个优越的算法。