For your curiosity:    Java's BigInteger and BigDecimal classes

  • The largest integer value that can be stored in a primitive data type is: 

      Long.MAX_VALUE =  9223372036854775807

  • The largest decimal/floating point value that can be primitive stored in a data type is: 

      Double.MAX_VALUE =  1.7976931348623157 E 308

  • $64,000 question:

    • What if you need to use even larger numbers ???

  • Answer:

    • You must write algorithms that can perform computation (+, -, *, /) on a portion of a number

How can you extend computations on larger number ?

  • How to perform computations on extremely large numbers....

    Example: 

              1234567890123456789012345678901234567890
        + 9999999999999999999999999999999999999999
       -------------------------------------------

    Suppose the computer can only add two 10 digits numbers....

How can you extend computations on larger number ?

  • How to perform computations on extremely large numbers....

    Example: 

              1234567890123456789012345678901234567890
        + 9999999999999999999999999999999999999999
       -------------------------------------------
                                        1234567889 




              1234567890
            + 9999999999
          --------------
             11234567889
             ^
	     |
           Carry

    (1) Add the first portion of 10 digits and record the carry

How can you extend computations on larger number ?

  • How to perform computations on extremely large numbers....

    Example: 

              1234567890123456789002345678901234567890
        + 9999999999999999999989999999999999999999
       -------------------------------------------
                              92345678901234567889 



                       1  <-- carry from last addition
              0234567890
            + 8999999999
          --------------
             09234567890
             ^
	     |
           Carry

    (2) Add the next portion plus the carry, and record the new carry

How can you extend computations on larger number ?

  • How to perform computations on extremely large numbers....

    Example: 

              1234567890123456789002345678901234567890
        + 9999999999999999999989999999999999999999
       -------------------------------------------
                    123456788992345678901234567889 



                       0  <-- carry from last addition
              1234567890
            + 9999999999
          --------------
             11234567889
             ^
	     |
           Carry

    (3) Add the next portion plus the carry, and record the new carry

How can you extend computations on larger number ?

  • How to perform computations on extremely large numbers....

    Example: 

              1234567890123456789012345678901234567890
        + 9999999999999999999999999999999999999999
       -------------------------------------------
          1234567890123456788992345678901234567889



                       1
              1234567890
            + 9999999999
          --------------
             11234567890
             ^
	     |
           Carry

    (4) Add the final portion plus the carry, and record the new carry

How can you extend computations on larger number ?

  • How to perform computations on extremely large numbers....

    Example: 

              1234567890123456789012345678901234567890
        + 9999999999999999999999999999999999999999
       -------------------------------------------
         11234567890123456788992345678901234567889

    (5) add the carry in front of the result to get the final answer

Java's BigInteger and BigDecimal classes

  • How do you implement arithmetic operation using extremely large numbers:

      1. You need to design a data storage structure to store a large number of digits (e.g.: an ArrayList)

      2. You will need to implement (= write) methods that perform computations on numbers by computing on a portion of the digits

  • Java has implemented this feature in the following 2 classes: 

      java.math.BigInteger:  integer computations

  java.math.BigDecimal:  decimal/floating point computations

    I will show you how to use them next.

Constructing BigInteger objects   Documentation:

  • The BigInteger class implements the arbitrary precision integer data type

  • The BigInteger constructor must use a number String to create an integer

    (String is the only way to specify a large number of digits)

  • Example how to instantiate arbitrary precision integer numbers: 

    public class BigIntegers
{
    public static void main(String[] args)
    {
        BigInteger a = new BigInteger("12345678901234567890");
        BigInteger b = new BigInteger("99999999999999999999");
        
        System.out.println(a); // BigInteger has a toString()
        System.out.println(b); // that prints it out nicely
    }
}

  • Note:   A BigInteger object is immutable

DEMO: demo/12-wrapper/03-big-numbers/BigIntegers.java

Arithmetic operations with BigInteger objects

  • The BigInteger class contain instance methods that perform airthmetic operations: 

      add( x ):       returns this BigInteger object + BigNumber object x 

  subtract( x ):  returns this BigInteger object - BigNumber object x 

  multiply( x ):  returns this BigInteger object × BigNumber object x 

  divide( x ):    returns this BigInteger object / BigNumber object x 

  remainder( x ): returns this BigInteger object % BigNumber object x

  • The BigInteger methods will return a BigInteger object as result

  • Example: 

      BigInteger a = new BigInteger("123456789123456789123");
  BigInteger b = new BigInteger("999999999999999999999");
  BigInteger c;

  c = a.add(b);

DEMO: demo/12-wrapper/03-big-numbers/Arithmetic.java

