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

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