Find something

Sunday, 13 July 2014

Commodious Calculations In Java: An introduction to java.math.BigInteger package.

Introduction

Often, we find that the built-in primitive datatypes are not enough to satisfy our thirst for precision. In many circumstances, we need to perform huge (and I mean huge) calculations that well exceed the range of the primitive datatypes. The developers of Java™ have provided (quite possibly the best) solution: They have added support for arbitrary precision numbers by including within the standard package the java.math package. We will discuss the BigInteger class here...


Where We Stand

Let's see the range of the various primitive datatypes we have:
(Adapted from the Java Language Specification)

4.2.1 Integral Types and Values

The values of the integral types are integers in the following ranges:
• For byte, from -128 to 127, inclusive
• For short, from -32768 to 32767, inclusive
• For int, from -2147483648 to 2147483647, inclusive
• For long, from -9223372036854775808 to 9223372036854775807, inclusive
• For char, from '\u0000' to '\uffff' inclusive, that is, from 0 to 65535
But, for the Floating-Point Types, it's pretty complicated. You may see the original article: Floating-Point Types, Formats, and Values. It turns out that the post gets unnecessarily complicated if I try to explain it.

As ridiculous as it may seem, we can easily cross the range of event the 64-bit long datatype. Try this simple example:


package maths;

/**
 * A simple class that demonstrates just how quickly the factorial function can
 * grow and exceed the range for {@code long} datatype.
 *
 * @author Subhomoy Haldar
 */
public class Factorial {

    public static void main (String[] args) {
        for (int i = 0; i <= 25; i++) {
            System.out.println(i + "! = " + fac(i));
        }
    }

    /**
     * A very obvious implementation of the factorial function.
     *
     * @param num Its factorial to be calculated.
     *
     * @return the factorial of {@code num}
     */
    public static long fac (int num) {
        long f = 1;
        for (int i = 1; i <= num; i++) {
            f *= i;
        }
        return f;
    }
}
Agreed that the code is very easy. But the output is equally confusing:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = -4249290049419214848
22! = -1250660718674968576
23! = 8128291617894825984
24! = -7835185981329244160
25! = 7034535277573963776
(The color is for indicative purpose only)
The works (apparently) works fine for numbers till 20, but goes all weird after that. We see that 21! is printed negative! This happens because the result overflows to the 64th bit, and we know that the 64th bit (in case of long, 32 for int, and so on) is the signed-bit. But that is fine... that can be rectified. But as soon as the result exceeds 64 bits, the information is lost... forever. Hence, we see the need to use arbitrary-precision datatypes.

BigInteger to the rescue...

Now, we get the first crack at the java.math package. Let us look at the javadocs of this class:

Immutable arbitrary-precision integers. All operations behave as if BigIntegers were represented in two's-complement notation (like Java's primitive integer types). BigInteger provides analogues to all of Java's primitive integer operators, and all relevant methods from java.lang.Math. Additionally, BigInteger provides operations for modular arithmetic, GCD calculation, primality testing, prime generation, bit manipulation, and a few other miscellaneous operations.
Great! But can it hold the weight of those bulky numbers?
The answer is in the docs:
All methods and constructors in this class throw NullPointerException when passed a null object reference for any input parameter. BigInteger must support values in the range -2Integer.MAX_VALUE (exclusive) to +2Integer.MAX_VALUE (exclusive) and may support values outside of that range. The range of probable prime values is limited and may be less than the full supported positive range of BigInteger. The range must be at least 1 to 2500000000. 
Awesome! Let's get cooking...
package maths;

import java.math.BigInteger;

/**
 * A simple class that demonstrates just how quickly the factorial function can
 * grow.
 *
 * @author Subhomoy Haldar
 */
public class Factorial {

    public static void main (String[] args) {
        for (int i = 0; i <= 25; i++) {
            System.out.println(i + "! = " + bigFac(i));
        }
    }

    /**
     * A very obvious implementation of the factorial function.
     *
     * @param num Its factorial to be calculated.
     *
     * @return the factorial of {@code num}
     *
     * @deprecated[1] Doesn't work for values greater than 20 as {@code long}
     * overflows.
     * @see Factorial#bigFac(int) Accurate replacement of this method.
     */
    public static long fac (int num) {
        long f = 1;
        for (int i = 1; i <= num; i++) {
            f *= i;
        }
        return f;
    }

    /**
     * Another very obvious implementation of the factorial function.
     *
     * @param num Its factorial to be calculated.
     *
     * @return the factorial of {@code num}
     */
    public static BigInteger bigFac (int num) {
        BigInteger f = BigInteger.ONE;
        for (int i = 1; i <= num; i++) {
            f = f.multiply(BigInteger.valueOf(i));
        }
        return f;
    }
}
The moment of truth...
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = 51090942171709440000
22! = 1124000727777607680000
23! = 25852016738884976640000
24! = 620448401733239439360000
25! = 15511210043330985984000000
Tada! [Cheers and applause] Thank you, thank you, oh! thank you very much!...

You can go as high as you like... the result will always be 100% correct (unless of course it exceeds the very big limit). I encourage you to go an explore the methods provided in this wonderful class (in the javadocs of course!). So that's it for now. I'll explain this important class: BigInteger in detail in my next post.
 

[1] @deprecated indicates that some particular method or field has become outdated and may be removed in a later release. I've deprecated the fac(int) method for it is limited in capabilities.

Most Viewed