Decimal To Fraction Conversion

Date: 06/25/98 at 21:13:06
From: Doug Lawson
Subject: Decimal To Fraction Conversion

Dr. Math,

I am trying to find a method (which can be programmed on a PC) to 
convert the decimal part of a real number to a fraction represented by 
integers for the numerator and denominator. The fractional number has 
particular uses in the textile industry.

I have tried to think of some way to have two equations with two 
unknowns, but I just can't think of how to do this. What we do know 
is a = b/c. We know that 'a' is a decimal number and both 'b' and 'c' 
are integers. I have asked family, friends and coworkers... but no 
one knows how to solve this easily.

As an example, consider the following number:  0.047619
0.047619 = b/c 

Depending on the accuracy you wish to have, this can be represented 
by 0.047619 = 3/63

The problem is: how do you get there with formulas?

Please let me know if you can help.
Sincerely,
Doug Lawson
Leesona Div., Kvaerner U.S. Inc.

Date: 06/26/98 at 09:22:47
From: Doctor Jerry
Subject: Re: Decimal To Fraction Conversion

Hi Doug,

Any terminating decimal (1/3=0.33333... is not terminating) can be 
written as a fraction.  For example,

0.047619 
          = 0/10 + 4/100 + 7/1000 + 6/10000 + 1/100000 + 9/1000000 
          = 47619/1000000.

In some cases, the numerator and denominator will have common factors 
that can be removed. In the case you gave, there are no common 
factors.

I suspect you may be wanting a good approximation to a number like 
0.047619 in terms of fractions like x/16 or y/32. If this is the case, 
you could write a short program which runs through the numbers j/32, 
j=0,1,...,31, picking out the one closest to 0.047619.

- Doctor Jerry, The Math Forum
  http://mathforum.org/dr.math/   

Date: 06/26/98 at 13:28:05
From: Doctor Peterson
Subject: Re: Decimal To Fraction Conversion

Hi, Doug -

I saw Dr. Jerry's answer, and want to suggest another way that may be 
what you want. His idea is probably the best if what you want is, say, 
to convert lengths into standard fractions such as 32nds. But there is 
a standard way to approximate any decimal (even an irrational number 
like pi!) by a fraction as closely as you want. A nice feature of this 
method is that if your number is the exact value of a fraction, you 
will know when you have reached it. (Though it generally won't work 
exactly because you will be missing some decimal places.) What you do 
is to repeatedly take the reciprocal and remove the integer part, 
building what is called a "continued fraction" that is equal to your 
number. I'll demonstrate with your case first:

What I wrote down:           What I did on my calculator:

               1
0.047619 = ---------         Enter 0.047619 and hit the 1/x key
           21.000021

               1
         = ----------
                  1          Write down the 21 and subtract it
           21 + -----          to get 0.000021
                47619        Hit 1/x again

            1
         = --                Since 1/47619 is so small, ignore it
           21

Let's do a slightly more difficult example, 0.127659:

               1
0.127659 = ---------         Enter 0.127659 and hit 1/x
           7.8333686

                 1
         = ------------
                  1          Write down the 7 and subtract it
           7 + --------        to get 0.8333686
               1.199949      Hit 1/x again

                  1
         = ---------------
                    1
           7 + -----------
                      1      Write down the 1 and subtract it
               1 + -------     to get 0.199949
                   5.00126   Hit 1/x again

                  1
         = ---------------
                     1
           7 + -----------
                      1
               1 + -------
                        1    Write down the 5 and subtract it to get
                   5 + ---     0.00126
                       787

               1
         = ---------
                 1
           7 + -----
                   1
               1 + -
                   5         Since 1/787 is so small, call it zero and 
stop

This is the answer. All I have to do is simplify:

              1
         = -------
                1
           7 + ---
                6
                -
                5

             1
         = -----
               5
           7 + -
               6

             1
         = -----
            47
            ---
             6

            6
         = --
           47

This is the fraction I used to get the decimal. This method of 
continued fractions, incidentally, is also used to solve Diophantine 
(integer) equations, so your first inclination might have taken to 
this method if you had searched far enough.

In some cases you will have to arbitrarily decide when to stop, 
because there won't be a natural stopping point. For example, try the 
method on 0.7071068 (1/sqrt(2)).

