Computer Science 101

with:  Erik Oosterwal

Search for specific programs or algorithms:
Custom Search




Floating Point Decimal to Integer Fraction


Here is a simple algorithm for converting a decimal fraction value to a whole number integer fraction or, in other words, this algorithm attempts to determine if a given number is rational.  Any decimal value will be converted to a whole number fraction within the desired accuracy.

The idea behind this algorithm is that a decimal fraction represents a slope of a line.  Algebraically speaking, the slope of a line is defined as the rise divided by the run or (Y2-Y1) / (X2-X1), all we have to do is find two integers that approximate the slope to the desired accuracy.  For positive values, we do this by setting the numerator to 0 and the denominator to 1, then comparing that fraction to the given decimal value.  If our fraction is too small (ie. our point lies below the line), then we increase the value of the numerator until it falls on or above the line.  If our fraction is too big (ie. our point lies above the line), then we increase the denominator until it falls on or below the line.

If we're given some irrational number, then the algorithm loops, increasing the numerator and denominator values until the the resulting fraction falls within the desired accuracy of the given number.

Sample code is provided in Visual Basic:



'
'   Routine to convert decimal values to integer fractions.
'
'   Written by:     Erik Oosterwal
'   Started on:     November 9, 2005
'   Completed on:   November 9, 2005
'

    Dim intNumerator, intDenominator, intNegative As Long   ' Declare integer variables as long
                                                            '   integers.
    Dim dblFraction, dblDecimal, dblAccuracy As Double      ' Declare floating point variables
                                                            '   as double precision.
    
    dblDecimal = Val(txtDecimal)                    ' Get the desired decimal value from the
                                                    '   front panel (VB Form).
    dblAccuracy = Val(txtAccuracy)                  ' Get the desired accuracy from the front
                                                    '   panel (VB Form).  Need to put a check
                                                    '   in here to make sure the desired
                                                    '   accuracy is not smaller than what the
                                                    '   programming language can handle.  For
                                                    '   VB, this should be 1E-13.
    
    intNumerator = 0                                ' Set the initial numerator value to 0.
    intDenominator = 1                              ' Set the initial denominator value to 1.
    intNegative = 1                                 ' Set the negative value flag to positive.
    
    If dblDecimal < 0 Then intNegative = -1         ' If the desired decimal value is negative,
                                                    '   then set the negative value flag to
                                                    '   negative.
    
    dblFraction = 0                                 ' Set the fraction value to be 0/1.
        
    While Abs(dblFraction - dblDecimal) > dblAccuracy   ' As long as we're still outside the
                                                        '   desired accuracy, then...
        If Abs(dblFraction) > Abs(dblDecimal) Then      ' If our fraction is too big,
            intDenominator = intDenominator + 1         '   increase the denominator
        Else                                            ' Otherwise
            intNumerator = intNumerator + intNegative   '   increase the numerator.
        End If
        
        dblFraction = intNumerator / intDenominator     ' Set the new value of the fraction.
        
    Wend
    
    txtNumerator.Text = Str(intNumerator)           ' Display the numerator and denominator
    txtDenominator.Text = Str(intDenominator)       '   values on the front panel (VB Form).


You can also download a zip file that contains an executable file that demonstrates this routine along with the Visual Basic project.




Discuss computer algorithms and other computer science topics at the Computer Algorithms blog page.

All code and original algorithms are © Erik Oosterwal - 1987-2008
Computer Science 101

Dressing for Success