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

別のアルゴリズムを使用して最適化します。あなたがしているように直線的に検索するのは超遅いです。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つに現れる素因数ごとに、またはの因数分解に現れる最大の指数をとることaによって得られます。例えば：bab

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

となることによって

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

これはすべて、素朴なアプローチはその単純さにおいて称賛に値するが、それらから最後の1ナノ秒ごとに最適化することに一日を費やすことができ、それでも優れたアルゴリズムに勝るものはないことを指摘することです。

于 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一方が他方で均等に割り切れる数が見つかるまで、1 の連続する倍数 (できれば大きい方) を生成します。

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 に答える