http://www.developer.com/net/vb/article.php/3694546/Implementing-a-Decimal-to-Fraction-Class-with-Operator-Overloading.htm

Back to article

Implementing a Decimal-to-Fraction Class with Operator Overloading


August 15, 2007

Introduction

You don't see overloaded operators used that much in custom code. And, in few business applications have I seen a request for fractions, but there was such a request made of me recently. Following a search on the web. I discovered news groups and Q&A sites where some of you did request a Fraction's class. So, I thought I'd share a solution.

In this article, you will learn how to implement a Fraction's class—which is ideally suited for overloaded operators, how to overload operators in Visual Basic, and get a quick reminder from your college days on the Euclidean algorithm for calculating the greatest common divisor.

An Overview

Turning a decimal number into a fraction encompasses a couple of specific steps. (There may be a faster, smaller way to convert decimals into fractions, but this solution works and uses some pretty neat elements of the .NET framework.) To convert a decimal number into a fraction, first note that .2 is equivalent to 2/10ths; thus, to solve the problem programmatically you need to:

  • Save the sign
  • Store the whole number
  • Find the numerator
  • Find the denominator
  • Find the greatest common divisor and reduce the fraction

To complete a Fraction class and make it generally useful, you also want to support basic arithmetic operations on fractions and mixed arithmetic on fractions and decimal (or double) numbers. All of these elements are described in the remainder of this article with a complete code listing at the end of the article.

Determining the Sign with Regular Expressions

You can start anywhere, but logically people in the West are oriented to reading from left to right, so that's where you will start. Assuming you have a decimal (double or single) number or a string representing the same, you can strip and store the sign of the number. The following fragment uses a Regular Expression to determine whether a string—you can easily convert numeric strings to and from a string or numeric representation—contains a negative sign and then you store the sign as an integer—1 or -1.

Private Sub SetSign(ByVal value As String)

   If (Regex.IsMatch(value, "^-")) Then
      Sign = -1
   End If

End Sub

The Regular Expressions "^-" simply checks for a – symbol at the beginning of the input string.

Storing the Whole Number

The whole number is as easy to store as the minus sign. You could convert the string to an integer that would do the job for you. You could use Math.Abs to get the number as an absolute value (because you stored the sign), or you could extract the substring, from left to right, up to the index of the decimal point. The latter is the technique demonstrated in the SetWholePart method that will be added to the Fraction class.

Private Sub SetWholePart(ByVal value As String, _
                         ByVal index As Integer)

   Dim whole As String = value.Substring(0, index)
   If (whole.Length > 0) Then
      WholeNumber = Convert.ToInt32(whole)
   End If

End Sub

The index of the decimal point is returned from the CheckNoDecimalPoint method, shown next.

Private Function CheckNoDecimalPoint(ByVal number As Double) _
   As Integer

   Dim index As Integer = number.ToString().LastIndexOf(".")

   If (index = -1) Then
      WholeNumber = Convert.ToInt32(number)
   End If

   Return index

End Function

Finding the Numerator

The easy work is done. Next, you need to find the numerator (and denominator) from the mantissa or the decimal (or fractional) part of the number. The answer is simple: The decimal number without the decimal point is the numerator. For example, 3.2 has a mantissa of .2. The mantissa .2 is 2/10ths, so clearly the mantissa reveals the numerator of the fraction.

The method SetFractionalPart orchestrates setting the numerator and denominator by stripping the mantissa from your input value.

Private Sub SetFractionalPart(ByVal value As String, _
                              ByVal index As Integer)
   Dim fraction As String = value.Remove(0, index + 1)

   If (fraction.Length > 0) Then
      SetFractionalPart(fraction)
      _numerator = Convert.ToInt32(fraction)
      SetDenominator(fraction)
      ReduceWithGcd()
   End If
End Sub

SetFractionalPart clearly shows that you Remove all of the input value up to and including the decimal point and then convert the remaining digits to the numerator store as an integer.

Finding the Denominator

The denominator is also pretty straightforward. The denominator is always 10nth where n is the length of the numerator. For example, a numerator of 234 has a denominator of 1,000 or 103. You can use Math.Exp and the length of the numerator to calculate the denominator (as shown next).

Private Sub SetDenominator(ByVal fraction As String)
   Denominator = Math.Pow(10, fraction.Length)
End Sub

The field fraction is set in an overloaded SetFractionalPart method that truncates the length of the decimal number to eight characters to ensure that it fits in an integer. (If you need a longer fraction, use a long data type.) Here is the overloaded SetFractionalPart method.

Private Sub SetFractionalPart(ByRef fraction As String)
   If (fraction.Length > 8) Then
      fraction = fraction.Substring(0, 8)
   End If

   _fractionalNumber = _
      Math.Round(Convert.ToDouble("." + fraction), 8)
End Sub

Factoring and Reducing with the Euclidean Algorithm