The only part about this method that may be hard to program would be 
the simplification of the fraction. If you actually want to do it, I 
have a different version of this method that is a little harder to 
explain, and takes more steps on a calculator, but would be easier to 
program.

This may be more than you need, but it's so much fun I wanted you to 
see it.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/   

Date: 06/28/98 at 21:12:22
From: Douglas Keith Lawson
Subject: Reply to Dr. Peterson Re: Decimal To Fraction Conversion

Thank you Dr. Peterson,

I will try your method at work and see how I can best implement it.  
I believe that your closing remarks in your reply to me were correct.  
The difficult part of the program would be simplification of the 
fraction. As such, I would be interested in seeing your alternate 
method.

To bore you with details about my interest in fractional math, let me
explain succinctly what I am doing. In the textile industry a type of
machine called a 'take-up' or 'winder' is used to wind fibers into 
free-standing cylindrical packages (like spools but without end 
plates). This is achieved using a thread guide that cycles parallel to 
the rotating axis of the cylinder being formed. The ratio of package 
revolutions to the axial traversing of the thread guide is defined as 
the wind ratio. Its significance in winding a good package can not be 
overstressed. In fact, this wind ratio is typically calculated and 
maintained with fixed gearing out to six (6) decimal places. 

The numerator and denominator of the fraction defining the wind ratio 
indicate a lot about how the fiber will be wound on the package. 
At first glance one would assume that this would not be critical; 
however, errors in the sixth decimal place can be seen with the naked 
eye and they can be detrimental to package stability.  

My firm has worked with the geared arangement for years and has easily 
been able to calculate the wind ratio as a function of gear ratios.  
As such, the numerator of the wind ratio is the product of several 
gear teeth multiplied by each other. The denominator is another gear 
tooth product. This method of calculation directly from given gear 
tooth numbers allowed us to keep the wind ratio as a fraction and 
easily utilize it that way. We are developing a digital control system 
to replace the gearing. We will enter the wind ratio directly on the 
computer controls of the winding machine as a number to six decimal 
places. This gives us greater flexibility than the gear arrangement; 
however, we now need a method to calculate wind parameters. What I 
need to do is take a given ratio and be able to return it to 
fractional form.

Your suggestions and your methods of approximating fractions are 
greatly appreciated.  I would be interested in seeing your alternate 
method of calculation and look forward to your reply.  Thank you again 
for your assistance.

Sincerely,
Doug Lawson
Leesona Div., Kvaerner U.S. Inc.

Date: 06/29/98 at 13:12:44
From: Doctor Peterson
Subject: Re: Decimal To Fraction Conversion

Hi, Doug. Now that I know how you plan to use the fraction, it's clear 
that my approach is what you need. 

The algorithm I am about to show you has an interesting history. I 
recently had a discussion with a teacher in England who had a 
challenging problem he had given his students, and wanted to know what 
others would do to solve it. The problem was to find the fraction 
whose decimal value he gave them, which is essentially identical to 
your problem! I wasn't familiar with a standard way to do it, but 
solved it by a vaguely remembered Diophantine method. Then, my 
curiosity piqued, and I searched the Web for information on the 
problem and didn't find it mentioned in terms of finding the fraction 
for an actual decimal, but as a way to approximate an irrational by a 
fraction, where the continued fraction method was used. 

I wrote to the teacher, and he responded with a method a student of 
his had come up with, which uses what amounts to a binary search 
technique. I recognized that this produced the same sequence of 
approximations that continued fractions gave, and was able to 
determine that it is really equivalent, and that it is known to some 
mathematicians (or at least math historians). 

After your request made me realize that this other method would be 
easier to program, I thought of an addition to make it more efficient, 
which to my knowledge is entirely new. So we're either on the cutting 
edge of computer technology or reinventing the wheel, I'm not sure 
which!

Here's the method, with a partial explanation for how it works:

We want to approximate a value m (given as a decimal) between 0 and 1, 
by a fraction Y/X. Think of fractions as vectors (denominator, 
numerator), so that the slope of the vector is the value of the 
fraction. We are then looking for a lattice vector (X, Y) whose slope 
is as close as possible to m. This picture illustrates the goal, and 
shows that, given two vectors A and B on opposite sides of the desired 
slope, their sum A + B = C is a new vector whose slope is between the 
two, allowing us to narrow our search:

