Как я могу оптимизировать код 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

Я бы оптимизировал, используя другой алгоритм. Поиск линейно, как вы делаете, это супер-трюк. Это факт, что наименее распространенным мультиплом из двух натуральных чисел является коэффициентом их продукта, разделенного на их самый распространенный делитель. Вы можете быстро вычислить наибольший общий делитель, используя Евклидовый алгоритм.

Таким образом:

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

Все это означает, что наивные подходы восхитительны в их простоте, но вы можете провести целый день оптимизировать каждую последнюю наносекунду из них и при этом не победить превосходный алгоритм.