menu

Wednesday, October 15, 2014

Using Fractional Numbers In Java

Using Fractional Numbers In JavaIntroduction:

     As you know some numbers in decimal system cannot be shown exactly, rather they must be defined as repeating decimal number. For example; 1/3 = 0.33.... or 1/6 = 0.1666... . The same issue is also a fact in binary system that used by computer systems. Lets consider the 7/10 number in binary system that is 111/1010. If we do this divide operation get 0.1011001100..., and see 1100 part is repeating. The same solution can be obtained by the method explained in Figure 1.To understand that a binary representation of a decimal number is repeating, we can both use dividing or writing the number as a/b, abbreviate it and look for b if it is a power of 2.It it is not power of 2 then
its a repeating number.
                                                          
    0.7 * 2 = 1.4  ---> 1 (Take the number left of the decimal brace(.))
    0.4 * 2 = 0.8  ---> 0 (if >1 subtract 1 and continue to multiply)
    0.8 * 2 = 1.6  ---> 1
    0.6 * 2 = 1.2  ---> 1
    0.2 * 2 = 0.4  ---> 0
    0.4 * 2 = 0.8  ---> 0
    0.8 * 2 = 1.6  ---> 1 (We found the repeating part)

 Result = 0.1011001100...  ---> 1100 part is repeating.

Figure 1

How java hold repeating numbers ?

      Now, lets look at how the number 0.7 which is a repeating binary number can be represented in java. In java, fractional numbers are represented according to IEEE 754 (IEEE Standard for Floating-Point Arithmetic) standarts which is used in most of the programming languages. In java, Float data type that can hold 32 bits, uses IEEE 754 single precision format, on the other hand Double data type that can hold 64 bits, uses IEEE 754 double precision format.In double precision 1 bit is used for sign, 11 bits are used for exponent, and 52 bits are used for mantissa(significant bits), in single precision 1 bit is used for sign, 8 bits are used for exponent, and 23 bits are used for mantissa.However in mantissa there exists one extra bit which has value 1 by default, that is used for normalization. That means totally we have 53 bits mantissa in double-precision and 24 bits  mantissa in single-precision.(see Figure 2.)

The behaviour of java is to find out the most accurate result by using either 52 or 53 bits in double-precision and using 23 or 24 bits in single-precision and do rounding if necessary.The most accurate result may slightly greater than or less than the required result.
                                       
                                         Sign        Exponent         Mantissa
 1 
11
 52 + 1
      64 bit double-precision format

 1
 8
 23 + 1
  32 bit single-precision format 

  Figure 2

Let's see how 0.7 can be shown in Double and Float data types.

double repeatingFractionNumber = 0.7;
in binary; 0.1011001100110011001100110011001100110011001100110011(52.bit)...
  
     Here, in double-precision, the bits after the 52nd bit are truncated.According to IEEE 754 standarts if the 52nd bit is 1 its left as it is.In this case since we truncated the number, we get slightly less number than 0.7.(Since the 53nd bit is zero here, its enough to use 52 bits. If we could get nearer number when we use 53nd bit with rounding it to 1, we would have been use 53nd bit.)

If we reconvert the 0.1011001100110011001100110011001100110011001100110011 number to decimal system again we get 0.6999999999999999555910790149937383830547332763671875.

We can get this result by running the below code fragment.

BigDecimal bd = new BigDecimal(repeatingFractionNumber);
System.out.println("0.7 in java actually is : " + bd);

If the 52nd bit and 53nd bits are 1, both of them are used, if 52nd and 53nd bits are 0, depending on the nearliness either the number left as it is or 53nd bit is rounded to 1. On the other hand, if 52nd bit is 0 and 53.bit 1, depending on the nearliness either the number left as it is or 52nd bit is rounded to 1 and 53nd bit is omitted, if 52nd bit is 1 and 53nd bit is 0, depending on the nearliness either the number left as it is or 53nd bit is rounded to 1. If we make rounding the result will be greater than the actual result, otherwise it will be less than it.(The same situation is also valid in single-precision when using 23 or 24 bits.)