num
^
|
+  +  +  +  +  +  +  +  +  +  +
|
+  +  +  +  +  +  +  +  +  +  +
|                                  slope m=0.7
+  +  +  +  +  +  +  +  +  +  +   /
|                               /
+  +  +  +  +  +  +  +  +  +  D <--- solution
|                           /
+  +  +  +  +  +  +  +  + /+  +
|                       /
+  +  +  +  +  +  +  C/ +  +  +
|                   /
+  +  +  +  +  + /+  +  +  +  +
|              /
+  +  +  +  B/ +  +  +  +  +  +
|          /
+  +  + /A  +  +  +  +  +  +  +
|     /
+  +/ +  +  +  +  +  +  +  +  +
| /
+--+--+--+--+--+--+--+--+--+--+--> denom

Here we start knowing the goal is between A = (3,2) and B = (4,3), and 
formed a new vector C = A + B. We test the slope of C and find that 
the desired slope m is between A and C, so we continue the search 
between A and C. We add A and C to get a new vector D = A + 2*B, which 
in this case is exactly right and gives us the answer.

Given the vectors A and B, with slope(A) < m < slope(B), 
we can find consecutive integers M and N such that 
slope(A + M*B) < x < slope(A + N*B) in this way:

If A = (b, a) and B = (d, c), with a/b < m < c/d, solve

    a + x*c
    ------- = m
    b + x*d

to give

        b*m - a
    x = -------
        c - d*m

If this is an integer (or close enough to an integer to consider it 
so), then A + x*B is our answer. Otherwise, we round it down and up to 
get integer multipliers M and N respectively, from which new lower and 
upper bounds A' = A + M*B and B' = A + N*B can be obtained. Repeat the 
process until the slopes of the two vectors are close enough for the 
desired accuracy. The process can be started with vectors (0,1), with 
slope 0, and (1,1), with slope 1. Surprisingly, this process produces 
exactly what continued fractions produce, and therefore it will 
terminate at the desired fraction (in lowest terms, as far as I can 
tell) if there is one, or when it is correct within the accuracy of 
the original data.

For example, for the slope 0.7 shown in the picture above, we get 
these approximations:

Step 1: A = 0/1, B = 1/1 (a = 0, b = 1, c = 1, d = 1)

        1 * 0.7 - 0   0.7
    x = ----------- = --- = 2.3333
        1 - 1 * 0.7   0.3

    M = 2: lower bound A' = (0 + 2*1) / (1 + 2*1) = 2 / 3
    N = 3: upper bound B' = (0 + 3*1) / (1 + 3*1) = 3 / 4

Step 2: A = 2/3, B = 3/4 (a = 2, b = 3, c = 3, d = 4)

        3 * 0.7 - 2   0.1
    x = ----------- = --- = 0.5
        3 - 4 * 0.7   0.2

    M = 0: lower bound A' = (2 + 0*3) / (3 + 0*4) = 2 / 3
    N = 1: upper bound B' = (2 + 1*3) / (3 + 1*4) = 5 / 7

Step 3: A = 2/3, B = 5/7 (a = 2, b = 3, c = 5, d = 7)

        3 * 0.7 - 2   0.1
    x = ----------- = --- = 1
        5 - 7 * 0.7   0.1

    N = 1: exact value A' = B' = (2 + 1*5) / (3 + 1*7) = 7 / 10

which of course is obviously right.

In most cases you will never get an exact integer, because of rounding 
errors, but can stop when one of the two fractions is equal to the 
goal to the given accuracy.

I have been playing with these ideas on my own, but have not yet 
gotten around to coding it to work out any bugs in the algorithm. I'll 
do that sometime soon, but you should be able to work it out from what 
I've given you. The only thing I'm really not sure of is the best way 
to decide when to stop. 

I hope this helps you. I have no special use for the algorithm right 
now (though I am a software engineer for a process control company!), 
but it's been fun playing with it.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/   

Date: 07/01/98 at 21:22:55
From: Douglas Keith Lawson
Subject: Reply To Dr.Peterson Re: Decimal To Fraction Conversion

Hello again Dr. Peterson:

