Storing a very, very large number theoretical
c#
Solution
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 229.
To demonstrate this upper bound, all you need to do is run the following code, which attempts to calculate (230)(230).
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];
Problem
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?