컴퓨터가 소수를 구하는 가장 빠른 연산 방법

Question

C언어는 오랜 역사를 갖고 있으며,

더 발전한 C++ 언어 역시 많은 곳에서 사용되고 있다.

특히 컴퓨터보다는 제한된 성능의 기계에서 사용하고는 한다.

보통 우리는 임베디드 시스템이라고 부른다.

임베디드 시스템에 적용하는 코드는 최적화가 절대적으로 필요하다.

왜냐하면, 컴퓨터처럼 성능이 좋은 것은 아니지마는

성능을 포기하지 않기 때문이다.

그러기에 코드 최적화를 통해서 코드 실행 시간을 단축할 필요가 있다.

코드 최적화라는 것은 쉽게 생각하면 메모리를 알맞게 사용하는 것이라고 보면 된다.

코드 최적화 방법에는 여러 가지가 있다.

그중에서 가장 기초가 되는 것이 나눗셈을 사용하지 않는 것이다.

인텔 Skylake cpu 를 기준으로 봤을 때,

나눗셈은 10 cycle의 연산이 필요하다면,

덧셈은 1 cycle 만에 처리가 된다.

즉, 덧셈 연산은 나눗셈 연산에 비해서 10배 빠르다고 한다.

(컴파일러마다 결과가 다를 수 있다.)

위와 같은 이유로 나눗셈은 코딩에 있어서 시간을 잡아먹는데 주된 범인이 될 수 있다.

나눗셈하면 또 부동소수점이 생각이 날 것이다.

float 와 double 자료형은 확실히 다른 int, short 자료형과 비교해서 많이 다르다.

메모리상에서도 많은 공간을 잡아먹기 때문에 최적화와는 거리가 멀다.

우리는 이런 float 과 double 자료형을 부동 소수점이라고 부른다.

부동 소수점은 수 체계에서 보면 유리수에 해당하는데,

유리수는 정수를 정수로 나눴을 때 생긴다.

일단 꼭 부동소수점의 연산이 필요한 것이 아니라면 정수형으로 만들어서 연산하는 것이 좋다.

예를 들면, *10, * 100 처럼 정수로 계산하면 메모리도 적게 잡아먹으며 연산속도도 보다 빠르게 된다.

실제로 얼마나 차이가 나는지 실제 코딩을 통해서 테스트해보도록 하자.

#include <stdio.h>
#include <time.h>

void main()
{
	clock_t start, end;
	float res;
	start = clock();

	int result;

	for (int i = 1; i <= 200000000; i++)
	{
		result = i/i;
	}

	end = clock();
	res = (float)(end - start) / CLOCKS_PER_SEC;

	printf("소요시간 : %.3f \n", res);
	return;
}

위는 나눗셈 연산을 사용한 코드이고,

컴퓨터 성능이 너무 좋아서

반복 횟수를 엄청 증가시켰다.

2억번... 반복시키기고 하였다.

결과는 0.713 초

몇 번을 더 실행시켜도 비슷한 수치가 나왔다.

#include <stdio.h>
#include <time.h>

void main()
{
	clock_t start, end;
	float res;
	start = clock();

	int result;

	for (int i = 1; i <= 200000000; i++)
	{
		result = i+i;
	}

	end = clock();
	res = (float)(end - start) / CLOCKS_PER_SEC;

	printf("소요시간 : %.3f \n", res);
	return;
}

이번에는 덧셈 연산을 사용한 코드이다.

나눗셈 연산과 똑같이 2억번 반복을 하도록 한다.

결과는 0.488 초

역시 여러번 실행시켜도 비슷한 수치가 나왔다.

앞서 말했듯이 속도가 10배 차이 나는 것은 이론적인 수치이고,

실제로 컴파일러에 따라 결과가 다르게 나온다는 것이다.

그리고 위의 두 결과는 Debug 모드에서 실행했기에 이런 차이가 발생한 것이고,

Release 모드로 실행하게 되면 시간 차이를 구할 수 없었다.

아무튼, 나눗셈은 덧셈 연산보다 느리다는 것을 확인할 수 있었다.

