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.