Как я могу оптимизировать мой код C / x86? - PullRequest
Новая
       28

Как я могу оптимизировать мой код C / x86?

4 голосов
/ 08 февраля 2010 
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;
}

Я пытаюсь разбить / сопоставить код для функции top с моей собственной функцией (внизу). У вас есть идеи, как я могу оптимизировать свою рутину?

PS. Это просто для удовольствия.

Ответы [ 2 ]

14 голосов
/ 08 февраля 2010

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

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

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

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

5 голосов
/ 08 февраля 2010

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

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

Это до сих пор просто понять, но должно дать значительное улучшение по сравнению с оригиналом.

...