Decimal To Fraction ConversionDate: 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; |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/