배열을 이용한 기존 데이터형을 초과하는 크기의 수 출력/연산(피보나치)

Java에서 long 자료형은 2^64 의 크기를 가진다. 즉 양수 9,223,372,036,854,775,807부터 -9,223,372,036,854,775,808까지 출력할 수 있다는 얘기가 된다.

 

C, C++에서도 큰 자료형들은 이와 비슷하거나 미치지 못한다.

name	expresses	value*
CHAR_BIT	Number of bits in a char object (byte)	8 or greater*
SCHAR_MIN	Minimum value for an object of type signed char	-127 (-27+1) or less*
SCHAR_MAX	Maximum value for an object of type signed char	127 (27-1) or greater*
UCHAR_MAX	Maximum value for an object of type unsigned char	255 (28-1) or greater*
CHAR_MIN	Minimum value for an object of type char	either SCHAR_MIN or 0
CHAR_MAX	Maximum value for an object of type char	either SCHAR_MAX or UCHAR_MAX
MB_LEN_MAX	Maximum number of bytes in a multibyte character, for any locale	1 or greater*
SHRT_MIN	Minimum value for an object of type short int	-32767 (-215+1) or less*
SHRT_MAX	Maximum value for an object of type short int	32767 (215-1) or greater*
USHRT_MAX	Maximum value for an object of type unsigned short int	65535 (216-1) or greater*
INT_MIN	Minimum value for an object of type int	-32767 (-215+1) or less*
INT_MAX	Maximum value for an object of type int	32767 (215-1) or greater*
UINT_MAX	Maximum value for an object of type unsigned int	65535 (216-1) or greater*
LONG_MIN	Minimum value for an object of type long int	-2147483647 (-231+1) or less*
LONG_MAX	Maximum value for an object of type long int	2147483647 (231-1) or greater*
ULONG_MAX	Maximum value for an object of type unsigned long int	4294967295 (232-1) or greater*
LLONG_MIN	Minimum value for an object of type long long int	-9223372036854775807 (-263+1) or less*
LLONG_MAX	Maximum value for an object of type long long int	9223372036854775807 (263-1) or greater*
ULLONG_MAX	Maximum value for an object of type unsigned long long int	18446744073709551615 (264-1) or greater*

