[Adept Open Source Library] Fractions are Useful Too

[Paul Marrington]

Fractions are Useful Too

There was a time before floating point co-processors and built-in floating point arithmetic that some systems chose to hold real numbers as fractions.

The Advantages of Fractions

1. Some numbers can be held more accurately as fractions. 1/3 cannot be accurately represented in floating point.
2. All fractions that do not cause an overflow are accurate, whereas floating point is always an approximation. It's common, for example, to see a result of 0.999999999998 when the result should have been one. This is particularly true when passing the number around. Writing a floating point to a relational database and retrieving it again for comparison to the original value can return false. This is because the floating point representation may change inside different systems.
3. The calculations are faster than floating point emulators. This advantage doesn't hold out against dedicated floating point hardware.
4. It was very cool for numbers that could be displayed as a fraction. The human mind mostly finds it easier and quicker to visualise two and an eigth, as compared to 2.125.
5. Some areas of use are more comfortable with fractions than decimals. Shares in a property or horse, for example, are commonly things like 1/3, 1/2 and 1/6.

The Disadvantages of Fractions

1. Floating point holds a more limited representation. A Java long is only 19 decimal digits. This is still a big number. If a fraction were to represent microseconds, it would hold nearly 585 thousand years. If course if it were to represent nanoseconds, it would be limited to 585 years.
2. All fractions that do not cause an overflow are accurate. Yes, this is a disadvantage also. Accuracy requires space. Each calculation can potentially increase the size of the denominator, thereby decreasing the largest number that can be held. 1/3 + 1/5 = 8/15. The largest possible number has now been reduced by 1/3. This is an implementation restriction that could be eradicated by having a separate whole part to fraction. A lot of the internal maths becomes more complicated and expensive, so I have chosen to keep the limitation.
3. Fractions are not as fast as integers at arithmetic. To minimise the issues with lost maximum whole parts, each calculation reduces the fraction to the smallest it can be. 1/3 + 1/6 is kept as 1/2, not 3/6. It might be possible to make the Fraction class smarter and only do the expensive greatest-common-denominator when converting to a viewable string or when a calculation is at risk of overflowing.

The Fraction Class

The Fraction class is an immutable class for creating and manipulating fractions. Immutable means that once a fraction has been created it cannot be changed, operations create a new instance. So,

Fraction result
  = new Fraction( 1, 1, 2)
    .times( new Fraction( 2, 0, 0));

 

creates 3 instances of Fraction. Creating these fractions is non-trivial since the fraction is normalised as part of the operation. Don't be scared. Normalisation isn't that intensive, but it is well to be concious that any method call can take valuable CPU time. I believe that it's always a good idea to save data in a variable with a lifetime to match it's static nature. In the previous example, given that I may often want to multiply by 2, I would create a final static called two and create it only once.

Why Immutable?

There are very few uses for immutable classes outside of the primative wrappers provided in the standard library. Fractions are one of them. Here are the benefits:

1. No synchronisation needed if used in threaded code. It can't change so it won't be changed accidentally.
2. The internal data is private, so it can be open to the world for read access safely.
3. They are safe from fiddly or unexpected side-effects.

Besides, an immutable class is easier to implement.

Creating a Fraction

The standard numerical constructor was shown before. It takes 3 long values for whole part, numerator and denominator. There is also a short form that just takes a whole number. Because whole numbers are used commonly and don't require normalisation, this becomes a good optimisation technique.

Fractions often come from text sources, so there's also a constructor that takes a string. It provides a more flexible way of representing a fraction. It can be a standard whole-numerator/denominator (i.e. 5-3/16). The whole part can be separated from the numerator by a space, a colon or a dash. String fractions can be decimal representations (as in 5.1875). Lastly, just for fun, it can be a percentage (10% == 1/10). With text entry comes the possibilty that the data cannot be interpreted as a fraction or decimal. In these cases, a public variable empty is set. If you want an exception, throw one. Since the fraction may be only part of the text, a public int is set to the next index in the string not used to build the fraction.

String fractionString = "1/3rd";
Fraction result = new Fraction( fractionString);
if (result.empty)
  throw new NumberConversionException(
    fractionString+" not a fraction");
String rest = fractionString.substring( result.after);
assertTrue( rest.equals( "rd");

 

The Greatest Common Denominator

The greatest common denominator is the largest integer that divides into both numbers without a remainder. Obviously it is useful in fractions as we have discussed above. It has other uses, too. Some PKI formulae use it. If the GCD (for short) is 1 then both numbers are relatively prime.

if (Fraction.greatestCommonDenominator( numerator, denominator) == 1)
 System.out.println( numerator+"/"+denominator+" are relatively prime");

 

Note that this is a static method so it can be used without generating a fraction.

Fractional Output

A Fraction instance has a toString() method that will display the fraction in the form W-N/D.

assertTrue( new Fraction( "1.5").toString().equals( "1-1/2");
assertTrue( new Fraction( "24%").toString().equals( "6/25");

 

It also has a toHTML() method that uses subscripts and superscripts to display a fraction. One and a half would display as 1^1/2 If you want to do anything else with the fractions, the numerator and denominator are public (if final).

// Display a fraction as a decimal value.
System.out.println(
  (Double) fraction.numerator / (Double) fraction.denominator);

 

Sorting and Maps

The Fraction class implements Comparable, equals() and hashCode(), so it can be used for sorting and as HashMap keys.

Fractional Maths

The Fraction class only implements basic math at this stage. It's all I've needed for dealing with shares.

• negative()
• inverse()
• plus()
• minus()
• times()
• divide()

So, if you need to play with fractions, this class is freely available in the Adept library at http://library.marringtons.com,

--
Posted by Paul Marrington to Adept Open Source Library at 7/07/2005 09:53:00 AM