Code:
using System;
using System.Windows.Forms;
namespace LargeNumbers
{
static public class Program
{
static public void Main()
{
DateTime time = DateTime.Now;
Blob num = new Blob(3).Pow(300);
Console.WriteLine(num.ToString());
DateTime time2 = DateTime.Now;
Console.WriteLine();
Console.WriteLine("ms: " + (time2 - time).TotalMilliseconds);
Console.ReadKey();
}
}
public class Blob
{
public const int Size = 512;
static private readonly ulong[] Potency =
{
0x1,0x2,0x4,0x8,0x10,0x20,0x40,0x80,0x100,0x200,0x400,0x800,0x1000,0x2000,0x4000,0x8000,0x10000,0x20000,0x40000,0x80000,0x100000,0x200000,0x400000,0x800000,
0x1000000,0x2000000,0x4000000,0x8000000,0x10000000,0x20000000,0x40000000,0x80000000,0x100000000,0x200000000,0x400000000,0x800000000,0x1000000000,
0x2000000000,0x4000000000,0x8000000000,0x10000000000,0x20000000000,0x40000000000,0x80000000000,0x100000000000,0x200000000000,0x400000000000,0x800000000000,
0x1000000000000,0x2000000000000,0x4000000000000,0x8000000000000,0x10000000000000,0x20000000000000,0x40000000000000,0x80000000000000,0x100000000000000,
0x200000000000000,0x400000000000000,0x800000000000000,0x1000000000000000,0x2000000000000000,0x4000000000000000,0x8000000000000000,
};
static public Blob MinValue
{
get
{
Blob ret = new Blob();
ret.Raw[0] = true;
ret.Raw[Size - 1] = true;
return ret;
}
}
static public Blob MaxValue
{
get
{
Blob ret = new Blob();
for (int i = 1; i < Size; i++)
{
ret.Raw[i] = true;
}
return ret;
}
}
private bool[] Raw;
public bool this[int index]
{
get
{
if (index < 0 || index >= Size) throw new IndexOutOfRangeException();
return Raw[index];
}
set
{
if (index < 0 || index >= Size) throw new IndexOutOfRangeException();
Raw[index] = value;
}
}
public Blob()
{
Raw = new bool[Size];
}
public Blob(long number)
{
Raw = new bool[Size];
if (number >= 0)
{
for (int i = 0; i < 64; i++)
{
Raw[Size - 64 + i] = (Convert.ToUInt64(number) & Potency[63 - i]) > 0;
}
}
else
{
number = ~number;
for (int i = 0; i < 64; i++)
{
Raw[Size - 64 + i] = (Convert.ToUInt64(number) & Potency[63 - i]) > 0;
}
Raw = (~this).Raw;
}
}
private Blob(bool[] raw)
{
Raw = raw;
}
static public Blob Parse(string decimalNumber)
{
return Parse(decimalNumber, NumberFormat.Decimal);
}
static public Blob Parse(string number, NumberFormat format)
{
Blob ret = new Blob();
switch (format)
{
case NumberFormat.Binary:
for (int i = number.Length - 1; i >= 0; i--)
{
switch (number[number.Length - i - 1])
{
case '0':
break;
case '1':
ret.Raw[Size - i - 1] = true;
break;
default:
throw new FormatException();
}
}
break;
case NumberFormat.Decimal:
bool neg = number.StartsWith("-");
if (neg) number = number.Substring(1);
Blob p = 1;
Blob ten = 10;
for (int i = number.Length - 1; i >= 0; i--, p *= ten)
{
if (number[i] < 48 || number[i] > 57) throw new FormatException();
ret += new Blob(Convert.ToInt64(number[i] - 48)) * p;
}
if (neg) ret = -ret;
break;
case NumberFormat.Hexadecimal:
number = number.ToLower();
for (int i = number.Length - 1; i >= 0; i--)
{
char cur = number[number.Length - i - 1];
int cur2 = 0;
if (cur > 47 && cur < 58)
{
cur2 = cur - 48;
}
else if (cur > 96 && cur < 103)
{
cur2 = cur - 87;
}
else
{
throw new FormatException();
}
for (int a = 0; a < 4; a++)
{
ret.Raw[Size - 4 - i * 4 + a] = (Convert.ToUInt32(cur2) & Potency[3 - a]) > 0;
}
}
break;
}
return ret;
}
public override string ToString()
{
return ToString(NumberFormat.Decimal);
}
public string ToString(NumberFormat format)
{
string ret = "";
switch (format)
{
case NumberFormat.Binary:
foreach (bool bo in Raw)
{
ret += bo ? 1 : 0;
}
break;
case NumberFormat.Decimal:
Blob num = Clone();
bool neg = Raw[0];
if (neg) num = -num;
bool m0, m1, m2, m3, m4;
while (num > 0)
{
m0 = false; m1 = false; m2 = false; m3 = false; m4 = false;
for (int i = 0; i < Size; i++)
{
m0 = m1; m1 = m2; m2 = m3;
m3 = m4; m4 = num.Raw[0];
for (int a = 0; a < Size - 1; a++) num.Raw[a] = num.Raw[a + 1];
num.Raw[Size - 1] = false;
bool bigger = true;
if (m0) bigger = true;
else if (!m1) bigger = false;
else if (m2) bigger = true;
else if (!m3) bigger = false;
if (bigger)
{
bool car = m3;
m3 = !m3;
if (m2)
{
m2 = car;
car = true;
}
else
{
m2 = !car;
}
m1 ^= car;
bool b = true;
for (int a = Size - 1; a >= 0 && b; a--)
{
b = num.Raw[a];
num.Raw[a] = true;
}
}
}
int rem2 = Convert.ToInt32(m4);
if (m3) rem2 += 2;
if (m2) rem2 += 4;
if (m1) rem2 += 8;
ret = rem2 + ret;
}
if (ret.Length == 0) ret = "0";
if (neg) ret = "-" + ret;
break;
case NumberFormat.Hexadecimal:
for (int i = 0; i < Size / 8; i++)
{
int by = 0;
for (int a = 0; a < 8; a++)
{
if (Raw[i * 8 + a]) by += 1 << 7 - a;
}
ret += by.ToString("x2");
}
break;
}
return ret;
}
public override int GetHashCode()
{
return 0;
}
public override bool Equals(object obj)
{
return false;
}
public Blob Clone()
{
return new Blob((bool[])Raw.Clone());
}
static public Blob operator +(Blob num1, Blob num2)
{
Blob ret = num1.Clone();
bool[] raw1 = ret.Raw, raw2 = num2.Raw;
bool car = false;
for (int i = Size - 1; i >= 0; i--)
{
if (raw1[i] ^ raw2[i])
{
raw1[i] = !car;
}
else if (raw1[i] && raw2[i])
{
raw1[i] = car;
car = true;
}
else
{
raw1[i] = car;
car = false;
}
}
return ret;
}
static public Blob operator ++(Blob num)
{
bool b = true;
for (int i = Size - 1; i >= 0 && b; i--)
{
b = num.Raw[i];
num.Raw[i] = !num.Raw[i];
}
return num;
}
static public Blob operator -(Blob num1, Blob num2)
{
return num1 + ~num2 + 1;
}
static public Blob operator -(Blob num)
{
return ~num + 1;
}
static public Blob operator --(Blob num)
{
num -= 1;
return num;
}
static public Blob operator *(Blob num1, Blob num2)
{
Blob res = new Blob();
for (int i = 0; i < Size; i++)
{
if (num2.Raw[i]) res += num1 << Size - i - 1;
}
return res;
}
static public Blob operator /(Blob dividend, Blob divisor)
{
if (divisor == 0) throw new DivideByZeroException();
Blob num1 = dividend.Clone(), num2 = divisor.Clone();
bool n1s = num1.Raw[0], n2s = num2.Raw[0];
if (n1s) num1 = -num1;
if (n2s) num2 = -num2;
Blob mod = new Blob();
for (int i = 0; i < Size; i++)
{
mod <<= 1;
if (num1.Raw[0]) mod.Raw[Size - 1] = true;
num1 <<= 1;
if (mod >= num2)
{
mod -= num2;
num1++;
}
}
return n1s ^ n2s ? -num1 : num1;
}
static public Blob operator %(Blob dividend, Blob divisor)
{
if (divisor == 0) throw new DivideByZeroException();
Blob num1 = dividend.Clone(), num2 = divisor.Clone();
bool n1s = num1.Raw[0], n2s = num2.Raw[0];
if (n1s) num1 = -num1;
if (n2s) num2 = -num2;
Blob mod = new Blob();
for (int i = 0; i < Size; i++)
{
mod <<= 1;
if (num1.Raw[0]) mod.Raw[Size - 1] = true;
num1 <<= 1;
if (mod >= num2)
{
mod -= num2;
num1++;
}
}
return mod;
}
static public Blob operator <<(Blob num1, int num2)
{
if (num2 < 0) return num1 >> -num2;
num2 %= Size;
Blob ret = new Blob();
bool[] raw = ret.Raw;
for (int i = 0; i < Size; i++)
{
int p = i + num2;
if (p < 0)
{
raw[i] = num1.Raw[0];
}
else if (p >= Size)
{
raw[i] = false;
}
else
{
raw[i] = num1.Raw[p];
}
}
return ret;
}
static public Blob operator >>(Blob num1, int num2)
{
if (num2 < 0) return num1 << -num2;
num2 %= Size;
Blob ret = new Blob();
bool[] raw = ret.Raw;
for (int i = 0; i < Size; i++)
{
int p = i - num2;
if (p < 0)
{
raw[i] = num1.Raw[0];
}
else if (p >= Size)
{
raw[i] = false;
}
else
{
raw[i] = num1.Raw[p];
}
}
return ret;
}
static public Blob operator ~(Blob num)
{
Blob ret = new Blob();
for (int i = 0; i < Size; i++)
{
ret.Raw[i] = !num.Raw[i];
}
return ret;
}
static public Blob operator |(Blob num1, Blob num2)
{
Blob ret = new Blob();
for (int i = 0; i < Size; i++)
{
ret.Raw[i] = num1.Raw[i] | num2.Raw[i];
}
return ret;
}
static public Blob operator &(Blob num1, Blob num2)
{
Blob ret = new Blob();
for (int i = 0; i < Size; i++)
{
ret.Raw[i] = num1.Raw[i] & num2.Raw[i];
}
return ret;
}
static public Blob operator ^(Blob num1, Blob num2)
{
Blob ret = new Blob();
for (int i = 0; i < Size; i++)
{
ret.Raw[i] = num1.Raw[i] ^ num2.Raw[i];
}
return ret;
}
static public bool operator ==(Blob num1, Blob num2)
{
for (int i = 0; i < Size; i++)
{
if (num1.Raw[i] != num2.Raw[i]) return false;
}
return true;
}
static public bool operator !=(Blob num1, Blob num2)
{
for (int i = 0; i < Size; i++)
{
if (num1.Raw[i] != num2.Raw[i]) return true;
}
return false;
}
static public bool operator >(Blob num1, Blob num2)
{
if (num1.Raw[0] && !num2.Raw[0])
{
return false;
}
else if (!num1.Raw[0] && num2.Raw[0])
{
return true;
}
else
{
for (int i = 1; i < Size; i++)
{
if (num1.Raw[i] != num2.Raw[i]) return num1.Raw[i] && !num2.Raw[i];
}
return false;
}
}
static public bool operator <(Blob num1, Blob num2)
{
if (num1.Raw[0] && !num2.Raw[0])
{
return true;
}
else if (!num1.Raw[0] && num2.Raw[0])
{
return false;
}
else
{
for (int i = 1; i < Size; i++)
{
if (num1.Raw[i] != num2.Raw[i]) return !num1.Raw[i] && num2.Raw[i];
}
return false;
}
}
static public bool operator >=(Blob num1, Blob num2)
{
return num1 > num2 || num1 == num2;
}
static public bool operator <=(Blob num1, Blob num2)
{
return num1 < num2 || num1 == num2;
}
static public implicit operator Blob(long num)
{
return new Blob(num);
}
public Blob Pow(uint pow)
{
Blob ret = 1;
Blob p = Clone();
int to = 0;
for (int i = 32; i >= 0; i--)
{
if ((pow & Potency[i]) > 0)
{
to = i + 1;
break;
}
}
for (int i = 0; i < to; i++)
{
if ((pow & Potency[i]) > 0)
{
ret *= p;
}
p *= p;
}
return ret;
}
}
public enum NumberFormat
{
Binary, Decimal, Hexadecimal
}
}