## A Custom Big Integer for Large Factorials

While eating lunch one day, I wondered how hard it’d be to write a lightweight custom big integer class so that I could compute large factorials. On most computers, the largest integer is 2^31 – 1 = 2,147,483,647. So you can only calculate up to 12! = 12 * 11 * . . * 1 = 479,001,600 because 13! is 6,227,020,800.

In C#, a BigInteger type was introduced a few years ago, but some languages don’t have such a type. I explored the idea of a custom big integer using C#.

Anyway, I defined a MyBigInt type that is just a List of int — a list of single integers. (I could have used a List of byte because each item in the list is just a single digit).

Next I coded up a method to add two custom big integers (no negative values allowed for simplicity). Then I coded up a method to multiply two custom big integers, which used the add method. Then I used the add and multiply methods to code up a factorial that can do arbitrarily large values.

If I ever want to code a big factorial function in some language that doesn’t have a big integer type, I can now do so.

```using System;
using System.Collections.Generic;
namespace MyBigIntDemo
{
class Program
{
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin lightweight big int demo \n");
Console.WriteLine(int.MaxValue);

MyBigInt x = new MyBigInt("12345678901234567890");
Console.WriteLine("x = " + x.ToString());

MyBigInt y = new MyBigInt("300");
Console.WriteLine("y = " + y.ToString());

MyBigInt z = MyBigInt.Sum(x, y);
MyBigInt p = MyBigInt.Product(x, y);

Console.WriteLine("\nsum of x and y     = " + z.ToString());
Console.WriteLine("\nproduct of x and y = " + p.ToString());

int n = 30;
MyBigInt nf = MyBigInt.Factorial(n);
Console.WriteLine("\n" + n + "! = " + nf);

Console.WriteLine("\nEnd demo \n");
Console.ReadLine();
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
Console.ReadLine();
}

} // Main

} // class Program

public class MyBigInt
{
public List<int> data;

public static MyBigInt Factorial(int n)
{
MyBigInt ans = new MyBigInt("1");
for (int i = 1; i < n; ++i)
{
MyBigInt ii = new MyBigInt(i.ToString());
ans = MyBigInt.Sum(ans, MyBigInt.Product(ans, ii));
}
return ans;
}

public MyBigInt(string s)
{
this.data = new List<int>();
int n = s.Length;
for (int i = n - 1; i ≥ 0; --i)
{
char c = s[i];
this.data.Add(int.Parse(c.ToString()));
}
}

public MyBigInt()
{
this.data = new List<int>();
}

public static MyBigInt Sum(MyBigInt x, MyBigInt y)
{
int n = x.data.Count;
if (y.data.Count > n)
n = y.data.Count;

MyBigInt result = new MyBigInt();
int xx = 0;
int yy = 0;
int carry = 0;
for (int i = 0; i < n; ++i)
{
if (i > x.data.Count - 1)
xx = 0;
else
xx = x.data[i];

if (i > y.data.Count - 1)
yy = 0;
else
yy = y.data[i];

int z = xx + yy + carry;
if (z ≥ 10) // 10, 11, . . 19
{
result.data.Add(z - 10);
carry = 1;
}
else
{
result.data.Add(z);
carry = 0;
}
}

if (carry == 1)
result.data.Add(1);
return result;
} // Sum

public static MyBigInt Product(MyBigInt x, MyBigInt y)
{
MyBigInt tmp = null;
MyBigInt result = new MyBigInt("0");

for (int j = 0; j < y.data.Count; ++j)
{
int carry = 0;
tmp = new MyBigInt();
for (int i = 0; i < x.data.Count; ++i)
{
int z = x.data[i] * y.data[j] + carry;
if (z ≥ 10)
{
tmp.data.Add(z % 10); // 9 * 7 = 63. 63 / 10 = 6 rem 3
carry = z / 10;
}
else // z is 0, 1, . ., 9
{
tmp.data.Add(z);
carry = 0;
}
} // i

if (carry > 0)
tmp.data.Add(carry);

for (int k = 0; k < j; ++k)
{
tmp.data.Insert(0, 0);
}

result = MyBigInt.Sum(result, tmp);

} // j

return result;
}

public override string ToString()
{
int n = this.data.Count;
string s = "";
for (int i = n - 1; i ≥ 0; --i)
s += this.data[i].ToString();
return s;
}

} // class MyBigInt

} // ns
```
Advertisements
This entry was posted in Machine Learning. Bookmark the permalink.