Fixed, Floating, and Exact Computation with Java's Bigdecimal

Calculations just got easier

Mike is the leader of JSR 13 (decimal enhancements), Josh is the author of Effective Java (Addison-Wesley, 2001), and Joe is Sun's floating-point expert for Java technology. They can be contacted at mfcuk.ibm.com, joshua.blochsun.com, and joe.darcysun.com, respectively.

When to Use float or double, When to Use BigDecimal

Decimal data types are widely used in commercial, financial, and web applications, and many general- purpose programming languages have either native decimal types or readily available decimal arithmetic packages. Hardware support for decimal types is planned, and current drafts of the IEEE 754 revision committee contain the decimal types and arithmetic expected to be included in the revised floating-point standard.

Since the 1.1 release, the libraries of the Java programming language supported decimal arithmetic via the java.math.BigDecimal class. With the inclusion of JSR13 into J2SE 1.5, BigDecimal now has true floating-point operations consistent with those in the IEEE 754 revision.

In this article, we first explain why decimal arithmetic is important and the differences between the BigDecimal class and binary float and double types. We then cover what's new in the J2SE 1.5 BigDecimal class. For tips on when to use BigDecimal, see the accompanying text box entitled "When to Use float or double, When to Use BigDecimal."

Why Decimal Arithmetic Is Important

Decimal arithmetic has been used for thousands of years, and over time has been refined to become the Indo-Arabic place value system we use today. This system, called "algorism," is the arithmetic taught at school and is pervasive in commercial calculations (the majority of numeric data in commercial databases are held as decimals, and nearly all the rest are integers).

For this reason, when computers were first built, many of them used decimal arithmetic (and even decimal addressing). However, it was shown that binary circuitry was more efficient, and when fractions were involved, binary floating-point (the float and double types in Java) is optimal for purely mathematical calculations.

Unfortunately, binary floating-point numbers cannot represent common decimal fractions exactly. In a decimal system, the numerical values that can be represented are:

significand•10^exponent

while the numbers that can be represented in a binary system are:

significand•2^exponent

In both cases, the significand and exponent are integers. Therefore, pure integer values can be represented exactly in binary and decimal (and in any other integer base). In contrast, the set of fractional values that can be represented exactly by a finite number of digits varies by base. In particular, as in Table 1, common decimal fractions like 0.1 do not have a terminating binary representation. Just as 1/3 is a repeating fraction in decimal, 1/10 is a repeating fraction in binary.

All binary fractions can be represented in decimal, but the reverse is not true. Therefore, the main advantage of doing computation in decimal is that everyday numbers such as 0.1 can be represented exactly. While a binary approximation can be very close to the exact answer, some applications demand exactness because even a tiny inaccuracy can lead to unacceptable errors in practice.