(출처: http://www.cplusplus.com/reference/climits/)

 

하지만 이 모든것이 표준을 지원하는 것은 아니기 때문에 큰 수를 표현하기에는 실질적으로 한계가 있는데 예를 들어 피보나치 수열을 구한다고 할 때, 100번 째 수까지 구하려면 어떻게 해야할까?

 

단순히 생각해보면 기존의 알고리즘을 그대로 이용하여 큰 자료형에 넣어서 출력하면 될 것이다.

 

 

#include <stdio.h>

void fibo(int n){
	if(n < 2){
		printf("%d\n", n);
		return;
	}
	printf("0\n1\n");
	int i;
	unsigned long long l = 0, r = 1, tmp;
	for(i=2;i<n;i++){
		tmp = l;
		l = r;
		r = tmp + r;
		printf("%d: %llu\n",i, r);
	}
}

int main()
{
	fibo(100);

	return 0;
}

 

위와 같이 소스코드를 작성해 보았다. 이는 단순히 반복문을 통하여 피보나치 수열을 구성한 것으로 void 함수 fibo에 매개변수로 몇 번째 피보나치 수까지 출력할 것인지를 지정하게 하였다. 편의를 위해 출력 서식등에는 큰 신경을 쓰지 않았으며 마음에 들지 않더라도 일단 진행해 보도록 하자.

 

 

피보나치를 10까지 구해본 결과 알맞게 나온 것을 볼 수 있다.(비교는 이곳 사이트를 참조하자)

크기를 조금 더 늘려본다면 어떨까? 50으로 진행해 보았다.

 

 

이번에도 정상적으로 출력된 것을 볼 수 있었다. 그렇다면 100번째 수 까지 출력해보도록 하자.

 

무언가 이상하지 않은가? 수열 특성상 이전 두 수의 합이 다음 수가 되는 만큼 크기는 갈수록 커져야 할 텐데 일일이 비교해 보지 않더라고 눈으로 보기에 숫자의 크기가 변하는 것을 볼 수 있다. 보통 이런 일이 일어나면 원인은 대부분, 거의 '오버플로우' 라고 할 수 있다.

 

제일 먼저 눈에 띄는 93~94번째 수를 위에서 언급한 사이트에서 찾아 비교해 보도록 하자.

 

 

7540113804746346429와 4660046610375530309를 더해서 12200160415121876738이 출력되는 것까지는 동일하다. 그렇다면

12200160415121876738과 7540113804746346429를 더한 19740274219868223167이 출력되었을까? 위의 소스 코드대로 짜여진 결과는 1293530146158671551. 12200160415121876738보다도 작은 값이 출력되었다.

 

오버플로우라고 하면 숫자가 계속 커지다가 음수로 출력되는 경우를 많이 보았을 테지만 코드에서는 unsigned long long으로 변수를 선언하였기에 음수가 나오지 않는 대신 약간 작은 값이 나오게 된다. 그냥 long long 변수로 컴파일하고 출력해보면 어떻게 될까?

 

 

음수가 출력되었다. 이로써 오버플로우가 발생되었다는 것은 명확해졌고 이제 남은 것은 더 큰 자료형을 찾아보는 것 뿐이다.

하지만 위에서 보여준 표에 따르면 2^64 범위를 넘는 자료형은 존재하지 않는다. 우리가 코드에서 사용한 자료형도 unsigned long long으로, 제일 큰 자료형을 사용했다. 하지만 당장 100번쨰 피보나치 수를 출력하려고 하면 218922995834555169026를 출력해야 하는데, 그렇다면 라이브러리를 사용하거나 다른 언어로 건너가야 할까?

 

단순히 피보나치 수열 출력을 위해서 그러는 건 에너지 낭비인 것 같다. 그렇다면 어떻게 해야 할까? 여기서 생각의 전환을 해보는 것이다.

중요한 시발점은 우리가 출력해야 할 수 자체를 하나의 정수로 보는 것이 아니라 문자열로 생각하는 것이다. C언어 학습 초기 때 다들 학생관리 프로그램이라고 해서 구조체에 학생의 이름, 생년월일, 전화번호 등을 묶어서 배열로 만들고 데이터를 입출력하는 예제를 만들어 본 경험이 있을 것이다.

그때 전화번호, 학번 등 긴 숫자를 정수형 변수에 저장하였는가? 나는 문자열(char 배열)에 저장하여 사용하였다. 이는 해당 데이터를 사칙연산이 필요한 수학적 데이터가 아니라 그냥 일련의 숫자로 표현된 문자열 같은 값으로 취급하는 것이다.

 

예를 들어 전화번호 01012345678을 저장한다고 하자. 우선 출력할 때부터 추가적인 작업이 필요하다. 왜냐면 맨 앞에 붙어있는 0은 자동적으로 출력이 되지 않기 때문이다. 물론 형식지정자를 사용해서 출력시킬 수 있겠지만 전화번호를 변경할 일이 온다면 어떨까? 가운데 자리를 변경하기 위해서 정수값 수십만을 가감해야 할까? 그런 것보다는 차라리 문자열 치환을 통해서 변경하는 것이 더욱 효과적일 것이다.

 

#include "fibonacci.h"
#define SIZE 30
#define TRUE 1
#define FALSE 0

void sumArr(int L[], int R[], int sum[]){
	int loopIndex, supp = 0;
	for(loopIndex = 0;loopIndex<SIZE;loopIndex++){
		sum[loopIndex] = L[loopIndex] + R[loopIndex] + supp;

		if (sum[loopIndex] > 9){
			sum[loopIndex] -= 10;
			supp = 1;
		}
		else{
			supp = 0;
		}
	}
}
void copyArr(int tgt[], int src[]){
	int loopIndex;
	for(loopIndex=0;loopIndex<SIZE;loopIndex++){
		tgt[loopIndex] = src[loopIndex];
	}
}
void printArr(int arr[], FILE* fp){
	int loopIndex;
	int trim = TRUE;
	for(loopIndex = SIZE-1;loopIndex>=0;loopIndex--){
		if(arr[loopIndex] != 0)	trim = FALSE;
		if(trim == FALSE) fprintf(fp, "%d", arr[loopIndex]);
	}
	fprintf(fp, "\n");
}
void fibo(int n){
	int numArrL[SIZE] = {0}, numArrR[SIZE] = {0}, numArrSum[SIZE] = {0}, numArrBuf[SIZE] = {0};

	numArrR[0] = 1;

	FILE *fp = fopen("output.txt", "w");
	fprintf(fp, "%d\n%d\n", 0, 1);

	int loopIndex;
	for(loopIndex = 0;loopIndex<n-2;loopIndex++){
		sumArr(numArrL, numArrR, numArrSum);
		copyArr(numArrBuf, numArrR); // tgt, src.
		copyArr(numArrR, numArrSum);
		copyArr(numArrL, numArrBuf);
		printArr(numArrSum, fp);
	}

	fclose(fp);
}

 

 

(※ 사실 이 포스팅을 하게 된 계기도 친구의 과제를 도와주다가 해결했던 경험을 기반으로 작성하였다. 그 과제가 바로 피보나치 수열 출력이었기 때문에 이 코드에선 곱셈, 나눗셈 등의 연산은 구현하지 않고 덧셈만 구현하였다. 곱셈, 나눗셈은 추후 업데이트 하도록 하겠다.)

 

위 코드는 최대 30자리까지 표현할 수 있다.

우선 각 함수의 동작을 알아보자.

 

1) void sumArr(int L[], int R[], int sum[])
이름에서 볼 수 있듯이 두 수를 더하는 함수다. 하지만 매개변수를 일반적인 숫자 자료형이 아닌 int형 배열로 받고 있다. 왜일까?
이는 각 수를 자릿수대로 배열에 집어넣는 것을 생각하면 된다.

