Monday, December 26, 2011

Guava Release 11's IntMath

As I stated earlier in the post Sneaking a Peek at Guava Release 11, Guava Release 11 provides numerous new classes including several classes specifically related to mathematical operations. In this post, I look at one of these that is targeted at integer math: Guava's IntMath.

As stated in my previous post, com.google.common.math.IntMath is largely based on Henry S. Warren, Jr.'s Hacker's Delight. As the class name indicates, the operations of this class are focused on "arithmetic on values of type int."

The next screen snapshot shows the methods and static attributes supported by IntMath as listed by javap:

For convenience, I have listed a text version of the above javap output here.

Compiled from "IntMath.java"
public final class com.google.common.math.IntMath {
  static final int MAX_POWER_OF_SQRT2_UNSIGNED;
  static final int[] POWERS_OF_10;
  static final int[] HALF_POWERS_OF_10;
  static final int FLOOR_SQRT_MAX_INT;
  static final int[] FACTORIALS;
  static int[] BIGGEST_BINOMIALS;
  public static boolean isPowerOfTwo(int);
  public static int log2(int, java.math.RoundingMode);
  public static int log10(int, java.math.RoundingMode);
  public static int pow(int, int);
  public static int sqrt(int, java.math.RoundingMode);
  public static int divide(int, int, java.math.RoundingMode);
  public static int mod(int, int);
  public static int gcd(int, int);
  public static int checkedAdd(int, int);
  public static int checkedSubtract(int, int);
  public static int checkedMultiply(int, int);
  public static int checkedPow(int, int);
  public static int factorial(int);
  public static int binomial(int, int);
  static {};
}

As the image and text output above indicate, the IntMath class has much to offer in terms of functionality related to integer arithmetic. The remainder of this post will demonstrate this.

Factorial calculation is commonly implemented in software development examples, especially in academic contexts such as illustrating recursion. The blog post Implementing the Factorial Function Using Java and Guava is devoted to different implementations of factorial implemented in Java and Guava. Guava Release 11 now provides a method for calculating factorial in IntMath.factorial(int).

Guava's IntMath.factorial(int) Demonstrated
   /**
    * Demonstrate factorial calculation.
    */
   public static void demoFactorial()
   {
      final int x = 5;
      final int factorial = IntMath.factorial(x);
      out.println("Factorial of x=" + x + " is " + factorial);
   }

Another often mathematical operation supported by Guava Release 11 is the calculation of the binomial coefficient via IntMath.binomial(int,int).

Guava's IntMath.binomial(int,int) Demonstrated
   /**
    * Demonstrate binomial Coefficient calculation
    * (http://en.wikipedia.org/wiki/Binomial_coefficient).
    */
   public static void demoBinomialCoefficient()
   {
      final int n = 5;
      final int k = 3;
      final int binomialCoefficient = IntMath.binomial(n, k);
      out.println(
           "Binomial Coefficient of n=" + n + " and k=" + k + " is "
         + binomialCoefficient);  
   }

Guava Release 11 also adds a method for calculating the greatest common divisor of two provided integers.

Guava's IntMath.gcd(int,int) Demonstrated
   /**
    * Demonstrate calculation of greatest common factor (GCF) [called greatest
    * common divisor here].
    */
   public static void demoGreatestCommonFactor()
   {
      final int x = 30;
      final int y = 45;
      final int gcf = IntMath.gcd(x, y);
      out.println("GCF of " + x + " and " + y + " is " + gcf);
   }

Guava Release 11 provides a method for calculating an integer square root of a provided integer, rounding to the integer result when needed based on the provided RoundingMode. The fact that the result of the square root function is an integer distinguishes this method from Math.sqrt(double).

Guava's IntMath.sqrt(int) Demonstrated
   /**
    * Demonstrate calculation of square roots.
    */
   public static void demoSquareRoot()
   {
      final int x = 16;
      final int sqrtX = IntMath.sqrt(x, RoundingMode.HALF_EVEN);
      out.println("Square root of " + x + " is " + sqrtX);
      final int y = 25;
      final int sqrtY = IntMath.sqrt(y, RoundingMode.HALF_EVEN);
      out.println("Square root of " + y + " is " + sqrtY);  
   }

Guava Release 11's IntMath provides the method pow(int,int) for the first integer multiplied by itself the number of times expressed by the second integer (similar to Math.pow(double,double), but accepting and returning integers rather than doubles.). The IntMath.pow(int,int) method provides handling for situations in which the operation would normally result in an overflow. In such a situation, according to the method's Javadoc, the method will return a result that "will be equal to BigInteger.valueOf(b).pow(k).intValue()."

