Big integers in C#

Question

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 for ulong length numbers. Does anyone have any better (preferably free) libraries, or is this level of performance normal?

Only problem is that they require the J# redistributables to be installed. The fact that J# is all but dead (it wasn't in VS 2008 atleast) probably doesn't help with promoting that. — Matthew Scharley, Oct 07 '08 at 00:39
J# is just to facilitate the migration of existing Java projects to .NET. I definitely wouldn't incorporate any of its libraries into a new project. — MusiGenesis, Oct 07 '08 at 01:44
possible duplicate of [How can I represent a very large integer in .NET? ](http://stackoverflow.com/questions/25375/how-can-i-represent-a-very-large-integer-in-net) — , May 26 '10 at 22:27
@Roger: I'd rather close the other, as this one has more up to information attached to it. — Matthew Scharley, May 27 '10 at 08:14

score 66 · Accepted Answer · edited Nov 13 '14 at 22:07

66

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.

edited Nov 13 '14 at 22:07

Zain Rizvi

23,586
22
91
133

answered Apr 27 '09 at 19:06

Davorin

1,278
10
14

27

For the record, The `System.Numerics` assembly is not referenced by default in new projects, so this needs to be added before `BigInteger` can be used. – Roman Starkov Dec 05 '10 at 16:45
In 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 – Jan Oct 14 '16 at 12:59

score 9 · Answer 2 · edited Apr 27 '09 at 19:47

9

F# also ships with one. You can get it at Microsoft.FSharp.Math.

edited Apr 27 '09 at 19:47

Motti

110,860
49
189
262

answered Jan 31 '09 at 13:22

Steve Severance

6,611
1
33
44

score 8 · Answer 3 · edited Apr 22 '15 at 13:42

8

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

edited Apr 22 '15 at 13:42

AnotherParker

789
5
16

answered Jun 19 '09 at 17:48

Rasmus Faber

48,631
24
141
189

score 4 · Answer 4 · answered Jun 23 '09 at 09:48

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)

Bouncy Castle

Mono

answered Jun 23 '09 at 09:48

Vadym Stetsiak

1,974
18
22

Sam Saffron · Answer 5 · 2008-10-07T00:50:03.997

4

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.

edited Oct 07 '08 at 00:50

answered Oct 07 '08 at 00:33

Sam Saffron

128,308
78
326
506

I 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. – Matthew Scharley Oct 07 '08 at 00:37
What size data are you working with, in general? Will stuff overflow the Int64 size on a regular basis, or is it an exception? – Sam Saffron Oct 07 '08 at 00:44
I'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. – Matthew Scharley Oct 07 '08 at 00:58
1

monoxide, I don't think it will be easy to get this to perform much faster than the implementation on codeproject for large numbers. – Sam Saffron Oct 07 '08 at 01:35
Like 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 :( – Matthew Scharley Oct 07 '08 at 02:13

score 3 · Answer 6 · answered Oct 07 '08 at 00:20

3

I'm not sure about the performance, but IronPython also has a BigInteger class. It is in the Microsoft.Scripting.Math namespace.

answered Oct 07 '08 at 00:20

Daniel Plaisted

16,674
4
44
56

score 2 · Answer 7 · answered Oct 07 '08 at 00:23

Yes, it will be slow, and 10x difference is about what I'd expect. BigInt uses an array to represent an arbitrary length, and all the operations have to be done manually (as opposed to most math which can be done directly with the CPU)

I don't even know if hand-coding it in assembly will give you much of a performance gain over 10x, that's pretty damn close. I'd look for other ways to optimize it--sometimes depending on your math problem there are little tricks you can do to make it quicker.

score 2 · Answer 8 · answered Oct 07 '08 at 00:29

2

I used Biginteger at a previous job. I don't know what kind of performance needs you have. I did not use it in a performance-intensive situation, but never had any problems with it.

answered Oct 07 '08 at 00:29

Jason Jackson

17,016
8
49
74

score 2 · Answer 9 · answered Oct 07 '08 at 00:31

2

This may sound like a strange suggestion, but have you tested the decimal type to see how fast it works?

The decimal range is ±1.0 × 10^−28 to ±7.9 × 10^28, so it may still not be large enough, but it is larger than a ulong.

There was supposed to be a BigInteger class in .NET 3.5, but it got cut.

answered Oct 07 '08 at 00:31

Powerlord

87,612
17
125
175

Yes, I saw that anouncement when originally looking for a BigInt library. Makes me sad. Oh well. – Matthew Scharley Oct 07 '08 at 00:34
You would have to be careful - using a decimal might cause rounding issues. – Blorgbeard Oct 07 '08 at 00:40
Decimal doesn't cause rounding errors. It's not floating point. – Kibbee Oct 07 '08 at 00:57
Decimal isn't float. It's a precision type as far as I'm aware. – Matthew Scharley Oct 07 '08 at 00:57
2

Decimal only tries to minimize errors due to rounding. It is not immune to rounding. http://msdn.microsoft.com/en-us/library/system.decimal.aspx – Robert Paulson Oct 07 '08 at 01:48
9

Decimal *is* a floating point type. It's just that it's a floating decimal point instead of a floating binary point. See http://pobox.com/~skeet/csharp/decimal.html I wouldn't expect rounding issues if all values are integers within the appropriate range though. – Jon Skeet Oct 07 '08 at 06:10

score 1 · Answer 10 · edited May 23 '17 at 12:17

1

This won't help you, but there was supposed to be a BigInteger class in .Net 3.5; it got cut, but from statements made at PDC, it will be in .Net 4.0. They apparently have spent a lot of time optimizing it, so the performance should be much better than what you're getting now.

Further, this question is essentially a duplicate of How can I represent a very large integer in .NET?

edited May 23 '17 at 12:17

Community

1
1

answered Nov 08 '08 at 20:41

technophile

3,556
1
20
24

BigInteger is in 3.5 but its an internal class. ;) Its there just not ready for prime time. – Ray Booysen Jan 31 '09 at 13:25

score 1 · Answer 11 · edited May 23 '17 at 12:09

1

See the answers in this thread. You will need to use one of the third-party big integer libraries/classes available or wait for C# 4.0 which will include a native BigInteger datatype.

edited May 23 '17 at 12:09

Community

1
1

answered Nov 10 '08 at 20:28

Scott Dorman

42,236
12
79
110

Charles Okwuagwu · Answer 12 · 2015-08-25T02:06:01.063

1

This Looks very promising. It is a C# Wrapper over GMP.

http://web.rememberingemil.org/Projects/GnuMpDotNet/GnuMpDotNet.html

There are also other BigInteger options for .Net here in particular, Mpir.Net

edited Aug 25 '15 at 02:06

answered Aug 25 '15 at 01:39

Charles Okwuagwu

10,538
16
87
157

1

Mpir.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. – John Reynolds Dec 10 '15 at 12:53

score 1 · Answer 13 · answered May 18 '19 at 09:10

You can also use the Math.Gmp.Native Nuget package that I wrote. Its source code is available on GitHub, and documentation is available here. It exposes to .NET all of the functionality of the GMP library which is known as a highly-optimized arbitrary-precision arithmetic library.

Arbitrary-precision integer are represented by the mpz_t type. Operations on these integers all begin with the mpz_ prefix. For examples, mpz_add or mpz_cmp. Source code examples are given for each operation.

Big integers in C#

13 Answers13

Linked

Related