Big integers in C#
Solution 1
As of .NET 4.0 you can use the System.Numerics.BigInteger class. See documentation here: http://msdn.microsoft.com/en-us/library/system.numerics.biginteger(v=vs.110).aspx
Another alternative is the IntX class.
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.
Solution 2
F#
also ships with one. You can get it at Microsoft.FSharp.Math
.
Solution 3
The System.Numerics.BigInteger
class in .NET 4.0 is based on Microsoft.SolverFoundation.Common.BigInteger
from Microsoft Research.
The Solver Foundation's BigInteger
class looks very performant. I am not sure about which license it is released under, but you can get it here (download and install Solver Foundation and find the Microsoft.Solver.Foundation.dll).
Solution 4
Here are several implementations of BigInteger in C#. I've used Mono's BigInteger implementation, works pretty fast (I've used it in CompactFramework)
Solution 5
I reckon you could optimize the implementation if you perform all the operations on BigInts that are going to return results smaller than a native type (Eg. int64) on the native types and only deal with the big array if you are going to overflow.
edit This implementation on codeproject, seems only 7 times slower ... But with the above optimization you could get it to perform almost identically to native types for small numbers.
Comments
-
Matthew Scharley almost 4 years
Currently I am borrowing
java.math.BigInteger
from the J# libraries as described here. Having never used a library for working with large integers before, this seems slow, on the order of 10 times slower, even forulong
length numbers. Does anyone have any better (preferably free) libraries, or is this level of performance normal? -
Matthew Scharley over 15 yearsYes, I saw that anouncement when originally looking for a BigInt library. Makes me sad. Oh well.
-
Matthew Scharley over 15 yearsI believe the J# library uses Byte's internally, it has a ToByteArray() function atleast, and no other ToArray() function. This might be an idea if I wanted to roll my own, I'm not too thrilled with that idea either though.
-
Blorgbeard over 15 yearsYou would have to be careful - using a decimal might cause rounding issues.
-
Sam Saffron over 15 yearsWhat size data are you working with, in general? Will stuff overflow the Int64 size on a regular basis, or is it an exception?
-
Kibbee over 15 yearsDecimal doesn't cause rounding errors. It's not floating point.
-
Matthew Scharley over 15 yearsI'm doing it mostly on a case by case basis, setting it to BigInt when I run into an overflow with a checked{} block. If it does that once, then there's a pretty good chance it'll do it repeatedly and often.
-
Sam Saffron over 15 yearsmonoxide, I don't think it will be easy to get this to perform much faster than the implementation on codeproject for large numbers.
-
Ashwin over 15 yearsDecimal only tries to minimize errors due to rounding. It is not immune to rounding. msdn.microsoft.com/en-us/library/system.decimal.aspx
-
Matthew Scharley over 15 yearsLike I said in my original post, I've never used a BigInteger implementation before, so I wouldn't know what sort of performance they get. That was more the question I was asking. Damn, I still want to roll my own as an intellectual excercise now though :(
-
Ray Booysen over 15 yearsBigInteger is in 3.5 but its an internal class. ;) Its there just not ready for prime time.
-
Roman Starkov over 13 yearsFor the record, The
System.Numerics
assembly is not referenced by default in new projects, so this needs to be added beforeBigInteger
can be used. -
John Reynolds over 8 yearsMpir.NET is partly based on Emil's GMP wrapper. The other part is X-MPIR, and fused together you get the convenience of Emil's wrapper and the performance of X-MPIR.
-
Jan over 7 yearsIn Solution Explorer do right click on References > Add Reference > Search for numerics and check the found reference. Now you can add "using System.Numerics;" at the top of your .cs file