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

 
Previous Post 자바/Java] 소수 찾기/만들기 (素數): Prime Number GeneratorC언어] 문자열 비교, 대소문자 구분/구분없이 비교하기 - Compare Strings I...del.icio.us / blogspot.com 등의 한글 인코딩(Encoding)은?C언어] 짝수 홀수 여부 판단; 숫자 짝홀 구하기; Even, Odd NumberBoot disk failure: 우분투를 VMware에 설치할 때 에러 해결 - (VM웨...C언어] (Yes-No) (Y-N) (+Cancel) 선택 묻기 사용자 입력받기 - 예/아...리눅스] 페도라(Fedora)를 VMware에 설치할 때, 운영체제(OS) 선택은?Ubuntu] 우분투 리눅스 비프음 제거하는 법 - Beep(삑삑하는 소리) 없애기C언어] 정규분포, 가우스(Gaussian) 랜덤(난수) 발생 - Gaussian Rand...우분투(Ubuntu)리눅스] root 계정으로 로그인하기, 루트(root) 계정 만들기

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

Thursday, October 05, 2006

이것은 원래 자바로 되어 있던 소스입니다: ▶▶ 자바/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)하여, 결과를 파일로 직접 저장하면 빠릅니다.

☞ C/C++

0 Comments:

Post a Comment

<< Home RSS 2.0 feed

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