에라토스테네스의 체가 과연 빠르긴 빠르네

꼭 이런 짓을 하고싶을 때가 있다.
소수의 합을 구할 때 에라토스테네스의 체가 빠르다는 거 당연한데, 굳이 일일이 계산하는 거랑 비교해보고 싶었다.
왜 그런지 따윈 없고... 단지 있다면 얼마 전 모 블로그에 내가 쓴 답글이 신경쓰여서랄까나...

그래서 VS .Net 2003으로 만들어봤다.

#include "stdafx.h"
#include <memory.h>
#include <math.h>
#include <windows.h>

#define PRIMES 2000000

int is_prime(int a)
{
    int i, sqrn=(int)sqrt((double)a);

    for(i=3; i<=sqrn; i+=2)
        if(a%i==0)
            return 0;
    return 1;
}

void brutal(int &iPrimes, long long &lSum)
{
    int i;
    lSum=2;
    iPrimes=1;

    for(i=3; i<PRIMES; i+=2)
    {
        if(is_prime(i))
        {
            iPrimes++;
            lSum+=i;
        }
    }
}

void eratosthenes(int &iPrimes, long long &lSum)
{
    bool *bNoPrime = new bool[PRIMES];
    lSum = 0;
    iPrimes = 0;
    int iMaxCompare = (int)sqrt((double)PRIMES);

    memset(bNoPrime, 0, sizeof(bool)*PRIMES);

    int i;
    for (i=2; i<=iMaxCompare; i++)
    {
        if (!bNoPrime[i])
        {
            iPrimes++;
            lSum += i;
        }

        for (int j=i*i; j<PRIMES; j+=i) bNoPrime[j] = true;
    }

    for (i=iMaxCompare+1; i<PRIMES; i++)
    {
        if (!bNoPrime[i])
        {
            iPrimes++;
            lSum += i;
        }
    }

    delete bNoPrime;
}

int main(int argc, char* argv[])
{
    DWORD dw;

    int iPrimes;
    long long lSum;

    dw = GetTickCount();
    eratosthenes(iPrimes, lSum);
    dw = GetTickCount()-dw;

    printf("Sieve of eratosthenes method\n  : %d prime numbers, sum is %I64d (%u milisec)\n", iPrimes, lSum, dw);

    dw = GetTickCount();
    Sleep(100);
    brutal(iPrimes, lSum);
    dw = GetTickCount()-dw;
    printf("Brutal force method\n  : %d prime numbers, sum is %I64d (%u milisec)\n", iPrimes, lSum, dw);

    return 0;
}

결과는 당연히 에라토스테네스의 체 쪽이 훨씬 빠르다.

Sieve of eratosthenes method
  : 148933 prime numbers, sum is 142913828922 (31 milisec)
Brutal force method
  : 148933 prime numbers, sum is 142913828922 (469 milisec)

이걸 해보며 발견한 시궁창같은 현실.

1. Visual C++ 6.0은 long long 형도 인식하지 못한다. 얜 정말 안 되는 애다.
첨엔 결과가 무식하게 클 줄 알고 long long으로 정의했는데, long long을 인식못하는 걸 보고 걍 .Net 2003으로 변절.
__int64로 바꾸면 되긴 하지만, 이미 난 삐졌음!
그런데, 결과는 long int 범위 안쪽. OTL

2. VS 계열에선 bool은 내부적으로 1바이트를 사용하고, BOOL(==int)은 4바이트를 사용한다.
따라서 BOOL이 훨씬 빠른 것이 상식이다.
(32비트 CPU에겐 32비트 연산이 가장 빠름, 8비트는 32비트로 확장해서 처리)
그런데, 소수 테이블을 bool로 지정할 때가 BOOL로 지정할 때보다 훨씬 빠르다. 뭐지?

3. VS6이나 VS.Net 2003이나 2백만 개의 배열은 못 잡는다. 런타임 오류 발생.
그래도 new를 이용해 동적으로 할당받는 건 문제가 없으니 예쁘게 봐주고 넘어감.

4. 댓글 보고 다시 확인해보니 결과가 틀렸음. long이 아니라 long long이 맞음.
그런데 잘못 생각한 이유는 다름아닌 .Net 2003의 printf에서 "%lld"를 인식하지 못하기 때문.
MSDN을 뒤져보니 VS2005부터는 %lld를 인식하나보다. 제길슨.