The final step is to find the greatest common divisor and reduce the numerator and denominator by this divisor. You can use the Euclidean algorithm—discovered by Euclid around 300 BC—that uses division, modular arithmetic, and remainders to quickly resolve the greatest common divisor. Here is a non-recursive Euclidean Gcd algorithm and a helper function that reduces the fraction.

Private Function Gcd(ByVal num As Integer, _
                     ByVal den As Integer) As Integer

   If (den Mod num = 1) Then Return 1
   While (den Mod num <> 0)
      Dim temp As Integer = num
      num = den Mod num
      den = temp
   End While

   Return num

End Function


Private Sub ReduceWithGcd()

   Dim divisor As Integer = Gcd(_numerator, _denominator)
   _numerator   = _numerator / divisor
   _denominator = _denominator / divisor

End Sub

That's it. You are finished. I will wrap up the discussion with some examples of overloaded operators that will permit arithmetic operations on Fraction objects.

Implementing Custom Operators

Overloaded operators are shared methods that accept the number and type of arguments based on the operator count. For example, - (subtraction) is a binary operator, so to support Fraction subtraction you need a shared method that takes two Fraction arguments. Operators also use the operator keyword. Here is an implementation of the subtraction operator for your Fraction class.

Public Shared Operator -(ByVal lhs As Fraction, _
                         ByVal rhs As Fraction) _
   As Fraction
   Return New Fraction(rhs.Number - lhs.Number)
End Operator

Operators are often perceived to be hard, but they are pretty intuitive. For the most part, the rule is that you need to implement symmetric operations. For example, if you implement subtraction, you should then implement addition. The other rule is don't add side effects or change the understood behavior of an operator. For example, the addition operator should perform some kind of arithmetic operation.

Listing 1 contains the complete implementation of the Fraction class, including several examples of overloaded operators for you to experiment with.

Listing 1: The complete listing of the Fraction class.

Public Class  Fraction

   Public Sub New(ByVal number As Double)
      _number = Math.Round(number, 8)
      Dim value As String = _number.ToString()

      SetSign(value)
      Dim index As Integer = CheckNoDecimalPoint(number)
      If (index = -1) Then Return

      SetWholePart(value, index)
      SetFractionalPart(value, index)

   End Sub

   Public Shared Operator +(ByVal lhs As Fraction, _
                            ByVal rhs As Fraction) _
      As Fraction
      Return New Fraction(rhs.Number + lhs.Number)
   End Operator

   Public Shared Operator -(ByVal lhs As Fraction, _
                            ByVal rhs As Fraction) _
      As Fraction
      Return New Fraction(rhs.Number - lhs.Number)
   End Operator

   Public Shared Operator =(ByVal lhs As Fraction, _
                            ByVal rhs As Fraction) _
      As Boolean
      Return rhs.Number = lhs.Number
   End Operator

   Public Shared Operator <>(ByVal lhs As Fraction, _
                             ByVal rhs As Fraction) _
      As Boolean
      Return rhs.Number <> lhs.Number
   End Operator

   Public Shared Widening Operator CType(ByVal rhs As Fraction) _
      As Double
      Return rhs.Number
   End Operator

   Public Shared Operator /(ByVal lhs As Fraction, _
                            ByVal rhs As Fraction) _
      As Fraction
      Return New Fraction(rhs.Number / lhs.Number)
   End Operator

   Public Shared Operator *(ByVal lhs As Fraction, _
                            ByVal rhs As Fraction) _
      As Fraction
      Return New Fraction(rhs.Number * lhs.Number)
   End Operator

   Public Shared Narrowing Operator CType(ByVal number As Double) _
      As Fraction
      Return New Fraction(number)
   End Operator

   Public Sub New(ByVal number As String)
      Me.New(Convert.ToDouble(number))
   End Sub

   Private _number As Double
   Public Property Number() As Double
      Get
         Return _number
      End Get
      Set(ByVal Value As Double)
         _number = Value
      End Set
   End Property

   Private _sign As Integer = 1
   Public Property Sign() As Integer
      Get
         Return _sign
      End Get
      Set(ByVal Value As Integer)
         _sign = Value
      End Set
   End Property

   Private _numerator As Integer = 0
   Public Property Numerator() As Integer
      Get
         Return _numerator
      End Get
      Set(ByVal Value As Integer)
         _numerator = Value
      End Set
   End Property

   Private _denominator As Integer = 1
   Public Property Denominator() As Integer
      Get
         Return _denominator
      End Get
      Set(ByVal Value As Integer)
         _denominator = Value
      End Set
   End Property

   Private _fractionalNumber As Double
   Public Property FractionalNumber() As Double
      Get
         Return _fractionalNumber
      End Get
      Set(ByVal Value As Double)
         _fractionalNumber = Value
      End Set
   End Property

   Private _wholeNumber As Integer
   Public Property WholeNumber() As Integer
      Get
         Return _wholeNumber
      End Get
      Set(ByVal Value As Integer)
         _wholeNumber = Value
      End Set
   End Property

   Private Sub SetSign(ByVal value As String)

      If (Regex.IsMatch(value, "^-")) Then
         Sign = -1
      End If

   End Sub


   Private Function CheckNoDecimalPoint(ByVa number As Double) _
      As Integer

      Dim index As Integer = number.ToString().LastIndexOf(".")

      If (index = -1) Then
         WholeNumber = Convert.ToInt32(number)
      End If

      Return index

   End Function

   Private Sub SetWholePart(ByVal value As String, _
                            ByVal index As Integer)

      Dim whole As String = value.Substring(0, index)
      If (whole.Length > 0) Then
         WholeNumber = Convert.ToInt32(whole)
      End If

   End Sub

   Private Sub SetDenominator(ByVal fraction As String)
      Denominator = Math.Pow(10, fraction.Length)
   End Sub

   Private Sub SetFractionalPart(ByRef fraction As String)
      If (fraction.Length > 8) Then
         fraction = fraction.Substring(0, 8)
      End If

      _fractionalNumber = _
         Math.Round(Convert.ToDouble("." + fraction), 8)
   End Sub

   Private Sub SetFractionalPart(ByVal value As String, _
                                 ByVal index As Integer)

      Dim fraction As String = value.Remove(0, index + 1)

      If (fraction.Length > 0) Then
         SetFractionalPart(fraction)
         _numerator = Convert.ToInt32(fraction)
         SetDenominator(fraction)
         ReduceWithGcd()
      End If
   End Sub

   Private Sub ReduceWithGcd()

      Dim divisor As Integer = Gcd(_numerator, _denominator)
      _numerator   = _numerator / divisor
      _denominator = _denominator / divisor

   End Sub

   Private Function Gcd(ByVal num As Integer, _
                        ByVal den As Integer) As Integer

      If (den Mod num = 1) Then Return 1
      While (den Mod num <> 0)
         Dim temp As Integer = num
         num = den Mod num
         den = temp
      End While

      Return num

   End Function

   Public Overrides Function ToString() As String

      If (FractionalNumber = 0 And WholeNumber = 0) Then
         Return ""
      End If

      Dim builder As StringBuilder = New StringBuilder()
      If (Sign = -1) Then builder.Append("-")

      If (Math.Abs(WholeNumber) <> 0) Then

         If (FractionalNumber = 1) Then
            builder.Append(Math.Abs(WholeNumber) + 1)
            Return builder.ToString()
         Else
            builder.Append(Math.Abs(WholeNumber))
            builder.Append(" ")
         End If
      End If

      If (FractionalNumber <> 0) Then
         builder.Append(Numerator.ToString())
         builder.Append("/")
         builder.Append(Denominator.ToString())
      End If

      Return builder.ToString()
   End Function

