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#.

CustomBigInt

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
This entry was posted in Machine Learning. Bookmark the permalink.