4 
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。这只是为了好玩。

4

2 回答 2

14

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

因此：

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的因式分解中的最大指数来获得的。例如：ab

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

以便

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

所有这一切都是为了指出，幼稚的方法因其简单性而令人钦佩，但您可以花一整天时间优化它们的每一纳秒，但仍然无法击败卓越的算法。

于 2010-02-08T16:13:08.943 回答
5

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

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

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

于 2010-02-08T16:30:43.770 回答