IntX

Project Description
IntX is an arbitrary precision integers library written in pure C# 2.0 with fast - O(N * log N) - multiplication/division algorithms implementation. It provides all the basic operations on integers like addition, multiplication, comparing, bitwise shifting etc. It also allows parsing numbers in base from 2 to 16 and converting them to string, also in any base. The advantage of this library is fast multiplication, division and from base/to base conversion algorithms - all the fast versions of the algorithms are based on fast multiplication of big integers using Fast Hartley Transform which runs for O(N * log N * log log N) time instead of classic O(N^2).

Bits of History
I have written IntX basically because I like big numbers and had some free time. Initial implementation was standard - I was using standard big integers +, -, *, / algorithms from Khuth book. After library was written I've decided to participate in contest held by GotDotNet.ru site and received some replies which were saying that my library is too ... usual. Well, it was true, so I've decided to implement some more interesting algorithms in it.

I've started with writing multiplication using Fast Hartley Transform so big integers multiplication time estimate became to be O(N * log N * log log N) (here N is amount of DWORDs in number representation) which was a bit better then O(N^2) with classic algorithm :) Then I saw fast algorithm for transforming from one base to another in Knuth book; it was based on fast multiplication so Parse()/ToString() started working faster - O(N * (log N)^2) instead of O(N^2). Finally division was also optimized (again, with the help of fast multiplication) - became as fast as multiplication.

All this happened in 2005 year and now I've decided to publish this library on CodePlex - maybe it will be useful for someone out there (well, there is not so many similar libraries under .NET; also System.Numeric.BigInteger from .NET FW 3.5 was cancelled). Before publishing it on CodePlex I also made some cosmetic changes in code - used new .NET 2.0 features like generics (to minimize code duplication) and rewritten unit tests to use NUnit (they were previously written for MbUnit which is almost unknown and not used by community).

Code Example
Here is the sample of code which uses IntX and calculates 42 in power 1048576 (which is 2^20):

using System;
using System.Diagnostics;
using Oyster.Math;
 
namespace IntxTestApp
{
  class Program
  {
    static void Calc()
    {
      Stopwatch sw = Stopwatch.StartNew();
      IntX.Pow(42, 1 << 20);
      sw.Stop();
      Console.WriteLine("{0} ms", sw.ElapsedMilliseconds);
    }
 
    static void Main()
    {
      Calc();
 
      IntX.GlobalSettings.MultiplyMode = MultiplyMode.Classic;
      Calc();
    }
  }
}

First Calc() call uses fast multiplication implementation (which is default), second - classic one. On my machine (Win XP Pro SP2, P4 2.8 GHz, 2 GB RAM) first call is 70 times faster than the second one (1 second against 68 seconds). Resulting number has 1,702,101 digits; you can get it here: 42pow1048576.txt.

Another example is factorial calculation:

using System;
using Oyster.Math;
 
namespace IntxTestApp
{
  class Program
  {
    static IntX Factorial(IntX n)
    {
      if (n < 0)
      {
        throw new ArgumentException("Can't calculate factorial for negative number.", "n");
      }
      return n == 0 ? 1 : n * Factorial(n - 1);
    }
 
    static void Main()
    {
      Console.WriteLine(Factorial(10000));
    }
  }
}

As you can see, IntX implements all the standard arithmetic operators so its usage is transparent for developer - like if you're working with usual integer.

Future Plans
I have no plans to further develop this library - I'm just sharing it with the community.