BigNumber.cpp

#include "BigNumber.h"

#include <vector>
#include <algorithm>

using namespace std;

BigNumber::BigNumber(){
}
BigNumber::BigNumber(int n){
	set(n);
}
BigNumber::BigNumber(const string &n){
	set(n);
}
BigNumber::~BigNumber(){
}

void BigNumber::set(int n){
	while(n){
		ary.push_back(n % 10);
		n /= 10;
	}
}
void BigNumber::set(const std::string &n){
	for(auto c : n){
		ary.push_front(c - '0');
	}
}

void BigNumber::push_front(char c){
	ary.push_front(c);
}
void BigNumber::push_back(char c){
	ary.push_back(c);
}
void BigNumber::shift(int n){
	for(int i=0;i<n;i++)
		push_front(0);
}

char BigNumber::operator[](const int &n) const{
	if(length() <= n)
		return 0;
	else
		return ary[n];
}
int BigNumber::length() const{
	return ary.size();
}

bool BigNumber::test(const BigNumber &o) const{
	int to = max(length(), o.length());

	for(int i=to-1;i>=0;i--){
		if((*this)[i] < o[i])
			return true;
		else if((*this)[i] > o[i])
			return false;
	}
	return true;
}
BigNumber BigNumber::add(const BigNumber &o) const{
	BigNumber dst;

	int to = max(length(), o.length());
	int save = 0;

	for(int i=0;i<to;i++){
		int result =
			(*this)[i] + o[i] + save;

		if(result >= 10)
			result %= 10, save = 1;
		else
			save = 0;

		dst.push_back(result);
	}
	if(save)
		dst.push_back(save);

	return dst;
}
BigNumber BigNumber::sub(const BigNumber &o) const{
	BigNumber dst;

	int to = max(length(), o.length());
	int save = 0;

	for(int i=0;i<to;i++){
		int result =
			(*this)[i] - o[i] - save;

		if(result < 0)
			result = 10 + result, save = 1;
		else
			save = 0;

		dst.push_back(result);
	}

	return dst;
}
BigNumber BigNumber::mul(const BigNumber &o) const{
	BigNumber dst;
	vector<BigNumber> numbers;

	for(int i=0;i<o.length();i++){
		int save = 0;
		BigNumber local;

		for(int j=0;j<length();j++){
			int result =
				(*this)[j] * o[i] + save;

			if(result >= 10)
				save = result / 10, result %= 10;
			else
				save = 0;

			local.push_back(result);
		}
		if(save)
			local.push_back(save);

		local.shift(i);
		numbers.push_back(local);
	}

	for(auto &number : numbers){
		dst = dst.add(number);
	}

	return dst;
}

BigNumber BigNumber::pow(const BigNumber &o) const{
	BigNumber dst = *this;
	BigNumber m = o;
	
	while(m.test(1) == false){
		m = m.sub(1);

		dst = dst.mul(*this);
	}

	return dst;
}
BigNumber BigNumber::mod(const BigNumber &o) const{
	BigNumber dst = *this;

	while(dst.test(o) == false){
		dst = dst.sub(o);
	}

	return dst;
}

void BigNumber::print() const{
	for(auto it=ary.rbegin();it!=ary.rend();++it)
		printf("%d", *it);
}

BigNumber.h

#pragma once

#include <string>
#include <deque>

class BigNumber{
public:
	BigNumber();
	BigNumber(int n);
	BigNumber(const std::string &n);
	virtual ~BigNumber();

	char operator [](const int &n) const;
	int length() const;

	/* this - o가 0이나 음수이면 1, 양수이면 0 */
	bool test(const BigNumber &o) const;

	BigNumber add(const BigNumber &o) const;
	BigNumber sub(const BigNumber &o) const;
	BigNumber mul(const BigNumber &o) const;
	//BigNumber div(const BigNumber &o);

	BigNumber pow(const BigNumber &o) const;
	BigNumber mod(const BigNumber &o) const;

	void print() const;

protected:
	void set(int n);
	void set(const std::string &n);
	
	void push_front(char c);
	void push_back(char c);
	void shift(int n);

	/* 필요없는 0 제거 */
	//void trim();

private:
	std::deque<char> ary;
};

main.cpp

#include "stdafx.h"

#include "BigNumber.h"

int _tmain(int argc, _TCHAR* argv[]){
	BigNumber n1("3");
	BigNumber n2("1993");

	BigNumber n3("123456789");
	BigNumber n4("1234567");

	BigNumber n5(3);

	//n3.mul(n4).print();

	n3.mod(n4).print();



	/*
	BigNumber m1("2");
	BigNumber m2("44");

	m1.pow(m2).print();
	*/
	return 0;
}