이때 자릿수는 거꾸로 집어 넣는편이 좋다. 단순히 거꾸로 출력시키면 우리가 큰 자릿수부터 써내려가는 것처럼 출력을 할 수 있으므로 이 방법을 선택하였다. 즉 각 배열은 숫자의 자릿수들을 포함하고 있으니 하나의 숫자를 의미한다고 보면 된다. 세 번째 매개변수는 두 수의 합인데 이는 다른 방법을 사용해도 좋다.

 

2) void copyArr(int tgt[], int src[])

단순히 tgt 배열에서 src배열로 원소들을 복사하는 함수로, 피보나치 특성상 이전 값을 백업해 둬야 하기에 구현하였다.

 

3) void printArr(int arr[], FILE* fp)

배열을 전달받은 파일 포인터로 출력시킨다. 이는 과제의 목적이 텍스트 파일로 출력시키는 것이었기때문에 매개변수를 지정하였지만 단순히 출력을 원한다면 <stdio.h>에 있는 stdout을 전달하면 된다.

 

4) void fibo(int n)

피보나치 수열을 출력하는 함수를 구현하였다. 기존의 알고리즘에서 i, j 가 j, (i+j) 로 변하는 과정을 버퍼를 이용한 값 교환으로 구현한 것처럼 여기서는 sumArr, copyArr 등의 함수를 이용하여 구현하였는데 이때 sumArr 함수가 배열을 반환하지 않고 매개변수로 받기에 추가적인 배열이 필요하여 총 4개의 배열로 구현하게 되었다.

 

void sumArr(int L[], int R[], int sum[]){
	int loopIndex, supp = 0;
	for(loopIndex = 0;loopIndex<SIZE;loopIndex++){
		sum[loopIndex] = L[loopIndex] + R[loopIndex] + supp;

		if (sum[loopIndex] > 9){
			sum[loopIndex] -= 10;
			supp = 1;
		}
		else{
			supp = 0;
		}
	}
}

 

여기서 제일 중요한 위 함수의 동작을 보자.

자릿수를 거꾸로 배열에 입력한 덕분에 for문에서 인덱스를 0부터 시작하면서 계산하여 합배열에 낮은 자릿수부터 저장할 수 있게 되었다.

 

중요한 것은 각 자릿수를 더할 때 합이 10을 넘지 않는다면 좋겠지만, 넘는 경우의 처리다.

산수를 배울 때 10을 초과한 수는 다음 자릿수 위에 1을 더해주는 표시를 했던 것을 기억하는가? 여기서는 그 동작을 supp 라는 변수가 담당하고 있다. 초기에는 당연히 0으로 초기화를 해주고, 각 자릿수마다 루프를 돌면서 두 자릿수의 합을 계산한다.

그리고 분기문에 따라 10을 초과한다면 자릿수의 합에서 10을 빼고 supp는 1이 된다. 즉 다음 자릿수에 1을 더하는 것이다. 그렇지 않는다면 불필요한 자릿수 덧셈을 방지하기 위해 supp는 0으로 다시 지정해주고 계속 루프를 돈다. 이 supp는 다음 자릿수에서 두 수의 각 자릿수에 더해진다.

 

이 과정은 기초적인 덧셈 과정을 그대로 반영한 것이다. 직관적으로 이해하기도 쉬우며 배열의 크기에 따라 매우 큰 자릿수까지 표현할 수 있다. 이를 바탕으로 뺄셈은 쉽게 구현할 수 있을 것이며, 이중 for문과 충분히 큰 배열을 사용한다면 곱셈까지 구현할 수 있을 것이다. 나눗셈은 아직 확신이 없지만 분명 구현할 수 있으리라 생각한다.

 

결과는 다음과 같다.

 

서식의 부재로 비교해 보기 조금 어려울 수 있지만 아래쪽부터 비교해 보면 값이 정확하게 일치하는 것을 알 수 있다.