I have printed out your 'alternate' method regarding converting a 
decimal back to its fractional equivalent.  I will study it at length 
shortly.

Since I last wrote you I took your first explanation concerning the 
method of continuing fractions and studied it. On my PC at work I 
utilize MathCad 7.0 from MathSoft to solve several engineering 
problems. I decided to give it a try as a method of programming the 
continuing fractions method.

I did have to adjust my thinking to make the method conform to 
'textile math'; however, I was able to write a crude program which 
could determine the fractional equivalent to the decimal number 
accurately out to 9 decimal places. In the textile equivalent of the 
continuing fractions method it appears to be necessary to examine the 
numbers in question with regard to 'rounding'.  In short, if the 
number in question is 12.75, it is necessary to regard the fractional 
number as 13-1/4, not 12+3/4. This is necessary as the integer portion 
of the real number (i.e. 13 from the example above) describes the 
pattern formed by the fibers as they are wound on a cylinder. The 
subsequent integer numbers extracted from the continuing fractions
describe sub-patterns. These numbers are referred to as knuckle 
patterns and they influence how the wound fibers will lock together 
between wound layers.

I still have a lot of work to do, but I would be nowhere without your 
help. I might end up just refining what I wrote based on the 
continuing fractions method. I suppose your comments were correct, I 
am reinventing the wheel, at least to a degree. As I mentioned in my 
last e-mail, the traditional method of determining the parameters I am 
studying begins by multiplying the number of gear teeth into products 
defining the numerator and denominator of a fraction. The electronic 
controls we are developing may appear to give the same number to six 
decimal places, but what the continuing fractions method has made me 
aware of is the fact that errors out as far as 9 decimal places can 
significantly influence the physical results. I would not have 
believed it.

Again, I thank you for your help and I apologize for taking so much of 
your time.  I know that the primary avenue for this forum is 
supporting students. Again, I would not be anywhere with this if it 
were not for your help.

Sincerely,
Doug Lawson
Leesona Div., Kvaerner U.S. Inc.

Date: 07/04/98 at 12:20:48
From: Doctor Peterson
Subject: Re: Decimal To Fraction Conversion

Hi, Doug. Glad I can help - and it's especially nice to know you're 
not just using the methods but also the ideas I came up with! I've 
been having a lot of fun with this (since before your question), and 
I'm learning myself.

Just to keep you up to date, I tried out my newly invented algorithm 
and realized it lacked one or two things. Specifically, to make it 
work right, you have to alternate directions, first adding A + N*B and 
then N*A + B. I tested my program for all fractions with up to three 
digits in numerator and denominator, then started playing with the 
problem that affects you, namely how to handle imprecision in the 
input. I haven't yet worked out the best way to allow for error, but 
here is my C++ function (a member function in a Fraction class 
implemented as { short num; short denom; } ) in case you need to go to 
this algorithm:

Fraction Fraction::toFract(double val)
{    // find nearest fraction
 int intPart = (int)val;
 val -= (double)intPart;
 Fraction low(0, 1);           // "A" = 0/1
 Fraction high(1, 1);          // "B" = 1/1
 for (int i = 0; i < 100; ++i)
 {
  double testLow = low.denom * val - low.num;
  double testHigh = high.num - high.denom * val;
  if (testHigh < Precision * high.denom)
   break; // high is answer
  if (testLow < Precision * low.denom)
  {  // low is answer
   high = low;
   break;
  }
  if (i & 1)
  {  // odd step: add multiple of low to high
   double test = testHigh / testLow;
   int count = (int)test;    // "N"
   int num = (count + 1) * low.num + high.num;
   int denom = (count + 1) * low.denom + high.denom;
   if ((num > 0x8000) ||
       (denom > 0x10000))
    break;
   high.num = num - low.num;  // new "A"
   high.denom = denom - low.denom;
   low.num = num;             // new "B"
   low.denom = denom;
  }
  else
  {  // even step: add multiple of high to low
   double test = testLow / testHigh;
   int count = (int)test;     // "N"
   int num = low.num + (count + 1) * high.num;
   int denom = low.denom + (count + 1) * high.denom;
   if ((num > 0x10000) ||
       (denom > 0x10000))
    break;
   low.num = num - high.num;  // new "A"
   low.denom = denom - high.denom;
   high.num = num;            // new "B"
   high.denom = denom;
  }
 }
 return Fraction(intPart, 1) + high;
}

