arbitary precision multiplication and power-raising

apmult.cc

#include <iostream>
#include <deque>
#include <iterator>

namespace tue
{
	// 10-based arbitary precision number
	struct arbitary_precision
	{
		struct one  {};
		struct zero {};

		arbitary_precision() = default;
		arbitary_precision(int n, int e) : man(n, '0'), exp{e} {}
		arbitary_precision(one ) : man{'1'}, exp{0} {}
		arbitary_precision(zero) : man{'0'}, exp{0} {}

		arbitary_precision& operator *= (arbitary_precision const& x);

	private:
		std::deque<char> man;
		int exp;

		void normalize();

		friend std::istream& operator >> (std::istream& i, arbitary_precision      & ap);
		friend std::ostream& operator << (std::ostream& o, arbitary_precision const& ap);
		friend arbitary_precision operator * (arbitary_precision const& a, arbitary_precision const& b);
	};

	namespace
	{
		bool is_blank(char x) { return (x == ' ' || x == '\t' || x == '\n'); }
		bool is_digit(char x) { return ('0' <= x && x <= '9'); }

		template <class PREDICATE>
		void ignore_if(std::istream& i, PREDICATE pred)
		{
			while (i && pred(i.peek()))
				i.ignore();
		}

		template <class PREDICATE, class OUTPUT_IT>
		void read_if(std::istream& i, PREDICATE pred, OUTPUT_IT out)
		{
			for (char ch; i && pred(ch = i.peek()); *out++ = ch, i.ignore()) {}
		}
	}

	std::istream& operator >> (std::istream& i, arbitary_precision& ap)
	{
		arbitary_precision x;

		ignore_if(i, is_blank);
		read_if(i, is_digit, std::back_inserter(x.man));
		int nfloor = x.man.size();

		if (i.peek() == '.') {
			i.ignore();
			read_if(i, is_digit, std::back_inserter(x.man));
		}
		x.exp = nfloor - x.man.size();

		x.normalize();
		std::swap(x, ap);
		return i;
	}

	std::ostream& operator << (std::ostream& o, arbitary_precision const& ap)
	{
		std::copy(ap.man.begin(), ap.man.end() + ap.exp, std::ostream_iterator<char>(o));
		if (ap.exp) {
			o << '.';
			std::copy(ap.man.end()+ap.exp, ap.man.end(), std::ostream_iterator<char>(o));
		}

		return o;
	}

	void arbitary_precision::normalize()
	{
		// remove leading zero
		while (exp + man.size() > 1 && man.front() == '0')
			man.pop_front();

		// add leading zero
		std::fill_n(std::front_inserter(man), 1 - (exp + static_cast<int>(man.size())), '0');

		// remove trailing zero
		while (exp < 0 && man.back() == '0') {
			man.pop_back();
			exp++;
		}
	}

	arbitary_precision operator * (arbitary_precision const& a, arbitary_precision const& b)
	{
		arbitary_precision r{static_cast<int>(a.man.size() + b.man.size()), a.exp + b.exp};

		auto rofirst = r.man.rbegin();
		for (auto ib = b.man.rbegin(); ib != b.man.rend(); ++ib, ++rofirst) {
			auto io = rofirst;
			for (auto ia = a.man.rbegin(); ia != a.man.rend(); ++ia, ++io) {
				auto x = (*ib - '0') * (*ia - '0') + (*io - '0');
				io[0] = x % 10 + '0';
				io[1] = x / 10 + io[1];
			}
		}

		r.normalize();
		return std::move(r);
	}

	arbitary_precision& arbitary_precision::operator *= (arbitary_precision const& x)
	{
		return (*this = std::move(*this * x));
	}

	arbitary_precision pow(arbitary_precision const& ap, int n)
	{
		if (n == 0) return arbitary_precision{arbitary_precision::one{}};
		if (n == 1) return ap;
		if (n == 2) return ap*ap;
		if (n == 3) return ap*ap*ap;
		auto r = pow(ap, n/2);
		if (n & 1) return r*r*ap;
		return r*r;
	}
}

int main()
{
	tue::arbitary_precision x;
	int n;
	std::cin >> x >> n;
	std::cout << pow(x, n) << std::endl;
}