كيف يمكنني تحسين بلدي ج / 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 صغيرة جدا).

عدل بدلا من إنشاء أرقام متتالية حتى تجد واحدة تقسم كلاهما 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

وأود أن تحسين باستخدام خوارزمية مختلفة.البحث خطيا مثل تقومون به هو سوبر بطيئة.انها حقيقة أن أقل شيوعا mulitple اثنين من الأعداد الطبيعية هو حاصل من منتجاتها مقسوما أعظم القاسم المشترك.يمكنك حساب القاسم المشترك الأكبر بسرعة باستخدام خوارزمية أقليدس.

وبالتالي:

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

كل هذا هو أن نشير إلى أن من السذاجة النهج الإعجاب في البساطة ولكن هل يمكن أن تنفق كل يوم تحسين كل نانوثانية للخروج منها و لا تزال لا تغلب متفوقة الخوارزمية.