Guava's IntMath.pow(int,int) Demonstrated
   /**
    * Demonstrate exponential power calculation.
    */
   public static void demoExponentialPower()
   {
      final int base = 2;
      final int exponent = 5;
      final int result = IntMath.pow(base, exponent);
      out.println(base + " to power of " + exponent + " is " + result);
   }

A particularly interesting method that Guava Release 11 provides that could be especially useful in certain software development and computer contexts is the method IntMath.isPowerOfTwo(int). This method returns a boolean indicating whether the provided integer is evenly divisible (no remainder) by two.

Guava's IntMath.isPowerOfTwo(int) Demonstrated
   /**
    * Demonstrate determination of whether an integer is a power of two.
    */
   public static void demoIsPowerOfTwo()
   {
      final int x = 16;
      out.println(x + (IntMath.isPowerOfTwo(x) ? " IS " : " is NOT " ) + " a power of two.");
      final int y = 31;
      out.println(y + (IntMath.isPowerOfTwo(y) ? " IS " : " is NOT " ) + " a power of two.");
   }

Guava's IntMath class provides two methods for performing logarithmic calculations, specifically focusing on the common logarithm (base 10) and the binary logarithm (base 2). Both of these are demonstrated in the next code listing.

Guava's IntMath.log10(int,RoundingMode) and IntMath.log2(int,RoundingMode) Demonstrated
   /**
    * Demonstrate IntMath.log10 and IntMath.log2.
    */
   public static void demoLogarithmicFunctions()
   {
      final int x = 10000000;
      final int resultX = IntMath.log10(x, RoundingMode.HALF_EVEN);
      out.println("Logarithm (base 10) of " + x + " is " + resultX);
      final int y = 32;
      final int resultY = IntMath.log2(y, RoundingMode.HALF_EVEN);
      out.println("Logarithm (base 2) of " + y + " is " + resultY);
   }

Guava Release 11's IntMath.divide(int,int,RoundingMode) allows for integer division in which the type of rounding used in the division can be specified as part of the call. This is more flexible than direct Java integer division which always rounds the quotient down to the lower integer (floor).

Guava's IntMath.divide(int,int,RoundingMode) Demonstrated
   /**
    * Demonstrate division using IntMath.divide.
    */
   public static void demoDivision()
   {
      final int dividend = 30;
      final int divisor = 10;
      final int quotient = IntMath.divide(dividend, divisor, RoundingMode.HALF_EVEN);
      out.println(dividend + " / " + divisor + " = " + quotient);
   }

I mentioned previously that Guava Release 11's IntMath.pow(int,int) would handle overflow situations by returning "BigInteger.valueOf(b).pow(k).intValue()" where 'b' is the first integer (base) and 'k' is the second integer (power/exponent). In some cases, it may be preferable to have an exception thrown when the overflow situation occurs rather than "hiding" the issue. In such cases, Guava Release 11's IntMath.checkedPow(int,int) is desirable because it will throw an ArithmeticException if the operation results in an overflow.

IntMath.checkedPow(int,int) Demonstrated
   /**
    * Demonstrate Guava Release 11's checked power method and compare it to
    * other common approaches for determining base multiplied by itself exponent
    * number of times.
    */
   public static void demoCheckedPower()
   {
      try
      {
         final int base = 2;
         final int exponent = 4;
         final int result = IntMath.checkedPow(base, exponent);
         out.println("IntMath.checkedPow: " + base + "^" + exponent + " = " + result);

         out.println(
              "IntMath.pow: " + Integer.MAX_VALUE + "^2 = " +
            + IntMath.pow(Integer.MAX_VALUE, 2));
         out.println(
              "Math.pow(int,int): " + Integer.MAX_VALUE + "^2 = "
            + Math.pow(Integer.MAX_VALUE, 2));
         out.println("Multiplied: " + Integer.MAX_VALUE*Integer.MAX_VALUE);
         out.print("IntMath.checkedPow: " + Integer.MAX_VALUE + "^2 = ");
         out.println(IntMath.checkedPow(Integer.MAX_VALUE, 2));
      }
      catch (Exception ex)
      {
         err.println("Exception during power: " + ex.toString());
      }
   }

Guava Release 11's IntMath class provides three more "checked" methods that throw an ArithmeticException when the given mathematical operation results in an overflow condition. These methods are for addition, substraction, and multiplication and are respectively called IntMath.checkedAdd(int,int), IntMath.checkedSubtract(int,int), and IntMath.checkedMultiply(int,int). As discussed in conjunction with IntMath.checkedPow(int,int), the advantage of this occurs in situations where it is better to have an exception and know overflow occurred than to blindly operate on an erroneous value due to an overflow condition.

