큰 정수 계산하기

정말 오랫만에 C / C++ 코딩을 하게 되었다.

long long 보다 큰, 아니 long 보다 큰 자료형을 거의 쓸일이 없었는데, 최근 불어닥치고 있는 소프트웨어 능력 평가로 인해 정말 오랫만에 C/C++로 코딩을 하고 있다.

문제자체는 쉬운데, 큰 정수를 다뤄야 하는 부분도 있어서 곰곰히 생각해보다가 매우 간단하게 long long의 곱셉이 가능하도록 급하게 만들어봤다.

999의 9승을 계산하는 긴급하게 만든 코드이므로 최적화나 다양한 테스트를 해보지는 못한 코드이다.

#include <stdio.h>

#define MAX_MODULO 100000000LL


typedef struct _BigNumber {
	long long quad;
	long long head;
	long long tail;
} BigNumber;

void toString(BigNumber a) {
	if (a.quad != 0) {
		printf("%lld", a.quad);		
		printf("%08lld", a.head);	
		printf("%08lld\n", a.tail);
	}else if (a.head != 0) {
		printf("%lld", a.head);
		printf("%08lld\n", a.tail);
	}else {
		printf("%lld\n", a.tail);
	}	
}

BigNumber multiply(BigNumber a, BigNumber b) {	
	BigNumber result;	
	result.quad = a.head*b.head + a.quad*b.tail + b.quad*a.tail;
	result.head = a.head * b.tail + a.tail * b.head;
	result.tail = a.tail*b.tail;	
	result.head += result.tail / MAX_MODULO;
	result.tail = result.tail % MAX_MODULO;
	result.quad += result.head / MAX_MODULO;
	result.head = result.head % MAX_MODULO;
	return result;
}

BigNumber add(BigNumber a, BigNumber b) {
	BigNumber result;
	result.quad = a.quad + b.quad;
	result.head = a.head + b.head;
	result.tail = a.tail + b.tail;
	result.head += result.tail / MAX_MODULO;
	result.tail = result.tail % MAX_MODULO;
	result.quad += result.head / MAX_MODULO;
	result.head = result.head % MAX_MODULO;
	return result;
}

BigNumber power(BigNumber a, int b) {
	BigNumber result;
	result.quad = a.quad;
	result.head = a.head;
	result.tail = a.tail;

	if (b == 0){
		result.quad = 0;
		result.head = 0;
		result.tail = 1;
		return result;
	}		

	if (b == 1) {
		return result;
	}

	for (int i = 1; i < b; i++) {
		result = multiply(result, a);		

	}
	return result;
}

int main() {
	BigNumber test;
	test.quad = 0;
	test.head = 0;
	test.tail = 999;
	toString(power(test, 9));
	return 0;
}