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

그러나 Jason이 지적했듯이 이것은 실제로 매우 효율적인 알고리즘은 아닙니다. 곱셈, 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

이 모든 것은 순진한 접근 방식이 단순함에 감탄할 수 있음을 지적하는 것입니다. 그러나 하루 종일 마지막 나노초를 최적화하는 데 보낼 수 있지만 여전히 우수한 알고리즘을 이길 수는 없습니다.