Application    computing factorial for large numbers

  • Recall the factorial of n! is define as: 

      n!  =  n × (n-1) × ... × 1

  • We can write the factorial method with a for-loop as follows: 

     public static long factorial(long n)
 {
     long result = 1;
        
     for ( int i = 1; i <= n; i++ )
     {
         result = result * i;
     }

        return result;
    }

  • However:   we can only compute the factorial for numbers ≤ 20 because the largest integer number in Java is 9223372036854775807

DEMO: demo/12-wrapper/03-big-numbers/Factorial.java

Application    computing factorial for large numbers

  • We will modify the factorial( ) method to return the factorial with arbitrary precision represented with a BigInteger: 

                    BigInteger
 public static  long       factorial(long n)
 {

     long result = 1;     <---- 
        
     for ( int i = 1; i <= n; i++ )
     {


         result = result * i;
     }

     return result;
 }

    The data type of variable (result) in the factorial( ) method must be changed
     

Application    computing factorial for large numbers

  • The result that is returned must now be a BigInteger object:
      

                    BigInteger
 public static  long       factorial(long n)
 {

     BigInteger result = new BigInteger( "1") ;
        
     for ( int i = 1; i <= n; i++ )
     {

                 
         result = result * i;    <---- 
     }

     return result;
 }

    Java cannot perform result * i because it can only multiply 2 BigInteger objects
    (i is is not a BigInteger object)

Application    computing factorial for large numbers

  • We first instantiate a BigInteger object containing the value i :
    The expression   "" + i   converts the int represention in i to a String representation 

                    BigInteger
 public static  long       factorial(long n)
 {

     BigInteger result = new BigInteger( "1") ;
        
     for ( int i = 1; i <= n; i++ )
     {
         BigInteger iBig = new BigInteger( "" + i); // int i --> String
                 
         result = result * i;    <---- 
     }

     return result;
 }

    Java cannot perform result * i because it can only multiply 2 BigInteger objects
    (i is is not a BigInteger object)

Application    computing factorial for large numbers

  • We then multiply the 2 BigInteger objects (result and iBig) and update result:
      

                    BigInteger
 public static  long       factorial(long n)
 {

     BigInteger result = new BigInteger( "1") ;
        
     for ( int i = 1; i <= n; i++ )
     {
         BigInteger iBig = new BigInteger( "" + i); // int i --> String
                 
         result = result.multiply(iBig);   
     }

     return result;
 }

     
    Done !

DEMO: demo/12-wrapper/03-big-numbers/BigFactorial.java

BigDecimal    Documentation:

  • The BigDecimal class implements the arbitrary precision decimal data type

  • The BigInteger constructor also use a number String to create an integer

    (String is the only way to specify a large number of digits)

  • Example how to instantiate arbitrary precision decimal numbers: 

        public static void main(String[] args)
    {
        BigDecimal a = new BigDecimal("1.234567890123456789e10");
        BigDecimal b = new BigDecimal("9.9999999999999999999e100");
        
        System.out.println(a); // BigDecimal has a toString()
        System.out.println(b); // that prints it out nicely
    }

  • Note:   A BigDecimal object is immutable

DEMO: demo/12-wrapper/03-big-numbers/BigDecimal.java

BigDecimal division that never ends

  • Caveat using BigDecimal numbers:

    • A division can produce in an infinite number of digits !!

  • Example:   the division of 1/3 using BigDecimal will cause a runtime error: 

    import java.math.BigDecimal;

public class DivisionError
{
    public static void main(String[] args)
    {
        BigDecimal a = new BigDecimal("1");
        BigDecimal b = new BigDecimal("3");
	BigDecimal c;
        
        c = a.divide(b); // 0.33333333...
	    // ArithmeticException: Non-terminating decimal expansion
    }
}

DEMO: demo/12-wrapper/03-big-numbers/InfinteDiv.java

Limiting the number of digits in a BigDecimal division

  • We can avoid the infinite dvision error by specifying the number of digit (= scale) of the result by using: 

      a.divide(b)  --->   a.divide(b, scale, roundingMode.HALF_UP)

  scale = # digits in the result of the division
  roundingMode.HALF_UP: rounds 0.5 in the last digit up

    Example: 

     public static void main(String[] args)
 {
    BigDecimal a = new BigDecimal("1");
    BigDecimal b = new BigDecimal("3");
    BigDecimal c;
        
    c = a.divide(b, 20, RoundingMode.HALF_UP); 
    System.out.println(c);
 }

DEMO: demo/12-wrapper/03-big-numbers/InfinteDivFix.java