I'm curious about one more thing: Would it be possible in your system 
to have the user enter a fraction rather than a decimal, to avoid the 
loss of precision? I recently answered a student's query as to whether 
decimals or fractions are "more precise," and my answer was that if 
the value you want is an exact fraction, you should represent it as a 
fraction, and if it's just a measurement with some level of precision, 
you should use a decimal. This could be a good application of that 
idea.

Thanks for keeping me informed. Just knowing this stuff is useful 
encourages me in helping students!

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/   

Date: 07/06/98 at 21:59:49
From: Douglas Keith Lawson
Subject: Reply to Dr. Peterson Re: Decimal To Fraction Conversion

Hello again Dr. Peterson,

Thank you for your last reply to my fraction question.  After I 
reviewed your 'slope' method of determining the fractional equivalent 
to a decimal number I have decided that your first suggestion of 
continuing fractions is best for my application. Both have merit; 
however, as I mentioned in my last correspondence, the integer numbers 
extracted from the continuing fractions method have meaning in the 
problem I am studying.

If I chose to examine the number by the slope method I might not 
obtain the same fraction and therefore might not extract the same 
integers that I can extract with the continuing fractions method.  
Your comments are well understood though, as far as determining 'how 
close' is close enough and knowing when to stop. 

I must apologize that your c++ code will not be of much use to me.  My
programming experience includes only FORTRAN and Pascal. In fact, I 
was writing a Pascal program to handle the continuing fractions. My 
Pascal problems are complicated by the fact that I only have a copy of 
Turbo Pascal 5.0 from Borland. Unfortunately, this was written for DOS 
and Win95 does not like the fact that Turbo makes direct system calls.  
As such I have to reboot in DOS mode to write my code. I was so 
frustrated that I downloaded an older, simpler Pascal compiler to 
write my code in a DOS window. I can't read or write to files with 
this version of Pascal, but once I get the program right I will create 
an executable file (EXE) using Turbo Pascal.

Once I realized what information I could extract using continuing 
fractions I knew this was the way to go.  The problem is as you 
suggested... writing the code to do this.

Thanks again for your help.

Sincerely,
Doug Lawson
Leesona Div., Kvaerner U.S. Inc.

Date: 03/22/15 at 12:46:45
From: Bart Broersma
Subject: Reply to Dr. Peterson Re: Decimal To Fraction Conversion

Hi,

I am one of the devolopers for the Lazarus IDE, and I've ported the C++
code on this page to Pascal.

I have adapted the code to handle 64-bit integers, negative numbers,
negative precisions, and bordeline values (values less than 0.5/MaxInt64
will return 0).

The code raises an exception if the input value is out of range for 64-bit
integer.

I have bound the precision parameter to the value parameter, in such a way
that value/precision will never be greater than 1E15, since greater
precision does not make much sense when using doubles.

The smallest possible precision can ever be 1/MaxInt64.

I have adjusted the test to see if a retrun candidate was inside the
specified precision (which may have to do more with the way I interpret
precision). With the original test, there were returnvalues that were
larger than the precision off (most of the time, just 1 significant digit
more).

I have thrown over 600 million random doubles (range: 0.0 - 1.0) to the
function and tested the results. They were all inside the (adjusted)
precision, and there were no mathematical overflows or rangecheck errors.

This of course does not prove that the function will never return a value
that does not match the precision, nor that it will never crash. For the
moment, however, I am satisfied that it works well.

I have applied the same testing to some other algorithms and they did
return fractions that did not match the precision, or suffered from
arithmetic overflow (which required extra checks inside that code).

I have now included the adapted code in my fractions unit, and I have put
in a comment:

{
  This implementation of FloatToFraction was originally written by:
  David Peterson and The Math Forum @ Drexel
  Source: http://mathforum.org/library/drmath/view/51886.html
  It was ported to FreePascal by Bart Broersma
  Adjustments made:
    * Precision is bound by a magnitude of -15 to Value
    * Bordeline cases close to zero are handled
    * Handle negative values
    * Handle negative precision
    * Original code dealt with 32-bit integers, it was adjusted for
64-bit integers

  The original copyright holder has granted me permission to adjust and
redistribute
  this code under LGPL license.

  When redistributing this code, the comments above MUST also be
redistributed with it!
}