곱셈으로 바꿔주면 덧셈과 시간이 비슷하게 측정되었다.

나눗셈이 확실하게 다른 연산보다 느리다는 것을 확인할 수 있었다.

하지만 나눗셈이 꼭 필요한 때도 있다.

이런 경우에는 어떻게 나눗셈 연산을 사용해야 하는지 알아보자.

비트연산 중에 쉬프트 연산자를 이용하면 나눗셈 연산과 같은 결과를 얻을 수 있다.

아두이노를 사용하는 경우 아날로그 신호를 읽으면 0~1023 신호를 읽을 수 있다.

10 bit 의 크기인데,

우리는 C언어에서 10bit 의 자료형을 배운 적이 없다.

8bit, 즉 1byte 의 크기인 char 자료형을 많이 다뤄봤었다.

아두이노 신호를 변수에 저장할 때 10bit를 저장하기 위해 int 자료형을 사용했다면

32bit 에서 10bit 를 뺀 22bit 메모리 공간을 낭비하게 되는 것이다.

아두이노 신호를 8 bit로 만들려면 센서값에서 4를 나누면 된다.

0~1023 의 센서 값 범위가 0~255 로 변하게 된다.

여기서 우리는 나눗셈을 사용한다면 속도저하가 생긴다는 것을 알았으므로 나누기보다 다른 방법을 선택해야 한다.

이때 쉬프트 연산자를 이용하는 것이다.

10bit 를 8bit 로 만들려면 ( 4로 나누려면)

오른쪽으로 쉬프트 연산을 2번 하면 된다.

예를 들어, 1013 의 센서값이 읽혔다고 하자, 4로 나눈 결과값은 253 이 된다.

이진수로 표현하자면 1013 = 11 1111 0101 , 이므로

쉬프트 연산을 오른쪽으로 2번 적용하면 이진수로 1111 1101 이 된다.

십진수로 읽으면 253 으로, 센서값을 4로 나눈 결과값과 같다는 것을 확인할 수 있다.

이런 방식으로 쉬프트연산을 사용한다면 나눗셈을 이용하지 않고도 나눗셈 결과를 얻을 수 있을뿐더러

컴퓨터 메모리 친화적인 연산을 사용하여 최적화할 수 있다.

마찬가지로 코드로 테스트를 진행해보도록 하겠다.

#include <stdio.h>
#include <time.h>



void main()
{
	clock_t start, end;
	float res;
	start = clock();

	int result;

	for (int i = 1; i <= 20000; i++)
	{
		result = i/4;
		printf("%d", result);
	}



	end = clock();
	res = (float)(end - start) / CLOCKS_PER_SEC;

	printf("\n소요시간 : %.3f \n", res);
	return;
}

나눗셈을 이용한 결과이며,

연산처리에 걸린 시간은 1.584초 이다.

#include <stdio.h>
#include <time.h>



void main()
{
	clock_t start, end;
	float res;
	start = clock();

	int result;

	for (int i = 1; i <= 20000; i++)
	{
		result = i>>2;
		printf("%d", result);
	}



	end = clock();
	res = (float)(end - start) / CLOCKS_PER_SEC;

	printf("\n소요시간 : %.3f \n", res);
	return;
}

쉬프트 연산을 이용한 결과이다.

연산처리에 걸린 시간은 1.472초 이다.

시간 차이가 거의 없긴 하다.

하지만 미세하게 쉬프트 연산이 더 빠른 것을 볼 수 있다.

컴파일러가 똑똑해 지면서 이런 부분에서는 차이가 없어진 것이 아닌가 싶다.

그래도 쉬프트 연산이 더 빨라야 하는 것이 이론적으로도 맞고, 실제로도 빠른 것을 확인할 수 있었다.

* 최적화가 꼭 필요하고 유의미한 결과를 가져온다면 코드 최적화를 하고,

그렇지 않으면 큰 의미가 없으므로 굳이 최적화를 하지 않아도 될 듯 하다.

컴퓨터가 소수를 구하는 가장 빠른 연산 방법 방법