Guava's checkedAdd(int,int), checkedSubtract(int,int), and checkedMultiply(int,int) Demonstrated
   /**
    * Demonstrate Guava Release 11's checked addition method.
    */
   public static void demoCheckedAddition()
   {
      try
      {
         final int augend = 20;
         final int addend = 10;
         final int sum = IntMath.checkedAdd(augend, addend);
         out.println(augend + " + " + addend + " = " + sum);

         final int overflowSum = IntMath.checkedAdd(Integer.MAX_VALUE, 1);
         out.println(Integer.MAX_VALUE + " + 1 = " + overflowSum);
      }
      catch (Exception ex)
      {
         err.println("Exception during addition: " + ex.toString());
      }
   }

   /**
    * Demonstrate Guava Release 11's checked subtraction method.
    */
   public static void demoCheckedSubtraction()
   {
      try
      {
         final int minuend = 30;
         final int subtrahend = 20;
         final int difference = IntMath.checkedSubtract(minuend, subtrahend);
         out.println(minuend + " - " + subtrahend + " = " + difference);

         final int overflowDifference = IntMath.checkedSubtract(Integer.MIN_VALUE, 1);
         out.println(Integer.MIN_VALUE + " - 1 = " + overflowDifference);
      }
      catch (Exception ex)
      {
         err.println("Exception during subtraction: " + ex.toString());
      }
   }

   /**
    * Demonstrate Guava Release 11's checked multiplication method.
    */
   public static void demoCheckedMultiplication()
   {
      try
      {
         final int factor1 = 3;
         final int factor2 = 10;
         final int product = IntMath.checkedMultiply(factor1, factor2);
         out.println(factor1 + " * " + factor2 + " = " + product);

         final int overflowProduct = IntMath.checkedMultiply(Integer.MAX_VALUE, 2);
         out.println(Integer.MAX_VALUE + " * 2 = " +  overflowProduct);
      }
      catch (Exception ex)
      {
         err.println("Exception during multiplication: " + ex.toString());
      }
   }

The blog post Handling Very Large Numbers in Java talks about issues with large numbers in Java and the overflow that can occur. As this post recommends, use of BigInteger and BigDecimal is often recommended for such situations. However, these new Guava IntMath "checked" methods provide another alternative for the Java developer who wants to deal with integers, but know when overflow has occurred.

I have shown simple examples of using most of the methods of the new IntMath class in Guava Release 11 [I did not discuss or show IntMath.mod(int,int)]. The next code listing ties all of the above examples together and is followed by the output from running that code listing.

UsingIntMath.java
package dustin.examples;

import static java.lang.System.err;
import static java.lang.System.out;

import com.google.common.math.IntMath;
import java.math.RoundingMode;

/**
 * Simple examples of using Guava Release 11's {@code IntMath} class.
 * 
 * @author Dustin
 */
public class UsingIntMath
{
   /**
    * Demonstrate binomial Coefficient calculation
    * (http://en.wikipedia.org/wiki/Binomial_coefficient).
    */
   public static void demoBinomialCoefficient()
   {
      final int n = 5;
      final int k = 3;
      final int binomialCoefficient = IntMath.binomial(n, k);
      out.println(
           "Binomial Coefficient of n=" + n + " and k=" + k + " is "
         + binomialCoefficient);  
   }

   /**
    * Demonstrate factorial calculation.
    */
   public static void demoFactorial()
   {
      final int x = 5;
      final int factorial = IntMath.factorial(x);
      out.println("Factorial of x=" + x + " is " + factorial);
   }

   /**
    * Demonstrate calculation of greatest common factor (GCF) [called greatest
    * common divisor here].
    */
   public static void demoGreatestCommonFactor()
   {
      final int x = 30;
      final int y = 45;
      final int gcf = IntMath.gcd(x, y);
      out.println("GCF of " + x + " and " + y + " is " + gcf);
   }

   /**
    * Demonstrate calculation of square roots.
    */
   public static void demoSquareRoot()
   {
      final int x = 16;
      final int sqrtX = IntMath.sqrt(x, RoundingMode.HALF_EVEN);
      out.println("Square root of " + x + " is " + sqrtX);
      final int y = 25;
      final int sqrtY = IntMath.sqrt(y, RoundingMode.HALF_EVEN);
      out.println("Square root of " + y + " is " + sqrtY);  
   }

   /**
    * Demonstrate determination of whether an integer is a power of two.
    */
   public static void demoIsPowerOfTwo()
   {
      final int x = 16;
      out.println(x + (IntMath.isPowerOfTwo(x) ? " IS " : " is NOT " ) + " a power of two.");
      final int y = 31;
      out.println(y + (IntMath.isPowerOfTwo(y) ? " IS " : " is NOT " ) + " a power of two.");
   }

   /**
    * Demonstrate exponential power calculation.
    */
   public static void demoExponentialPower()
   {
      final int base = 2;
      final int exponent = 5;
      final int result = IntMath.pow(base, exponent);
      out.println(base + " to power of " + exponent + " is " + result);
   }