To show how to use rounding to get a nearer number lets consider 0.1 in decimal system. If we convert 0.1 to binary system we get,
0.000110011... 0011 with 0011 part repeating.
(The number that we can get from 53 bits is 0.09999999999999999167332731531132594682276248931884765625, while the number we can get from rounding 52nd bit to 1 is 0.1000000000000000055511151231257827021181583404541015625 which is closer to 0.1)

In 64 bit double-precision this number will be (The zeros after 0. are not meaningful so they are not included in 53 bits)
0.0001100110011001100110011001100110011001100110011001101(52nd bit changed to 1 and 53nd bit and later are omitted)

If we convert 0.0001100110011001100110011001100110011001100110011001101 to decimal system again we get 0.1000000000000000055511151231257827021181583404541015625 number which is greater than 0.1

Now we'll see how 0.7 can be shown with float data type which is 32 bit single-precision format.

float repeatingFractionNumber = 0.7f;
In binary; 0.101100110011001100110011(24 bits)... (Java choose to use 24 bits here, since the number we get with 24 bits (0.699999988079071044921875) is closer to 0.7 than we could get from 23 bits(0.69999992847442626953125)

Since the 24nd bit is 1 we didn't do any rounding.If there is no rounding the result will be less than the desired result.

Below is the code fragment to show 0.7 in float data type in java.

BigDecimal bd = new BigDecimal(repeatingFractionNumber);
System.out.println("0.7f  in java actually is : " + bd); 

Up to now, we look for how the double and float numbers are hold in java according to IEEE Floating point standarts in double and single precision.The basic principle is to use 52 bits or 53 bits in double-precision, and to use 23 bits or 24 bits in single-precision to get the nearest result whether its less or more than the actual result.In this approach, lets consider the continuosly added double or float numbers.When we continue to add the numbers , the rounding operation will be continue and the total error may continuosly increase. That means if you do scientific calculations its ok to use Double and Float, however its not suitable if you do financial calculations. We have to use some methods to minimize the total error. We now examine that methods with examples.

Using BigDecimal:

See the below 2 examples use with Double.

Example 1:

double d1 = 0.1, d2 = 0.2, d3 = 0.3;         
if (d1 + d2 == d3)
 System.out.println("0.1+0.2=0.3");
else
 System.out.println("0.1+0.2=?");

If we run this piece of code we get 01+02 = ?. Its not surprising for us, since we now know how double numbers are hold in java.
Remember,
0.1  = 0.1000000000000000055511151231257827021181583404541015625
0.2 = 0.200000000000000011102230246251565404236316680908203125
0.3 = 0.299999999999999988897769753748434595763683319091796875
Therefore 0.1 + 0.2 is greater than 0.3.

Example 2:

double totalValue = 7.0;
int numberOfOrders = 0;       
for (double orderValue = 0.7; totalValue >= orderValue ;) {
  totalValue -= orderValue ;       
  numberOfOrders ++;
}              
System.out.println("totalValue ="+totalValue );
System.out.println("numberOfOrders ="+numberOfOrders);

When we run this code fragment we see the total value is 0.6999999999999988, and number of orders are 9 while the expected result is total value is 0 and number of orders are 10.

Lets use BigDecimal in the same examples.

Example 1:

BigDecimal d1 = new BigDecimal("0.1");
BigDecimal d2 = new BigDecimal("0.2");
BigDecimal d3 = new BigDecimal("0.3"); 
if (d1.add(d2).equals(d3))
 System.out.println("0.1+0.2=0.3");
else
 System.out.println("0.1+0.2=?");

The result is as expected "0.1+0.2=0.3".

Example 2(Method 1):
           
BigDecimal totalValue = new BigDecimal("7.0");
int numberOfOrders = 0;
final BigDecimal ORDER_VALUE = new BigDecimal("0.7");
for (BigDecimal orderValue ORDER_VALUE ;                             
  totalValue.compareTo(orderValue ) >= 0;) {
  totalValue totalValue.subtract(orderValue );
  numberOfOrders ++;
} 
System.out.println("totalValue =" + totalValue );
System.out.println("numberOfOrders =" +numberOfOrders );

In this case we get totalValue zero and numberOfOrders as 10.

The important point with this approach is, to get the desired result we have to use the constructor of BigDecimal which expects String as parameter. The constructor with double parameter will not solve our previous problems.With this technique, we can use setScale method of BigDecimal class to change the scale.

Example 2 (Method 2):

double totalValue= 7.0;
int numberOfOrders = 0;
final int DECIMAL_PLACE = 2;      
for (double orderValue = 0.7; totalValue >orderValue ;) {
  totalValue round(totalValue -= orderValue);
  numberOfOrders ++;
 }                
System.out.println("totalValue="+totalValue);
System.out.println("numberOfOrders ="+numberOfOrders );

double round(Double d) {   
   BigDecimal bd = new BigDecimal(d.toString());
   bd = bd.setScale(DECIMAL_PLACE , BigDecimal.ROUND_HALF_EVEN);
   d = bd.doubleValue();
   return d;
}

We can use this method if we don't want to use BigDecimal's add, substract... methods which are slower.For each operation we do rounding by using BigDecimal setScale method with the desired scale and round mode and return the result as double.Be careful to use the BigDecimal's constructor which expects String.
We use  BigDecimal.ROUND_HALF_EVEN for round mode .This mode minimizes the total error and if we have equal distance  below and above border and  if the number next to the last decimal place is even behave as ROUND_DOWN, if it is odd behave as ROUND_UP. i.e; for  0.685  with 2 decimal place rounded to 0.68 while  0.675 with 2 decimal place rounded to 0.68.
However for this behaviour to be consistent, we again have to use BigDecimal's String constructor.Otherwise, since  the actual value of 0.685 in memory is 0.685000000000000053290705182007513940334320068359375 the rounded result will be 0.69.

When we use BigDecimal we can minimize the error rate and can use the desired round mode. However, using BigDecimal instead of primitive types is both more complicated and may cause to have performance issues.i.e; in my computer Example 2 (Method 1) is 50 times slower than Example 2 and Example 2 (Method 2).(In this test I changed the totalValue to 7000000.0 for clarity). If we need better performance we can use penny calculation by using int and long variables.In this case we have to manage the decimal point part.

Using int or long:

Implementation of Example 2 with primitive variables.

int totalValue= 700; // 7.0 is 700 penny
int numberOfOrders= 0;         
//0.7 is 70 penny
for (int orderValue= 70; totalValue >orderValue;) {
 totalValue-= orderValue;       
 numberOfOrders++;
}              
System.out.println("totalValue(in penny)="+totalValue);
System.out.println("numberOfOrders="+numberOfOrders);

In this technique we could use int variable for 9-10 place numbers and lonf for 18-19 place numbers.If we need more place we have to use BigDecimal.We don't need rounding here, however we have to manage the decimal point method if we need decimal point.

Rounding methods:

     We mention about that we can use BigDecimal for rounding in the desired level.The performance problem of BigDecimal is also valid in rounding , instead of BigDecimal's round method we can use two alternative methods..

   1- BigDecimal.setScale() method:
                          
Double d = some double;
BigDecimal bd = new BigDecimal(bd.toString());
bd = bd.setScale(decimalPlace, BigDecimal.ROUND_HALF_EVEN);
d = bd.doubleValue();

   2- Math.round() method:

double totalValue = 7.0;
int numberOfOrders= 0;
final double DECIMAL_PLACE_MULTIPLIER = 100; // if decimal place 2 use //100, if 3 use 1000 etc.
for (double orderValue= 0.7; totalValue >= orderValue;) {
 totalValue round(totalValue -= orderValue);
 numberOfOrders++;
 }              
System.out.println("totalValue ="+totalValue );
System.out.println("numberOfOrders="+numberOfOrders);
       
double round(Double d) {   
        d = Math.round(d * DECIMAL_PLACE_MULTIPLIER)                / DECIMAL_PLACE_MULTIPLIER;
        return d;
 }

With this method we can get 30 times faster results for 7000000 total value. However, this method behave always s ROUND_UP for numbers that has equal distance for below and above borders.

    3- Casting:

double totalValue = 7.0;
int numberOfOrders= 0;
final double DECIMAL_PLACE_MULTIPLIER = 100; // if decimal place 2 use //100,if 3 use 1000 etc.
for (double orderValue= 0.7; totalValue >= orderValue;) {
  totalValue round(totalValue -= orderValue);
  numberOfOrders++;
}              
System.out.println("totalValue ="+totalValue );
System.out.println("numberOfOrders="+numberOfOrders);

double round(double d) {
   long l  =(long) (d < 0 ? d * DECIMAL_PLACE_MULTIPLIER - 0.5 : d *                             DECIMAL_PLACE_MULTIPLIER + 0.5);
   return l / DECIMAL_PLACE_MULTIPLIER ;
}

The basic principle of this technique using decimal place multiplier, getting desired decimal place and adding 0.5 to obtain ROUND_UP behaviour for the equal distance number to below and above borders and.

With this method we can get 60 times faster results than BigDecimal round method and 2 times faster than Math.round()  method with total value 7000000.

However, this method again always use ROUND_UP for numbers that has equal distance for below and above borders.You may build your own implementation to develop BigDecimal's ROUND_HALF_EVEN like method.

Note on using Float and Double: Another point is to consider Double.doubleToLongBits()  and Float.floatToIntBits() methods  when using float and double in hashcode implementation, since the values like NaN, Infinity cannot be used directly and have to be used with the long(for double since its 64 bits) and int(for int since its 32 bits) values that are counterpart of the bit representation of those values.

Conclusion:

     In java when you're dealing with fractional numbers, if the required result has to be exact like financial calculations using float or double data types can result wrong behaviours. The reason is the repeating fractional numbers .To solve the issue we can use BigDecimal with String parameter's constructor for calculations. Meanwhile if we need scaling we can use setScale method of BigDecimal with the desired round method like ROUND_HALF_EVEN to minimize the total error.However using BigDecimal is not only complicated but also has some performance problems, especially when dealing with large number of numbers.In this case we may use penny calculation with int and long values, and calculate decimal point at the end of the calculation.But be careful when you need more than 18-19 place values adaing have to use BigDecimal.In addition, we may use Math.round() or Cast techniques instead of BigDecimal's setScale method.

If we design according to maximum scale that we would have, we could minimize the loss of precision because of rounding.(i.e; if we have only fractional numbers with 2 scale, the maximum scale we can obtain from the multiplication of those numbers will have max 4 scale, so we have to use 4 as scale.)However even in this case , because of the previosly mentioned issues about holding the fractional numbers in java, we may need rounding.Using the ROUND_HALF_EVEN round mode we can minimize the total error.The rounding mode must be same in all modules of all systems that are communicating, otherwise we may get different results from different modules.

Also, if we don't do any rounding, when the number, i.e; 2098.81999, inserted directly to database say to a column with scale 2, will be resulted in 2098.81.This number must ve 2098.82 if you don't want ROUND_UP mode.The same way if the need to compare sum() of a column in database with a number calculated in java, the ROUND_HALF_EVEN mode will be the best choose.

References and Resources:

Joshua Bloch. Effective Java - Programming Language Guide

http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html

http://mindprod.com/jgloss/floatingpoint.html

You can download the source code from here.

No comments:

Post a Comment