For example, consider a 5 percent sales tax on a $0.70 telephone call, rounded to the nearest cent. The calculation for this might be 1.05×0.70. The exact answer should be 0.735, which rounds to $0.74, but if doubles are used for the calculation, then the result will be slightly less than the exact answer and so would round down to $0.73. These one-cent errors tend to be systematic and over millions of calculations rapidly add up to very significant amounts. (For more examples, see http://www2.hursley.ibm.com/decimal/.)

Avoiding these kinds of errors is theoretically possible, using detailed error analysis and careful programming, but it is much safer and easier to use a decimal data type, which can give exact answers where expected. In the Java programming environment, the BigDecimal class is provided precisely for this purpose.

Decimal Floating-Point?

The original BigDecimal class supported two styles of computation, exact arithmetic and rounding to a given scale (the scale of a BigDecimal is the number of fractional digits to the right of the decimal point—it is the negative of the exponent shown above). All integer values, therefore, have a scale of zero. The fractional value 0.5 has a scale of 1 and the fractional value 0.50 has a scale of two; BigDecimal distinguishes between these numerically equal values with a different representation. This is useful for fixed-point computation, in which the location of the decimal point in the desired result is fixed; in other words, where the number of fractional digits is a known constant.

For example, if the result should be in dollars, the scale is 0; if the result should be in dollars and cents, the scale is 2; if the result should be in dollars and mills (tenths of a cent), the scale is 3. The original BigDecimal arithmetic methods that add, subtract, and multiply only return exact results, so to implement fixed-point semantics, each arithmetic operation needs to be followed by a setScale call. Example 1 is the earlier tax calculation.

The new BigDecimal supports a third style of computation—floating-point. In floating-point computation, it doesn't matter where the digits of the result are in relation to the decimal point; the decimal point "floats" in different positions. Floating-point computation returns either an exact or a fixed-width result. To a first approximation, returning a fixed-width result allows floating-point operations to execute at the same speed regardless of the exponent value.

This style of calculation is increasingly useful because decimal calculations are now more frequent and complex than before. For example, interest on financial accounts is now usually calculated daily rather than quarterly, telephone calls in Europe are priced by the second, taxes are adjusted to finer precision (sometimes to four or five digits), and financial calculations are subject to more analysis, such as profiling to detect money laundering. All of these operations are simplified if a floating-point arithmetic is used (with a high precision so that the results are exact, if possible).

The advantages of decimal floating-point are now widely recognized. The decimal floating-point formats proposed by the IEEE 754 revision committee are being implemented in hardware by IBM, and the ISO C and C++ committees are working on adding the same types to those languages.

MathContext

The floating-point style of computation is implemented by having overloaded methods that accept an additional context parameter to specify how any rounding should occur. This context, held in a java.math.MathContext object, contains a precision and rounding mode. The precision specifies how many digits to have in the result and the rounding mode specifies how any discarded digits affect the result. For example, if you have two BigDecimal objects A and B with values 2 and 3, respectively, then the code segment in Example 2(a) would give C the value 0.6666667 (that is, rounded to seven digits using the given rounding mode). Using a different rounding mode, Example 2(b) would give C the value 0.6666666. Any precision may be chosen, including very large ones, and a precision of 0 indicates unlimited precision (as in the existing methods where no context is specified).

The MathContext class includes four constants; one for unlimited precision and one matching each of the proposed IEEE 754 decimal floating-point formats. We strongly recommend that you use one of the latter where possible to maximize potential performance improvements in the future. For applications where up to 16 digits of precision are sufficient, we suggest MathContext.DECIMAL64; for higher precisions up to 34 digits, use MathContext.DECIMAL128.

New Methods and Constructors

In addition to the MathContext variants of existing methods, there are a number of new methods that greatly enhance the usefulness of the class. These include:

• divideInteger (where the result is always an integer), remainder, divideAndRemainder, plus, and pow (raise to power) for arithmetic.
• precision, which returns the number of significant digits in a BigDecimal.
• round, which rounds a number according to a MathContext.
• byteValueExact, shortValueExact, intValueExact, and longValueExact, which convert a BigDecimal to a primitive integer and throw an exception if the conversion is not exact.
• scaleByPowerOfTen, which multiplies a BigDecimal by a power of 10 efficiently.
• stripTrailingZeros, which returns a BigDecimal with the same value and the shortest possible coefficient.
• toEngineeringString, which is an alternative to toString (which uses engineering notation if an exponent is needed).

New constructors have been added, which allow creation directly from a char array (or subarray), int, or long. All constructors also have MathContext variants, allowing rounding during construction. There's also a new static valueOf factory that constructs a BigDecimal from a double using the same rounding as Double.toString.

RoundingMode

In the old BigDecimal, rounding modes are represented by constant ints, as in Example 1. These remain, for compatibility, but a new java.math.RoundingMode enum has been added. This enumeration class makes the rounding modes abstraction available in a robust way that is independent of BigDecimal. Example 2 shows a new RoundingMode in use.

Implementing Exact Divide

The original BigDecimal class had methods for exact add, subtract, and multiply whose logical operands were just the two numbers in question. However, the divide operations required additional information—either an implicit or explicit scale for the result and an optional rounding mode. BigDecimal now has a two-operand exact divide method, too: If the exact quotient is representable as a BigDecimal, that value is returned; otherwise, an exception is thrown.

The main implementation challenge for this is dealing with repeating decimal fractions such as 1/3 or 29/33. When doing division by hand, loops in the digit sequences can be observed; but adding that sort of detection mechanism to the division code would be awkward. Another possibility would be to reuse the existing high-precision output of divide taking a MathContext. If it was possible to compute an upperbound, say n, on the number of digits in an exact quotient (if such a quotient exists), the divide that rounds to a given precision could be used to compute the exact quotient, too. If the n digit quotient wasn't exact, no exact quotient exists. We will now derive the necessary bound.

First, consider the fraction a/b, with a and b as integers. Next, we'll remove common factors from a and b to get a' and b' where a' and b' are mutually prime. For example, 76/100 is 17/25 after removing common factors: a/b=a'/b'. Now, a'/b' has a nonterminating decimal expansion if, and only if, b'=2ⁱ5^j from some integer i and j greater than or equal to zero. Why is this true? Take a finite sequence of fractional digits, like 0.34902. This fraction is equal to an integer divided by a power of 10; in this case, 34902/100000. Since 10=2×5, in reduced form, all terminating fractions have a denominator like 2ⁱ5^j. For example: 34902/100000=34902/10⁵=34902/(2⁵5⁵)= 17451/(2⁴5⁵).

Going in the other direction, we will now prove that if a quotient is equal to c/2ⁱ5^j, it has a terminating decimal expansion.

Assume i>j, multiply numerator and denominator by 5^i-j:

(c×5^i-j)/(2ⁱ5^j×5^i-j)=(c×5^i-j)/(2ⁱ5ⁱ)=(c×5^i-j)/10ⁱ

Because (c×5^i-j) is just an integer, dividing by 10ⁱ just moves the decimal point. Therefore, all c/2ⁱ5^j have a terminating decimal expansion. Therefore, to bound the number of digits of a'/b', we only need to consider a'/2ⁱ5^j.

Since the number of digits of a product is the sum of the number of digits of the two factors, we therefore only have to consider the number of digits in a' and the number of digits in 1/2ⁱ5^j. If you take the reciprocal of a power of 10, the result only needs one nonzero digit; for example 1/1000=.001. Therefore, it is the difference between i and j that affects how many digits the reciprocal will have. Additionally, the reciprocal of a power of 2 usually needs more digits than a power of 5 with the same exponent. (Try it!) The digits of the reciprocal of a power of 2 are powers of 5:

1/2¹=1/2=0.5 (5¹=5)
1/2²=1/4=0.25 (5²=25)
1/2³=1/8=0.125 (5³=125)

and the digits of the reciprocal of a power of 5 are powers of 2:

1/5¹=1/5=0.2 (2¹=2)
1/5²=1/25=0.04 (2²=4)
1/5³=1/125=0.008 (2³=8)

Using this observation and some algebra, which we'll omit, we get this bound for the number of nonzero digits for 1/2ⁱ5^j: max(ceil((i-j)•log10(5)),ceil((j-i)• log10(2)),1)max(ceil((i-j)•0.7),ceil((j-i)• 0.302),1).

Given the i and j for b'=2ⁱ5^j, we can use this tight-bound calculated above. However, finding a' and b' and then i and j is expensive, and we would prefer to avoid that cost for an already expensive divide operation. So, we want to derive a looser bound that needs less factoring information. We get the longest results when b' is a power of 2. So, without factoring, we assume b is a power of 2. The essence of the approach is, based on the number of digits of b, find the smallest power of two that has more digits and use that power of 2 in the formula above. In other words, maximize i and set j to zero. This gives a final bound of ceil(10×precision(b)/3)4×precision(b).

So, if a/b has an exact quotient, it will need no more than precision(a)+ceil(10×precision(b)/3) digits.

DDJ