Thursday, October 05, 2006

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

이것은 원래 자바로 되어 있던 소스입니다: ▶▶ 자바/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: