Storing a very, very large number theoretical [closed]

Question

It's old news, but I was recently reading about the largest prime numbers, which about one year ago a 17 million digit prime number was found (the largest to date). This got me thinking a little bit as you have to be able to compute the number to ensure that it is prime. What methods could be implemented to do this? I'm unaware of any data type that could hold this much data and still allow it to be computed. Can BigInt handle this?

Answer 1

The claim that BigInteger "in theory has no upper or lower bounds" is incorrect. In .NET 4.0, the BigInteger struct is internally represented using an uint[] array. Given that the maximum value for uint is 4,294,967,295, and that the maximum length for the array is 2,146,435,071, the current implementation of BigInteger has a theoretical upper bound of 4,294,967,295 ^{2,146,435,071} (assuming perfect packing). This allows it to store integers consisting of billions of digits (including your prime), but not trillions.

Edit: As mentioned in the comments, arrays cannot exceed 2 gigabytes in total size, unless the <gcAllowVeryLargeObjects> setting in enabled (which requires .NET 4.5 and 64-bit). Since the uint data type occupies 4 bytes, the maximum number of elements in the array is limited to 2²⁹.

To demonstrate this upper bound, all you need to do is run the following code, which attempts to calculate (2³⁰)⁽²³⁰⁾.

var bi = BigInteger.Pow(1 << 30, 1 << 30);

Within a few seconds, you would get an error:

OutOfMemoryException: Array dimensions exceeded supported range.

Do not be misled by the name of the exception type; this error will be thrown even if you have abundant memory to accommodate the entire number. The same error would, in fact, be thrown if you run the following snippet:

var s = new uint[1 << 30];

Answer 2

MSDN claims that

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

So yes, it could handle a number like this, in theory. This type also provides many mathematical operations which can work with it.

Answer 3

From the documentation for BigInteger.

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

However, it goes on to say:

because it has no upper or lower bounds, an OutOfMemoryException can be thrown for any operation that causes a BigInteger value to grow too large.

So I guess the answer is, yes it could handle it, however you have to have a machine with enough memory.