참, 무식하게 찾는 쪽 코드는 Studying the Logical World에서 거의 그대로 업어왔다.
여기가 앞에서 언급한 그 블로그다.

Trackback 2 Comment 7
  1. Favicon of http://zfanta.com BlogIcon  환타 2009.09.06 15:53 address edit & delete reply

    정보올림피아드에선 아직도 대부분 vs6을 많이 쓴다고 하네요 ㅋㅋ
    그리고 답은 142913828922로 long long으로 해줘야 합니다.

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.09.06 16:10 address edit & delete

      그렇군요. 수정해뒀습니다.
      이번 주말 몇 가지 테스트를 해 본 결과 VS6를 .Net 2003으로 대체할 필요가 없다는 결론을 내렸습니다. OTL

      회사에서 다음 버전을 사 주면 그 땐 좀 더 다양한 테스트를 해봐야겠습니다.

      참, 아시겠지만, VS6에서 이 짓(?)을 하려면 long long → __int64, %lld → %I64d 로 바꿔줘야 합니다. 물론 본 소스도 그렇게 하면 잘 돌아가구요.

  2. 김우승 2009.09.06 17:21 address edit & delete reply

    가급적이면 C99의 기술은 MS compiler와는 같이 안 쓰는게 좋을 것 같은데요.
    VS 2008에서도 표준 호환은 C95라고 명시하고 있습니다. VS 2010에서는 아예 C 표준 library 중 안전하지 않다고 생각하는 것에다가 오류 message를 낸다고 하더군요. 좀 심했다고 생각....

    bool과 BOOL의 경우는 단일체의 경우는 BOOL이 빠르겠지만 배열이나 다른 container의 경우는 bool이 일반적으로 빠른게 당연할 겁니다. 왜냐하면 memory 사용량이 확 주니까요. 우리는 보통 가상 memory system을 쓰기 때문에 memory 할당을 하는 것이 복잡합니다. 따라서 적은 양의 memory를 쓰는게 좋죠.

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.09.06 18:34 address edit & delete

      1. 그렇다면 VS6이나 VS2003에서 64비트 변수를 사용하기 위해선 어떤 지시자를 써야 하는 건가요?
      어떤 표준을 따르는지를 명확하게 하겠다고 표준을 죄다 찾아볼 수도 없고... OTL

      2. bool과 BOOL은 어셈블러 코드를 뽑아보니 명확해지더군요.
      BOOL에선 굳이 *4를 계속 하시던데, 그 놈이 느린 속도의 원인이었습니다.

    • 김우승 2009.09.06 22:57 address edit & delete

      1. 글쎄요. 그게 솔직히 진지하게 고민해본 적이 없군요... -_-. 죄송.
      좀 찾아보고, 고민도 해봤는데요.
      그냥 제가 쓸데없는 소리 한 것 같습니다. 잊어주세요.
      C 표준과 Visual C++ 관계는 2007년 올라온 이 글을 참고하는게 좋을 것 같습니다.
      http://blogs.msdn.com/vcblog/archive/2007/11/05/iso-c-standard-update.aspx

      2. 전 * 4가 그렇게 성능을 하락시키는 요인이라고 생각하지 않습니다. 요새는 귀찮아서 직접 하고 싶지가 않네요... 이 또한 죄송.

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.09.06 23:04 address edit & delete

      1. 읽어보겠습니다. 좋은 정보 고맙습니다.

      2. 컴파일된 어셈블러를 놓고 비교해본 겁니다.
      다른 부분 코드에 전혀 차이가 없으니 *4가 원인일 수 밖에 없습니다.
      게다가 무려 200만번 루프를 돌고, 내부적으로 한 루프당 3번씩 계산을 하니까 곱하기를 600만번 더 했습니다.
      이 정도면 원인이 될 수 있다고 봅니다.

      가상메모리는 어짜피 한번에 할당받는 크기가 달라졌을 뿐이니 여기선 원인이 아닐 것 같습니다. 저도 더 이상 확인해보고 싶은 생각은 안 드니 패스하겠습니다.

  3. 지나가던사람 2009.12.29 21:32 address edit & delete reply

    오래된 글이지만 지나가다가 답글 달아봅니다. 2백만 개의 배열을 못 잡는건 스택영역에 잡으셨기 떄문이죠. 전역변수로 잡으시면 됩니다.