Is there an upper bound to BigInteger?

Question

Possible Duplicate:
What does BigInteger having no limit mean?

The Javadoc for BigInteger does not define any maximum or minimum. However, it does say:

(emphasis added)

Immutable arbitrary-precision integers

Is there such a maximum, even in theory? Or is the way BigInteger operates fundamentally different, such that there is in reality no maximum except for the amount of memory available on the computer?

The accepted answer in that possible duplicate does not specify the theoretical limit of `BigInteger`; or, if it truly does not have one, it does not explain why. Instead, it just says that if there *is* a maximum, it will never affect you with current memory limitations. — asteri, Oct 02 '12 at 15:44
Its probably in base 2, so the max is (2 ^ 32) ^ Integer.MAX_VALUE in base 2. — Ran, Feb 09 '15 at 19:43
@Ran, `BigInteger.valueOf(2).pow(500500)` returned something for me. — Samuel Edwin Ward, Apr 17 '15 at 21:04

score 108 · Accepted Answer · edited Jun 20 '20 at 09:12

108

The number is held in an int[] - the maximum size of an array is Integer.MAX_VALUE. So the maximum BigInteger probably is (2 ^ 32) ^ Integer.MAX_VALUE.

Admittedly, this is implementation dependent, not part of the specification.

In Java 8, some information was added to the BigInteger javadoc, giving a minimum supported range and the actual limit of the current implementation:

BigInteger must support values in the range -2^{Integer.MAX_VALUE} (exclusive) to +2^{Integer.MAX_VALUE} (exclusive) and may support values outside of that range.

Implementation note: BigInteger constructors and operations throw ArithmeticException when the result is out of the supported range of -2^{Integer.MAX_VALUE} (exclusive) to +2^{Integer.MAX_VALUE} (exclusive).

edited Jun 20 '20 at 09:12

Community

1
1

answered Oct 02 '12 at 15:24

assylias

321,522
82
660
783

6

As the values are used as unsigned `int` values, the maximum is more like `(2^32)^Integer.MAX_VALUE * 10^Integer.MAX_VALUE` as it can be scaled as well. – Peter Lawrey Oct 02 '12 at 15:26
1

@PeterLawrey Are you sure there is a scale for BigInteger? (there is one for BigDecimal). – assylias Oct 02 '12 at 15:28
2

Since integer MAX_VALUE is approx 2^31, the maximal value can't be kept in 32-bit computer memory :) So the memory is the limit. – Suzan Cioc Oct 02 '12 at 15:33
2

@SuzanCioc You could store an array of 2^32 integers on a 64 bits machine though (assuming you have enough RAM). – assylias Oct 02 '12 at 15:42
2

