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

上部関数のコードを自分の関数（下）で打ち負かす/一致させようとしています。ルーチンを最適化する方法はありますか？

詩これはただの楽しみのためです。

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

別のアルゴリズムを使用して最適化します。あなたがしているように直線的に検索するのは超スローです。 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 の少なくとも1つの因数分解の1つに現れる各プライムファクターを取得することによって得られますか a と b, 、の因数分解に表示される最大指数でそれを取る a また b. 。例えば：

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

となることによって

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

これはすべて、ナイーブなアプローチはそのシンプルさにおいて賞賛に値することを指摘することですが、最後のナノ秒ごとに一日中最適化することができ、それでも優れたアルゴリズムを打ち負かすことはできません。