What is the limit of the Value Type BigInteger in C#?

Question

As described in MSDN BigInteger is :

An immutable type that represents an arbitrarily large integer whose value in theory has no upper or lower bounds.

As I can see BigInteger is a ValueType, as much as I know, a ValueType must have a maximum size of 16 bytes.

MSDN goes further saying :

an OutOfMemoryException can be thrown for any operation that causes a BigInteger value to grow too large.

and more :

Although this process is transparent to the caller, it does incur a performance penalty. In some cases, especially when repeated operations are performed in a loop on very large BigInteger values

How could it store such big values, as big as double.MaxValue + double.MaxValue ? I was told that it has ReferenceType obejects inside it, but all I can find here in its definition in VisualStudio is ValueTypes.

What's its real limit ? And even if doesn't have one, how can it "as a value type" manage to store all that amount of data ?

Answer 1

As I can see BigInteger is a ValueType, as much as I know, a ValueType must have a maximum size of 16 bytes.

No, that's not true. It's a conventional limit, but it's entirely feasible for a value type to take more than that. For example:

public struct Foo {
    private readonly int a, b, c, d, e; // Look ma, 20 bytes!
}

However, I strongly suspect that BigInteger actually includes a reference to a byte array:

public struct BigInteger {
    private readonly byte[] data;
    // Some other fields...
}

(Moslem Ben Dhaou's answer shows one current implementation using int and uint[], but of course the details of this are intentionally hidden.)

So the value of a BigInteger can still be small, but it can refer to a big chunk of memory - and if there isn't enough memory to allocate what's required when you perform some operation, you'll get an exception.

How could it store such big values, as big as double.MaxValue + double.MaxValue ?

Well BigInteger is for integers, so I wouldn't particularly want to use it for anything to do with double... but fundamentally the limitations are going to be around how much memory you've got and the size of array the CLR can cope with. In reality, you'd be talking about enormous numbers before actually hitting the limit for any specific number - but if you have gazillions of smaller numbers, that obviously has large memory requirements too.

Answer 2

As a confirmation to the answer from Jon Skeet, I looked to the source code of BigInteger. It actually contains two internal properties as follow:

internal int _sign;
internal uint[] _bits;

_bits is used by almost all private/public methods within the class which are used to read/write the actual data.

_sign is used to keep the sign of the BigInteger.

The private methods are extensively using binary operators and calculations. Here is a small list of constants used in the class that might reflect a bit the limits:

private const int knMaskHighBit = -2147483648;
private const uint kuMaskHighBit = 2147483648U;
private const int kcbitUint = 32;
private const int kcbitUlong = 64;
private const int DecimalScaleFactorMask = 16711680;
private const int DecimalSignMask = -2147483648;

PS: I should have commented on J.S. answer, but a comment is too short. To view the source code, either download it or decompile System.Numerics.dll.

Answer 3

TL;DR: BigInteger maxvalue is 2^68685922272

In .Net 4.7.2 BigInteger uses an uint array for bits.

An uint holds 32bits of data.

An array's max size is defined as internal const int MaxArrayLength = 0X7FEFFFFF; 7FEFFFFF = 2146435071

Now, to calculate: max size of array x capacity of each uint is: 2146435071 x 32 = 68685922272. But that's only the count of the bits in a BigInteger.

Which means BigInteger's max value is: 2^68'685'922'272 which is stupendusly large (used ' for easier readability).

If they ever decide to increase the array's max size, then it will also increase the max value for BigInteger.

Answer 4

I just did some quick experiments on this. Max seems to be around 2^65,000,000,000 but actual practicality 2146435071

I get a System.OverflowException on the below at 0x1F. It overflowed between E FFFF FFE2 and F 7FFF FFE1. (or somewhere between 2^64,424,509,410 and 2^66,571,993,057)

// Test 1
BigInteger test = 1;
for (int i = 0x00; i < 0xFF; i++)
    test <<= 0x7FFFFFFF;

// Test 2
BigInteger.Pow((BigInteger)2, 0x7FEFFFF0); // OK - I think - never finished
BigInteger.Pow((BigInteger)2, 0x7FEFFFFF); // Immediate OutOfMemoryException

I should also note that while ~66,571,993,057 seems to be supported. The usefulness is more like 2^2146435071 because POWER and shifts don't seem to work with a POWER larger then 2,146,435,071(for POW() ) or a shift amount more than 2,147,483,647. Larger shifts can be done but it would take several rounds ruining efficiency. And the other item is slow at those speeds - a single shift was taking about 7 seconds and BigInteger.Pow() took at least 5 minutes.

.Net 5, AMD Threadripper, 32GB RAM, Windows 10 x64