Project DescriptionIntX 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 HistoryI 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 ExampleHere 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 PlansI have no plans to further develop this library - I'm just sharing it with the community.
System.Numerics.BigInteger in .NET 4.0According to the
BCL team blog MS is going to introduce System.Numerics.BigInteger class in .NET 4.0, this time for sure :) Once I saw this blog entity I was interested in performance of their solution - you can download preliminary version together with
MS Solver Foundation (it's for .NET 3.5), it's called Microsoft.SolverFoundation.Common.BigInteger in there. I did some tests and it appears that BigInteger is faster than my IntX (up to 1.5-2x) on standard operations but starts losing when FHT comes into play (when multiplying really big integers, for example).
So internally System.Numerics.BigInteger seem to use standard arbitrary arithmetic algorithms (but optimized very well, I must say) and I am not worrying about IntX library since, due to its use of FHT, it can be times faster for really big integers.