BigUInt

BigUInt.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

public class BigUInt
{
	string number;

	static readonly int half = Math.Sqrt(ulong.MaxValue).ToString().Length - 1;

	BigUInt(string number) { this.number = number; }

	public BigUInt() : this("0") { }

	public override string ToString() { return number; }

	public static BigUInt Parse(string s)
	{
		if (Regex.Match(s, "\\D").Success)
			throw new FormatException("Input string was not in a correct format.");

		return new BigUInt(s);
	}

	public static BigUInt Pow(uint x, uint y)
	{
		ulong cutoff = ulong.MaxValue / x;
		ulong sum = 1;
		uint maxPow;
		for (maxPow = 0; maxPow < y && sum <= cutoff; maxPow++)
			sum *= x;

		string maxSum = sum.ToString();
		BigUInt bigUInt = new BigUInt();
		bigUInt.number = maxSum;
		var shortcuts = new Dictionary<uint, BigUInt>();
		shortcuts[maxPow] = bigUInt;
		uint count = maxPow;
		while (count < y)
		{
			uint square = count * 2;
			if (square < y)
			{
				bigUInt = Multiply(bigUInt, bigUInt);
				count = square;
				shortcuts[count] = bigUInt;
				continue;
			}

			foreach (var kvp in shortcuts.Reverse())
				if (kvp.Key < y - count)
				{
					bigUInt = Multiply(bigUInt, kvp.Value);
					count += kvp.Key;
					continue;
				}

			bigUInt = Multiply(bigUInt, Pow(x, y - count));
			count = y;
		}

		return bigUInt;
	}

	public static BigUInt Multiply(params BigUInt[] multiplicands)
	{
		if (multiplicands.Length > 2)
			return Multiply(multiplicands[0], Multiply(multiplicands.Skip(1).ToArray()));

		Func<string, List<long>> split = s =>
		{
			var list = new List<long>();
			while (s != "")
			{
				int length = s.Length - Math.Min(half, s.Length);
				list.Add(long.Parse(s.Substring(length)));
				s = s.Substring(0, length);
			}
			return list;
		};

		var allList = new List<BigUInt>();
		List<long> leftList = split(multiplicands[0].ToString()), rightList = split(multiplicands[1].ToString());
		StringBuilder sb = new StringBuilder();
		for (int l = 0; l < leftList.Count(); l++)
			for (int r = 0; r < rightList.Count(); r++)
			{
				sb.Length = 0;
				for (int i = 0; i < l + r; i++)
					for (int j = 0; j < half; j++)
						sb.Append("0");
				allList.Add(new BigUInt((leftList[l] * rightList[r]) + sb.ToString()));
			}

		return Add(allList.ToArray());
	}

	public static BigUInt Add(params BigUInt[] addends)
	{
		StringBuilder sb = new StringBuilder();
		long remainder = 0;
		IEnumerable<BigUInt> remaining;
		for (int part = 1; (remaining = addends.Where(p => p.ToString().Length > half * (part - 1))).Any() || remainder != 0; part++)
		{
			long sum = remainder;
			foreach (BigUInt addend in remaining)
			{
				Func<int, int> index = i => addend.ToString().Length - Math.Min(half * i, addend.ToString().Length);
				sum += long.Parse(addend.ToString().Substring(index(part), Math.Min(half, index(part - 1))));
			}
			string s = sum.ToString("D" + (half + 1));
			remainder = long.Parse(s.Substring(0, s.Length - half));
			sb.Insert(0, s.Substring(s.Length - half));
		}
		return new BigUInt(sb.ToString().TrimStart('0'));
	}
}