Is there an upper bound to BigInteger? [duplicate]

Asked 2/10, 2012 at 15:21 Answered 2/10, 2012 at 15:28

107

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?

Virgate answered 2/10, 2012 at 15:21 Comment(5)

In theory there is no limit. – Houle 2/10, 2012 at 15:29

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. – Virgate 2/10, 2012 at 15:44

Its probably in base 2, so the max is (2 ^ 32) ^ Integer.MAX_VALUE in base 2. – Copula 9/2, 2015 at 19:43

@Ran, BigInteger.valueOf(2).pow(500500) returned something for me. – Iguanodon 17/4, 2015 at 21:4

@Ran, "returns nothing" doesn't mean anything in Java. – Alveta 20/3, 2016 at 19:1

111

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).

Bankbook answered 2/10, 2012 at 15:24 Comment(17)

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. – Silicosis 2/10, 2012 at 15:26

@PeterLawrey Are you sure there is a scale for BigInteger? (there is one for BigDecimal). – Bankbook 2/10, 2012 at 15:28

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. – Nor 2/10, 2012 at 15:33

@SuzanCioc You could store an array of 2^32 integers on a 64 bits machine though (assuming you have enough RAM). – Bankbook 2/10, 2012 at 15:42

@Bankbook 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. – Silicosis 2/10, 2012 at 15:48

@Bankbook 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 ints . 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. – Tatianatatianas 31/1, 2015 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 ? – Tatianatatianas 31/1, 2015 at 16:13

@Tatianatatianas each` int` can take 2^32 values. An array of int can hold up to 2^32 ints. 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). – Bankbook 31/1, 2015 at 16:29

@Bankbook 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). – Tatianatatianas 31/1, 2015 at 16:35

@Tatianatatianas 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). – Bankbook 31/1, 2015 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)? – Flood 22/8, 2016 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[]. – Bankbook 22/8, 2016 at 14:59

(2 ^ 32) ^ Integer.MAX_VALUE are so many numbers, I hope never need to use it – Tighten 10/1, 2017 at 23:4

All in all, its approximately 18GB or somewhat more than that (below 19GB). – Chickenlivered 10/1, 2021 at 8:15

@Bankbook What is stopping them to implement it using a LinkedList? – Grime 21/9, 2021 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 – Sprightly 3/4, 2022 at 4: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. – Bankbook 3/4, 2022 at 8:17

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.

Cincinnati answered 2/10, 2012 at 15:28 Comment(0)

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.

Silicosis answered 2/10, 2012 at 15:25 Comment(3)

In full fairness, you'd just need more logic to print it. – Aquilar 2/10, 2012 at 17:51

If its ok to use multiple Strings you could use multiple BigIntegers as well. ;) – Silicosis 2/10, 2012 at 18:2

True, but that would cause much more complications in your code than just the print routine. – Aquilar 2/10, 2012 at 18:9

Hot tags

Godot Unity Godot Help Programming Godot 4.X GUI GDScript 3D 2D Physics CSharp Godot 3.X VR XR Projects C++

Recommended topics

Hot tags