@assylias Good point. You can also store a `new int[2^31-1]` in a 64-bit JVM. Its about 8 GB which costs about $40. – Peter Lawrey Oct 02 '12 at 15:48
@assylias I do not understand how you get to the calculation `(2 ^ 32) ^ Integer.MAX_VALUE` . Eg: I have a `int[]` that can save maximum `5` `int`s . Each `int` can have a maximum value of `2^4`. Then the array with maximum values saved in it will look like `{16,16,16,16,16}`. If it is represented in the background by `BigInteger` as `1616161616` then how this number `which is supposed to be (MAX_NUMBER)` is equivalent to `(2^4)^5` ? Or I am understanding it completely wrong. – Ankit Jan 31 '15 at 16:13
What I understood is that `2^32` is the maximum `unsigned int` value that we can save at a single place in the array. The array can have a length of maximum `2^32` or `INTEGER.MAX_VALUE` . Then how `(2 ^ 32) ^ Integer.MAX_VALUE` ? – Ankit Jan 31 '15 at 16:13
@Ankit each` int` can take 2^32 values. An array of `int` can hold up to 2^32 `int`s. That array can therefore represent up to 2^32 (the number of positions in the array) ^ (2^32) (the number of values that each position can have). – assylias Jan 31 '15 at 16:29
@assylias This is where I am getting confused `ARRAY can represent UPTO`. In my example an array can represent max `1616161616`. and it is not equal to max we will get by `5 (number of positions in the array) ^ 16 (number the number of values that each position can have)`. – Ankit Jan 31 '15 at 16:35
@Ankit To make it simple, imagine your array has 2 positions, and each positions can have 3 values, the possible values are (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2, 2), or a total of 3^2 = 9 combinations. So you could use that to represent numbers from 0 to 8 (the fact that the largest combination is (2,2) does not mean that the largest number is 22). – assylias Jan 31 '15 at 17:15
@assylias, would you please clarify: 1. `Integer.MAX_VALUE` is the max size of a **`Byte` array on a 32-bit machine**, isn't it? 2. If so, the array can therefore represent up to (assuming we get the whole RAM) `Byte.MAX_VALUE (the number of values that each position can have) ^ Integer.MAX_VALUE` (the number of positions in the array)? – OfirD Aug 22 '16 at 14:43
1. Integer.MAX_VALUE is the maximum size of arrays in general in Java (whether it's an `int[]` or a `byte[]` and whether the JVM is 32 or 64 bits. 2. I don't understand why you are referring to bytes - BigIntegers are stored in an `int[]`. – assylias Aug 22 '16 at 14:59
`(2 ^ 32) ^ Integer.MAX_VALUE` are so many numbers, I hope never need to use it – deFreitas Jan 10 '17 at 23:04
All in all, its approximately `18GB` or somewhat more than that (below 19GB). – Animesh Sahu Jan 10 '21 at 08:15
@assylias What is stopping them to implement it using a `LinkedList`? – John Strood Sep 21 '21 at 10:58
wouldn't it be (Integer.MAX_VALUE)^(Integer.MAX_VALUE)? which would be smaller than what you're suggesting for most implementations where the max value is 2147483647, not 4294967295 – David Bandel Apr 03 '22 at 04:10
@DavidBandel Possibly, but you could also use the array to hold the unsigned value and have the sign in a separate field. It seems to be the case for [the reference implementation](https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/math/BigInteger.java#l124). – assylias Apr 03 '22 at 08:17

embedded.kyle · Answer 2 · 2012-10-02T15:55:35.893

BigInteger would only be used if you know it will not be a decimal and there is a possibility of the long data type not being large enough. BigInteger has no cap on its max size (as large as the RAM on the computer can hold).

From here.

It is implemented using an int[]:

  110       /**
  111        * The magnitude of this BigInteger, in <i>big-endian</i> order: the
  112        * zeroth element of this array is the most-significant int of the
  113        * magnitude.  The magnitude must be "minimal" in that the most-significant
  114        * int ({@code mag[0]}) must be non-zero.  This is necessary to
  115        * ensure that there is exactly one representation for each BigInteger
  116        * value.  Note that this implies that the BigInteger zero has a
  117        * zero-length mag array.
  118        */
  119       final int[] mag;

From the source

From the Wikipedia article Arbitrary-precision arithmetic:

Several modern programming languages have built-in support for bignums, and others have libraries available for arbitrary-precision integer and floating-point math. Rather than store values as a fixed number of binary bits related to the size of the processor register, these implementations typically use variable-length arrays of digits.

score 14 · Answer 3 · edited Oct 02 '12 at 15:31

14

The first maximum you would hit is the length of a String which is 2³¹-1 digits. It's much smaller than the maximum of a BigInteger but IMHO it loses much of its value if it can't be printed.

edited Oct 02 '12 at 15:31

NullUserException

83,810
28
209
234

answered Oct 02 '12 at 15:25

Peter Lawrey

525,659
79
751
1,130

13

In full fairness, you'd just need more logic to print it. – Marko Topolnik Oct 02 '12 at 17:51
4

If its ok to use multiple Strings you could use multiple BigIntegers as well. ;) – Peter Lawrey Oct 02 '12 at 18:02
5

True, but that would cause much more complications in your code than just the print routine. – Marko Topolnik Oct 02 '12 at 18:09

Is there an upper bound to BigInteger?

3 Answers3

Linked

Related