   /**
    * Demonstrate IntMath.log10 and IntMath.log2.
    */
   public static void demoLogarithmicFunctions()
   {
      final int x = 10000000;
      final int resultX = IntMath.log10(x, RoundingMode.HALF_EVEN);
      out.println("Logarithm (base 10) of " + x + " is " + resultX);
      final int y = 32;
      final int resultY = IntMath.log2(y, RoundingMode.HALF_EVEN);
      out.println("Logarithm (base 2) of " + y + " is " + resultY);
   }

   /**
    * Demonstrate Guava Release 11's checked addition method.
    */
   public static void demoCheckedAddition()
   {
      try
      {
         final int augend = 20;
         final int addend = 10;
         final int sum = IntMath.checkedAdd(augend, addend);
         out.println(augend + " + " + addend + " = " + sum);

         final int overflowSum = IntMath.checkedAdd(Integer.MAX_VALUE, 1);
         out.println(Integer.MAX_VALUE + " + 1 = " + overflowSum);
      }
      catch (Exception ex)
      {
         err.println("Exception during addition: " + ex.toString());
      }
   }

   /**
    * Demonstrate Guava Release 11's checked subtraction method.
    */
   public static void demoCheckedSubtraction()
   {
      try
      {
         final int minuend = 30;
         final int subtrahend = 20;
         final int difference = IntMath.checkedSubtract(minuend, subtrahend);
         out.println(minuend + " - " + subtrahend + " = " + difference);

         final int overflowDifference = IntMath.checkedSubtract(Integer.MIN_VALUE, 1);
         out.println(Integer.MIN_VALUE + " - 1 = " + overflowDifference);
      }
      catch (Exception ex)
      {
         err.println("Exception during subtraction: " + ex.toString());
      }
   }

   /**
    * Demonstrate Guava Release 11's checked multiplication method.
    */
   public static void demoCheckedMultiplication()
   {
      try
      {
         final int factor1 = 3;
         final int factor2 = 10;
         final int product = IntMath.checkedMultiply(factor1, factor2);
         out.println(factor1 + " * " + factor2 + " = " + product);

         final int overflowProduct = IntMath.checkedMultiply(Integer.MAX_VALUE, 2);
         out.println(Integer.MAX_VALUE + " * 2 = " +  overflowProduct);
      }
      catch (Exception ex)
      {
         err.println("Exception during multiplication: " + ex.toString());
      }
   }

   /**
    * Demonstrate Guava Release 11's checked power method and compare it to
    * other common approaches for determining base multiplied by itself exponent
    * number of times.
    */
   public static void demoCheckedPower()
   {
      try
      {
         final int base = 2;
         final int exponent = 4;
         final int result = IntMath.checkedPow(base, exponent);
         out.println("IntMath.checkedPow: " + base + "^" + exponent + " = " + result);

         out.println(
              "IntMath.pow: " + Integer.MAX_VALUE + "^2 = " +
            + IntMath.pow(Integer.MAX_VALUE, 2));
         out.println(
              "Math.pow(int,int): " + Integer.MAX_VALUE + "^2 = "
            + Math.pow(Integer.MAX_VALUE, 2));
         out.println("Multiplied: " + Integer.MAX_VALUE*Integer.MAX_VALUE);
         out.print("IntMath.checkedPow: " + Integer.MAX_VALUE + "^2 = ");
         out.println(IntMath.checkedPow(Integer.MAX_VALUE, 2));
      }
      catch (Exception ex)
      {
         err.println("Exception during power: " + ex.toString());
      }
   }

   /**
    * Demonstrate division using IntMath.divide.
    */
   public static void demoDivision()
   {
      final int dividend = 30;
      final int divisor = 10;
      final int quotient = IntMath.divide(dividend, divisor, RoundingMode.HALF_EVEN);
      out.println(dividend + " / " + divisor + " = " + quotient);
   }

   /**
    * Main function for demonstrating Guava Release 11's {@code IntMath} class.
    * 
    * @param arguments Command-line arguments; none expected.
    */
   public static void main(final String[] arguments)
   {
      demoBinomialCoefficient();
      demoFactorial();
      demoGreatestCommonFactor();
      demoSquareRoot();
      demoIsPowerOfTwo();
      demoExponentialPower();
      demoLogarithmicFunctions();
      demoCheckedAddition();
      demoCheckedSubtraction();
      demoCheckedMultiplication();
      demoCheckedPower();
      demoDivision();
   }
}

This blog post has attempted to demonstrate the usefulness and ease-of-use provided by Guava Release 11's IntMath class. This class provides numerous convenient method for simplifying common mathematical operations on integers. Guava Release 11 provides essentially the same methods in the com.google.common.math package for longs (LongMath) and similar methods for double's (DoubleMath) and BigIntegers (BigIntegerMath).

No comments: