mwultong Blog ... 프로그래밍 / 계산기

컴퓨터 엑셀 워드 포토샵 구글어스 WINDOWS JAVASCRIPT JAVA C++

 
Thursday, October 05, 2006

C언어] 소수 계산: 소수(素數) 찾기/만들기: Prime Number Generator


C언어와 수학에 대한 게시물입니다.

이것은 원래 자바로 되어 있던 소스입니다: ▶▶ 자바/Java] 소수 찾기/만들기 (素數): Prime Number Generator 참고

자바와 속도 비교도 할 겸, C로 작성해 보았습니다.

파일명: 0.cpp
#include <stdio.h>
#include <math.h>

int isPrime(unsigned int number);


void main(void) {

  puts("2\n3");

  for (unsigned int i = 5; i < 0xFFFFFF; i += 2)
    if (isPrime(i)) printf("%u\n", i);

}




int isPrime(unsigned int number) {
  if (number % 3 == 0) return 0;

  unsigned int y = 2;
  unsigned int x = (unsigned int) sqrt((double)number);

  for (unsigned int i = 5; i <= x; i += y, y = 6 - y)
    if (number % i == 0) return 0;

  return 1;
}



자바와 속도 비교


0xFFFFFF (16777215) 까지의 수에서 소수를 찾았습니다

C언어:
0:00:41.84 (41 sec)

JAVA:
0:00:59.94 (59 sec)

자바가 C보다 약간 느린 정도입니다. 의외로 빠릅니다.
그런데 자바 소스에서 int 를 모두 long 으로 바꾸어 주니
0:02:45.79 (2 min 45 sec)
이렇게 오래 걸렸습니다.

C의 int 와 long 은 모두 32비트이고,
자바의 int 는 32비트, long 은 64비트이기 때문에 느린 것은 당연하지만, 2배 넘게 느린 것은 좀 놀랍군요.



C소스에서 "unsigned int"를 64비트 정수인 "unsigned __int64" 로 모두 바꾸고 실행해 보니
0:01:22.21 (1 min 22 sec)
자바보다는 빠르지만, 역시 이렇게 느려졌습니다.


결론은, 32비트 정수를 다룰 때에는, 자바의 속도가 그리 느리지 않고, 순수한 C에 육박한다는 것입니다.



0xFFFFFF 이 정도의 숫자는 가장 빠른 알고리즘으로는
0:00:03.04 (3 sec)
밖에 걸리지 않습니다. 물론 엄청나게 복잡한 알고리즘의 C 프로그램입니다. 여기서 소개하는 간단한 알고리즘으로는 45초 정도도 빠른 것입니다.


지금까지 말한 모든 속도 측정은, 펜티엄III 1.3기가 CPU에서 이루어졌습니다.

그렇지만 소수 찾기 속도는 컴퓨터 성능이 아닌 알고리즘 성능에 좌우됩니다.





실제 계산보다, 화면 출력에서 시간이 더 소모되기에, 화면으로 출력하는 대신
0.exe > out.txt
이렇게 재지향(Redirection)하여, 결과를 파일로 직접 저장하면 빠릅니다.




tag: cpp
C언어 | C/C++ (Visual C++)

0 Comments:

<< Home RSS 2.0 feed

구글 Google 에서 제공하는 무료 블로그 서비스인 블로거 Blogger 의 인터넷 주소는 www.blogger.com 입니다. Blogger 에 블로그를 만들면, blogspot.com 이라는 주소에 블로그가 생성됩니다.
블로그를 직접 방문하지 않고도 최신 게시물을 구독하려면 RSS 2.0 feed 주소를 리더기에 등록하시면 됩니다.
Previous Posts
Monthly Archives
Top