(Note: "{" and "}" in pascal start and end comments)

===============================
procedure AdjustPrecision(var Precision: Double; Value: Double);
const
  MaxPrec = Double(1.0)/MaxInt64;
begin
  Precision := Abs(Precision);
  if ((Abs(Value) / Precision) > 1E15) then
  begin
    //writeln('Value / Precision > 1E15');
    Precision := Abs(Value) / 1E16;
  end;
  if (Precision < MaxPrec) then
    Precision := MaxPrec;
end;

procedure CheckRange(Value: Double);
begin
  if (Value > MaxInt64) or (Value < MinInt64) then
    raise ERangeError.Create(SRangeCheckError);
end;

function IsBorderlineValue(Value: Double; out F: TFraction): Boolean;
const
  MaxPrec = Double(1.0)/MaxInt64;
  ZeroBoundary = MaxPrec / 2;
begin
  if (Abs(Value) <= MaxPrec) then
  begin
    Result := True;
    //writeln('Abs(Value) < 1/MaxInt64 [',MaxPrec,']');
    if (Abs(Value) < ZeroBoundary) then
    begin
      //writeln('Abs(Value) < ZeroBoundary [',ZeroBoundary,']');
      F.Numerator := 0;
      F.Denominator := 1;
    end
    else
    begin
      if (Value < 0) then
      F.Numerator := -1
        else
      F.Numerator := 1;
      F.Denominator := MaxInt64;
    end;
  end
  else
    Result := False;
end;

function MF_FloatToFraction(Value, Precision: Double): TFraction;
var
  IntPart, Count, Num, Denom: Int64;
  i: Integer;
  TestLow, TestHigh, Test: Double;
  L,H: TFraction;
  IsNeg: Boolean;
begin // find nearest fraction
  CheckRange(Value);
  AdjustPrecision(Precision, Value);
  //Borderline cases
  if IsBorderlineValue(Value, Result) then
    Exit;
  IsNeg := (Value < 0);
  Value := Abs(Value);
  intPart := Round(Int(Value));
  Value := Frac(Value);
  L.Numerator := 0;
  L.Denominator := 1;
  H.Numerator := 1;
  H.denominator := 1;
  for i := 1 to 100 do
  begin
    testLow := L.Denominator * Value - L.Numerator;
    testHigh := H.Numerator - H.Denominator * Value;
    if (Abs(H.ToFloat - Value) < Precision) then
    begin
      break; // high is answer
    end;
    if (Abs(L.ToFloat - Value) < Precision) then
    begin // low is answer
      H := L;
      break;
    end;
    if Odd(i) then
    begin // odd step: add multiple of low to high
      test := testHigh / testLow;
      count := Round(Int(test)); // "N"
      num := (count + 1) * L.Numerator + H.Numerator;
      denom := (count + 1) * L.Denominator + H.Denominator;
      if ((num > High(Int64) - 1) or
      (denom > High(Int64) - 1)) then
      begin
        break;
      end;
      H.Numerator := num - L.Numerator; // new "A"
      H.Denominator := denom - L.Denominator;
      L.Numerator := num; // new "B"
      L.Denominator := denom;
    end
    else
    begin // even step: add multiple of high to low
      test := testLow / testHigh;
      count := Round(Int(test)); // "N"
      num := L.Numerator + (count + 1) * H.Numerator;
      denom := L.Denominator + (count + 1) * H.Denominator;
      if ((num > High(Int64) - 1) or
      (denom > High(Int64) - 1)) then
      begin
        //writeln('  ((num > High(Int64) - 1) or 
                    (denom > High(Int64) - 1))');
        break;
      end;
      L.Numerator := num - H.Numerator; // new "A"
      L.Denominator := denom - H.Denominator;
      H.Numerator := num; // new "B"
      H.Denominator := denom;
    end;
  end;
  //Avoid call to TFraction.Normalize in Result := H + IntPart
  Result := H;
  Result.Numerator := Result.Numerator+ (Result.Numerator * IntPart);
  if IsNeg then
    Result.Numerator := -Result.Numerator;
end;