12

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?

shadowjfaith
  • 932
  • 8
  • 14
  • you can save it into string – Ranjit Singh Jan 10 '14 at 15:08
  • possible duplicate of [To find factorial of 500 and store it in a variable...and perform calculations...How to store such a huge number?](http://stackoverflow.com/questions/18535998/to-find-factorial-of-500-and-store-it-in-a-variable-and-perform-calculations) – Almo Jan 10 '14 at 15:09
  • had to do that in college. I'd just use an array and implement your own solution – Jonesopolis Jan 10 '14 at 15:09
  • BigInt is limited to 2^64 `-9,223,372,036,854,775,808` to `9,223,372,036,854,775,807` – Lotok Jan 10 '14 at 15:13
  • Kind of related, excellent TED talk on monster prime numbers, http://www.ted.com/talks/adam_spencer_why_i_fell_in_love_with_monster_prime_numbers.html – Konstantin Jan 10 '14 at 15:13
  • @James What is the source of your information? – Ondrej Janacek Jan 10 '14 at 15:14
  • There is an [MSDN post here](http://social.msdn.microsoft.com/Forums/vstudio/en-US/2604f7dc-049d-4230-aace-4253b8bd037c/bigint-in-c?forum=netfxbcl). But also its a 64bit integer. Binary maths would mean it has the upper limit of 2^64 – Lotok Jan 10 '14 at 15:16
  • @Almo possibly, but there is a big leap from 1,000 digits to 17 million. Could an array support 17 million or is that also just limited by memory? – shadowjfaith Jan 10 '14 at 15:23
  • @kostyan I've seen that, which is one of the things that perked my interest in the matter, and it is an amazing talk. – shadowjfaith Jan 10 '14 at 15:25
  • @tnw: It's not the first time that the documentation was incorrect. – Douglas Jan 10 '14 at 15:28
  • @tnw As you can see by some of the answers there is a discrepancy. Also it's a 17 MILLION digit long number. As stated by some answers and MSDN it has a no theoretical upper bound, which doesn't mean it can or cannot handle this. – shadowjfaith Jan 10 '14 at 15:30
  • 2
    @James you are confusing the bigint type in SQL Server (a 64 bit normal integer type) with the `BigInteger` in the .NET framework which is an integer type only bounded by memory. – Anders Forsgren Jan 10 '14 at 15:40

5 Answers5

20

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];
Douglas
  • 53,759
  • 13
  • 140
  • 188
  • +1 Very helpful as you gave an actual number to the theoretical maximum. – shadowjfaith Jan 10 '14 at 15:44
  • I've just discovered that there's a similar answer for Java: http://stackoverflow.com/a/12693333/1149773 – Douglas Jan 10 '14 at 15:46
  • 1
    Under normal circumstances (i.e. not 64bit .NET 4.5 with gcAllowVeryLargeObjects enabled) the maximum size of any object is 2Gb (2^31 bytes), so wouldn't the maximum length of the uint array be around 2^31/4 = 2^29 uints only? – Anders Forsgren Jan 10 '14 at 15:49
  • @AndersForsgren Good point, and most likely true given typical development environments, but it would still hold the number, and given the rate of prime number discovery I'm sure that 2Gb would be a thing of the past for most by the time a 500+ million prime is discovered (if they are truly indefinite). – shadowjfaith Jan 10 '14 at 15:59
5

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.

Ondrej Janacek
  • 12,486
  • 14
  • 59
  • 93
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.

poy
  • 10,063
  • 9
  • 49
  • 74
  • Don't forget that "out of memory" doesn't mean "I'm out of RAM", it means "I'm out of address space". Putting more memory in your machine just makes it faster, it doesn't make out-of-memory errors go away. – Eric Lippert Jan 10 '14 at 16:22
  • 1
    Yea but if you have a x64 system... You would have 8TB of address space. – poy Jan 10 '14 at 16:44
0

As far as I have tested BigInt can handle absolutely huge numbers. I literally let the console print the number for a few minutes. The only limitation is your memory.

Georgi-it
  • 3,676
  • 1
  • 20
  • 23
0

If you look into how the operations are actually implemented, you'll find out that there's no reason to limit them to eg. 32-bit numbers (overflows, infinite polynomials etc.). So if you replicate the same logic in software, you can do anything with arbitrarily large numbers. Of course, making it fast is another matter entirely.

Luaan
  • 62,244
  • 7
  • 97
  • 116