fortran과 C언어로 소수 구하기
In the world/컴퓨터 2009. 5. 22. 17:25소수 구하는 프로그램은 알려진 것이 많지만, 내 생각 구조가 일반적인 사람의 영역에 속한는 지 알아보기 위해 새로 만들어봤다.
먼저 fortran77로 구현해 보았다. 그 이유는 안타깝게도(?) fortran77이 나에게 가장 익숙한 언어이기 때문이다. 간단하게 제일 먼저 떠오른 생각은 소수의 정의이다. 어떤 자연수가 소수이기 위해서는 1과 자기 자신 이외로는 나누어 떨어지지 말아야 한다. 요넘을 그대로 적용해 보았다. 아주 단순 무식하게..
PROGRAM PRIME_NUM
IMPLICIT NONE
INTEGER PRIME(20000),I,J,L,MAX_NUM
LOGICAL N
MAX_NUM=100000
N=.TRUE.
L=3
PRIME(1)=1
PRIME(2)=2
PRINT*,PRIME(2)
DO I=3,MAX_NUM,2
DO J=2,L-1
IF(MOD(I,PRIME(J)).EQ.0) N=.FALSE.
ENDDO
IF(N.EQ..TRUE.) THEN
PRINT*,I
PRIME(L)=I
L=L+1
ENDIF
N=.TRUE.
ENDDO
END
100000까지의 자연수 중에 소수를 출력하는 코드이다. 1은 소수가 아니고 2는 소수라는 기본 정보를 넣고, 그 다음부터는 자신보다 작은 소수로 나누어 떨어지는지를 확인하고 소수면 출력하고 PRIME이란 배열에 넣어준다. PRIME이라는 배열은 다음 숫자의 소수여부를 판단할 때 사용한다.
얼핏보면 그럴 듯 하고, 맞는 결과를 출력하지만 예상대로 매우 느리다.
이쯤되면 생각의 전환이 필요하다. 숫자 하나하나 소수여부를 판단하는 방식을 버리자. 어렸을 때 배운 소수 찾아내는 방법이 생각 났다. 숫자를 쭉 적어놓고, 2의배수를 지운다. 그다음 3의 배수를 지운다. 이런 식으로 소수의 배수들을 지워나가면, 결국 소수들만 남을 것이다. 코드로 만들어 보자.
PROGRAM PRIME_NUM
IMPLICIT NONE
INTEGER I,J,MAX_NUM
LOGICAL PRIME(100000)
MAX_NUM=100000
DO I=1,MAX_NUM
PRIME(I)=.TRUE.
ENDDO
DO I=2,MAX_NUM
IF(PRIME(I).EQ..TRUE.) THEN
J=2
DO WHILE(I*J.LE.MAX_NUM)
PRIME(I*J)=.FALSE.
J=J+1
ENDDO
ENDIF
ENDDO
DO I=2,MAX_NUM
IF(PRIME(I).EQ..TRUE.) PRINT*,I
ENDDO
END
첫 번째 것보다 코드가 복잡하지도 않으면서 속도는 많이 빨라졌다. time명령어로 알아보니까 첫 번째 코드는 수행시간이 4.723 초가 나오고, 두 번째 코드는 0.043 초가 나온다. 대략 100배 정도 빠르다. 첫 번째 코드가 얼마나 쓰레기인지 알수 있다. ~.~;
요 넘을 이제 C코드로 만들어 보자.
#include <stdio.h>
int main()
{
int i,j,max_num;
int prime[100000];
max_num=100000;
for(i=1;i<=max_num;i++){
prime[i-1]=1;
}
for(i=2;i<=max_num;i++){
if(prime[i-1]==1){
j=2;
while(i*j<=max_num){
prime[i*j-1]=0;
j++;
}
}
}
for(i=2;i<=max_num;i++){
if(prime[i-1]==1) printf("%d\n",i);
}
return 0;
}
컴파일 해서 수행해보니, 0.032 초가 나온다. 포트란 컴파일러(pgf77)보다는 C 컴파일러(pgcc)가 최적화 성능이 좋은가 보다. gnu 계열 컴파일러는 더 느리게 나온다. cpu는 AMD 바로셀로나 칩 이란다.
이제 궁금한 점이 생겼다. 첫 번째 코드는 배터지게 욕먹을 코드라는 것이 증명되었고, 그럼 두 번째 코드는 어느 정도 좋은 성능을 발휘하는 것일까. google 에서 소수 구하는 fortran 코드를 구해보았다. 잘 안 찾아진다. 내가 검색을 잘 못하나보다. 그래서 그럴 듯한 C 코드 하나 긁어와 봤다.
#include <stdio.h>
#include <math.h>
int isPrime(unsigned int number);
void main(void) {
puts("2\n3");
for (unsigned int i = 5; i < 100000; 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;
}
요 작은 코드에 함수까지 구현하고, 변수 타입도 상황에 맞게 양수로만 정의하는 등, 일단 내가 만든 것 보다는 표면적으로 뭔가 있어보인다. 같은 컴파일러로 컴파일하여 같은 조건에서 수행해 보았다.
수행시간 0.049 초 나온다. 아마도 함수 호출 때문에 지연 시간이 조금 있는 것 같다. 뭐 아무튼 내가 만든 것과 큰 차이를 보이지 않는다. 다행이다.
먼저 fortran77로 구현해 보았다. 그 이유는 안타깝게도(?) fortran77이 나에게 가장 익숙한 언어이기 때문이다. 간단하게 제일 먼저 떠오른 생각은 소수의 정의이다. 어떤 자연수가 소수이기 위해서는 1과 자기 자신 이외로는 나누어 떨어지지 말아야 한다. 요넘을 그대로 적용해 보았다. 아주 단순 무식하게..
PROGRAM PRIME_NUM
IMPLICIT NONE
INTEGER PRIME(20000),I,J,L,MAX_NUM
LOGICAL N
MAX_NUM=100000
N=.TRUE.
L=3
PRIME(1)=1
PRIME(2)=2
PRINT*,PRIME(2)
DO I=3,MAX_NUM,2
DO J=2,L-1
IF(MOD(I,PRIME(J)).EQ.0) N=.FALSE.
ENDDO
IF(N.EQ..TRUE.) THEN
PRINT*,I
PRIME(L)=I
L=L+1
ENDIF
N=.TRUE.
ENDDO
END
100000까지의 자연수 중에 소수를 출력하는 코드이다. 1은 소수가 아니고 2는 소수라는 기본 정보를 넣고, 그 다음부터는 자신보다 작은 소수로 나누어 떨어지는지를 확인하고 소수면 출력하고 PRIME이란 배열에 넣어준다. PRIME이라는 배열은 다음 숫자의 소수여부를 판단할 때 사용한다.
얼핏보면 그럴 듯 하고, 맞는 결과를 출력하지만 예상대로 매우 느리다.
이쯤되면 생각의 전환이 필요하다. 숫자 하나하나 소수여부를 판단하는 방식을 버리자. 어렸을 때 배운 소수 찾아내는 방법이 생각 났다. 숫자를 쭉 적어놓고, 2의배수를 지운다. 그다음 3의 배수를 지운다. 이런 식으로 소수의 배수들을 지워나가면, 결국 소수들만 남을 것이다. 코드로 만들어 보자.
PROGRAM PRIME_NUM
IMPLICIT NONE
INTEGER I,J,MAX_NUM
LOGICAL PRIME(100000)
MAX_NUM=100000
DO I=1,MAX_NUM
PRIME(I)=.TRUE.
ENDDO
DO I=2,MAX_NUM
IF(PRIME(I).EQ..TRUE.) THEN
J=2
DO WHILE(I*J.LE.MAX_NUM)
PRIME(I*J)=.FALSE.
J=J+1
ENDDO
ENDIF
ENDDO
DO I=2,MAX_NUM
IF(PRIME(I).EQ..TRUE.) PRINT*,I
ENDDO
END
첫 번째 것보다 코드가 복잡하지도 않으면서 속도는 많이 빨라졌다. time명령어로 알아보니까 첫 번째 코드는 수행시간이 4.723 초가 나오고, 두 번째 코드는 0.043 초가 나온다. 대략 100배 정도 빠르다. 첫 번째 코드가 얼마나 쓰레기인지 알수 있다. ~.~;
요 넘을 이제 C코드로 만들어 보자.
#include <stdio.h>
int main()
{
int i,j,max_num;
int prime[100000];
max_num=100000;
for(i=1;i<=max_num;i++){
prime[i-1]=1;
}
for(i=2;i<=max_num;i++){
if(prime[i-1]==1){
j=2;
while(i*j<=max_num){
prime[i*j-1]=0;
j++;
}
}
}
for(i=2;i<=max_num;i++){
if(prime[i-1]==1) printf("%d\n",i);
}
return 0;
}
컴파일 해서 수행해보니, 0.032 초가 나온다. 포트란 컴파일러(pgf77)보다는 C 컴파일러(pgcc)가 최적화 성능이 좋은가 보다. gnu 계열 컴파일러는 더 느리게 나온다. cpu는 AMD 바로셀로나 칩 이란다.
이제 궁금한 점이 생겼다. 첫 번째 코드는 배터지게 욕먹을 코드라는 것이 증명되었고, 그럼 두 번째 코드는 어느 정도 좋은 성능을 발휘하는 것일까. google 에서 소수 구하는 fortran 코드를 구해보았다. 잘 안 찾아진다. 내가 검색을 잘 못하나보다. 그래서 그럴 듯한 C 코드 하나 긁어와 봤다.
#include <stdio.h>
#include <math.h>
int isPrime(unsigned int number);
void main(void) {
puts("2\n3");
for (unsigned int i = 5; i < 100000; 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;
}
요 작은 코드에 함수까지 구현하고, 변수 타입도 상황에 맞게 양수로만 정의하는 등, 일단 내가 만든 것 보다는 표면적으로 뭔가 있어보인다. 같은 컴파일러로 컴파일하여 같은 조건에서 수행해 보았다.
수행시간 0.049 초 나온다. 아마도 함수 호출 때문에 지연 시간이 조금 있는 것 같다. 뭐 아무튼 내가 만든 것과 큰 차이를 보이지 않는다. 다행이다.