Problem Description
Given a positive decimal number, convert it
to an irreducible mixed or proper fraction. If the denominator
of the fraction is larger than a specified maximum denominator, present
the solution in the above format as a fraction which is the best
estimate of the input value and display the error value.
Version 3 - convert both ways (decimal to
fraction, and fraction to decimal) and add optional constraint to display
decimal input in mixed fraction form with denominators restricted to
16, 32, or 64. Jump to download
link
Background & Techniques
First, some terminology: A fraction, N/D, is proper if the numerator,
N, is less than the denominator, D. (I remember which is
which by associating the D in denominator with the number
that is down in the fraction. A mixed fraction is one whose value is
greater than 1 and is expressed as an integer plus a proper fraction (X +
N/D). If the GCD, Greatest Common Divisor of N and D equals 1 then
the fraction is in lowest terms, irreducible.
This program probably has little use unless you are a programmer curious about how to convert a decimal number to a
fraction or someone who needs help with a homework assignment .
We start by separating the integer part from the decimal part of the input number. Multiply the
decimal part by a power of 10 large enough to convert it to an integer, i.e. 10 raised to the power of the number of digits in the fractional part.
(For example, given 0.124, multiply by 103 = 124).
So we now have our initial try at a fractional form answer (124/1000). We'll reduce it to lowest terms by dividing numerator and denominator by the greatest common denominator of the two.
In our example, GCD(124,1000)=4 so the fraction reduces to 31/250. If the denominator is less than or equal to the
specified max denominator size, we're done.
Otherwise, we'll have to provide the closest possible estimate whose denominator is smaller than the maximum specified. We'll just try all denominators from 2 to the max specified and calculate the numerator which produce a value closest to the original decimal part. Numerator = ((original decimal part) x trial denominator) rounded to the nearest integer.
The error of this estimate is original decimal part - numerator / trial denominator. We'll save the numerator and trial denominator which produces
the smallest absolute error and report that as the solution.
Assuming the maximum denominator for our example is 100, the closest
fractional representation of 0.124 is 12/97 which in
decimal form is 0.12371..., less than .0003 from the input value.
Addendum May 28, 2005: It didn't take long for regular contributor
Don Rowlett to point out that I once had ignored the European by
defined some constants with '.' for a decimal separator rather than a
','. I think that is now corrected. Don also added a trick for
converting repeated decimals if one of the repeated cycles is given so we
implemented the option for the user to specify whether the input decimal
terminates or repeats forever. This also required adding big integer
arithmetic because even a single cycle of some repeated decimals are too
long to be represented in normal integer arithmetic (for example 1/29 has
the 28 digit repeating decimal representation
.0344827586206896551724137931 0344827 etc......... ) Compiling
Version 2 of this
program will require the Big Integer unit contained in our DFF Library
file.
Addendum February 7, 2006: I
recently decided to upgrade another [program (Cutlist)
to add a "carpenter arithmetic" option for input and output
displays. Woodworkers, at least us Yanks or
Brits, who use the English measurement system are stuck with
measuring lengths in feet and inches (12ths of a foot). Parts
of an inch for wood workers are not measured in 10ths and hundredths - not
challenging enough for us - we measure parts of an inch in 64ths and
multiples of 64ths (32nds, 16ths, 8ths, 4ths and
halves). I developed the procedures to do the necessary
conversions in both directions and added them to version 3 of this
program. I also removed the Big Integer capability because it
was an unnecessary complication when measuring in 64ths. I'll leave
the previous version on the download zipped source
file for anyone interested in exploring rational numbers with cycle
lengths greater than 18 digits. I removed the GCD
function that had been embedded in favor of the common library version in
our Mathslib unit. As a result, DFFLIBV04 or later version of the
library file is required to recompile version 3.
Running/Exploring the Program