59

I looked into this stackoverflow question relating to Big Integer and specifically I do not understand this line (the words in italics):

In the BigInteger class, I have no limits and there are some helpful functions there but it is pretty depressing to convert your beautiful code to work with the BigInteger class, specially when primitive operators don't work there and you must use functions from this class.

I don't know what I am missing but to represent something that has no limit you would require infinite memory ? Whats is the trick here ?

Community
  • 1
  • 1
Geek
  • 26,489
  • 43
  • 149
  • 227

4 Answers4

93

There is no theoretical limit. The BigInteger class allocates as much memory as it needs for all the bits of data it is asked to hold.

There are, however, some practical limits, dictated by the memory available. And there are further technical limits, although you're very unlikely to be affected: some methods assume that the bits are addressable by int indexes, so things will start to break when you go above Integer.MAX_VALUE bits.

Graham Borland
  • 60,055
  • 21
  • 138
  • 179
  • 1
    It is very much like a String or a byte[] that way (although I think those are technically limited to integer-addressable elements). – Thilo Aug 23 '12 at 09:20
  • 2
    @Thilo: so is BigInteger: the data is held in an int[] which puts a theoretical limit on the size of numbers it can represent. – Michael Borgwardt Aug 23 '12 at 09:20
  • I hear work is underway for "long" arrays (and have to wonder who needs that) ;-) – Thilo Aug 23 '12 at 09:22
  • @Thilo What do you mean by "It is very much like a String or a byte[] that way (although I think those are technically limited to integer-addressable elements)." – Geek Aug 23 '12 at 09:24
  • 2
    @MichaelBorgwardt The backing int[] array is surely an implementation detail, rather than being specified behaviour, no? – Graham Borland Aug 23 '12 at 09:24
  • @MichaelBorgwardt What is the throretical limit on int[] ? Doesn't array grow as much as it can grow ? How would long[] solve this ? – Geek Aug 23 '12 at 09:25
  • Can it use 128 bit memory addressing? – huseyin tugrul buyukisik Aug 23 '12 at 09:25
  • @Geek: just like a String, it is only (really) limited by how much memory you have. There are some technical limits, too, but if you reach those, you are probably already beyond practical use cases. – Thilo Aug 23 '12 at 09:26
  • 6
    An array in Java can only have 2^32 elements currently. Some people want 2^64. A BigInteger stores its bits in an int[], so it can store at most 2^32 ints, i.e. 2^37 bits right now. Pretty large. – Thilo Aug 23 '12 at 09:27
  • @Thilo It's actually quite a useful thing when you want to operate on huge files in-memory. The installed RAM of today's machines is really starting to show the artificial cap of `Integer.MAX_VALUE` to the size of files that can be processed that way. – Marko Topolnik Aug 23 '12 at 09:28
  • 7
    @Graham Borland: The backing int[] is an implementation detail, but the BigInteger API has several methods using int parameters to access the nth bit and the toString() methods indirectly limits the theoretical magnitude of the BigInteger implementation, since the number must be representable as a String. Because of that, a BigInteger can't be larger than 2^(2^31-1)-1, which is much less than the limit imposed by the backing int array. – jarnbjo Aug 23 '12 at 09:36
  • Edited answer to take into account the int-addressable issue. – Graham Borland Aug 23 '12 at 09:41
18

Graham gave great answer to this question. I would like only to add that you have to be carefull with valueOf method because it is created using long parameter so the maximum value is Long.MAX_VALUE.

Adam Sznajder
  • 9,108
  • 4
  • 39
  • 60
  • 3
    The one that takes a long parameter obviously cannot go beyond, but there are constructors that take Strings or byte arrays. – Thilo Aug 23 '12 at 09:32
  • 1
    There's no public constructor that takes `long` as argument. There's only a getter (with warnings about losing information in the documentation). – martijno Aug 23 '12 at 09:38
  • 4
    No real need not be careful, as the `BigInteger.valueOf(long)` method will give you a compilation error if you try to write a literal that exceeds `Long.MAX_VALUE`. Furthermore, it's easy to construct a BigInteger much greater, say `BigInteger.valueOf(10).pow(10000)` – leonbloy Jan 10 '14 at 02:03
6

Yes its used when we need very big numbers with arbitrary precision. It's important to note that "arbitrary" precision or number of digits does not mean "unlimited": it means that the number of digits in a number or number of digits of precision in a calculation is limited by memory and/or defined limits to precision that we specify.

Eduard
  • 3,176
  • 3
  • 21
  • 31
3

Look at the BigInteger class source code, you will see (it can be done with NetBean). A number will be represented as an int arrays. Example, 10113 will be [1, 0, 1, 1, 3] (this is not exactly what the BigInteger class does, just an example how big number module work). So, technically, its only limit will be your memory.

Vũ Mạnh Cường
  • 39
  • 2