End Class

If you implement a conversion operator—CType, as I did to support cross type arithmetic—you have to specify whether the conversion is widening or narrowing. In the Fraction class above, you can perform operations on doubles and Fractions, as shown in Listing 2, a simple test console application.

Listing 2: A console application to test the Fraction class.

Module Module1

   Sub Main()
      While (True)
         Console.WriteLine("Enter a decimal number (q=quit)"
         Dim value As String = Console.ReadLine()
         If (value = "q") Then Return

         Dim fraction As Fraction = New Fraction(value)
         Console.WriteLine("{0} is equivalent to {1}", _
            fraction.Number, fraction.ToString())

         Console.WriteLine("Test: {0}={1} is {2}", _
                           fraction, 0.25, fraction = 0.25)
         Console.WriteLine("Test: {0}*{1} is {2}", fraction, 0.5, _
                           fraction * 0.5)
      End While

   End Sub

End Module

Step through the code to see that operations like fraction * 0.5 actually calls the CType conversion operator, the constructor, and the operator* method.

Finally, the StringBuilder class is used to display the properly formatted fraction.

Summary

Calculating fractions is an opportunity to explore some interesting elements of the .NET framework. While you are parsing the sign, storing the whole number, and calculating the fraction, you can use Regular Expressions, Math class methods, the Euclidean algorithm, and experiment with operator overloading.

Enjoy.

About the Author

Paul Kimmel is the VB Today columnist for www.codeguru.com and has written several books on object-oriented programming and .NET. Check out his new book UML DeMystified from McGraw-Hill/Osborne. Paul is a software architect for Tri-State Hospital Supply Corporation. You may contact him for technology questions at pkimmel@softconcepts.com.

If you are interested in joining or sponsoring a .NET Users Group, check out www.glugnet.org. Glugnet is opening a users group branch in Flint, Michigan in August 2007. If you are interested in attending, check out the www.glugnet.org web site for updates.

Copyright © 2007. All Rights Reserved.
By Paul Kimmel. pkimmel@softconcepts.com

Sitemap | Contact Us