Program to convert from decimal to fraction

This is a discussion on Program to convert from decimal to fraction within the C Programming forums, part of the General Programming Boards category; Please does anybody know an algorithm which can be used to convert a decimal to a fraction especially irrational fractions ...

  1. #1
    Registered User
    Join Date
    Feb 2013
    Location
    Buea Cameroon
    Posts
    64

    Program to convert from decimal to fraction

    Please does anybody know an algorithm which can be used to convert a decimal to a fraction especially irrational fractions thanks. That is a programm that can convert to 0.333333333333333333333 to 1/3 like any scientific calculator does.

  2. #2
    Registered User
    Join Date
    Apr 2013
    Posts
    1,283
    You need to find the length of the repeating pattern and set n = length of repeating pattern. Then multiply the number by 10^n, then subtract that number from 10^n times the number. The result will be (10^n - 1) times the number, and an integer. Then that integer divided by (10^n - 1) is the fraction. After this, use Euclid algorithm to find greatest common divisor to reduce the fraction.

    For example 1/7 = 0.142857142857142857142857142857..., that's a 6 digit pattern. You need to multiply this number by 10^6 to get 142857. .... Then subtract the original number resulting in (10^6 - 1) x number = 142857. The fraction is 142857 / 999999 and in this case the greatest common divisor is 142857, so the result is 1/7.

  3. #3
    Registered User
    Join Date
    Oct 2011
    Posts
    847
    Check out continued fractions and Euclidean algorithm at Wikipedia.

  4. #4
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by acho.arnold View Post
    especially irrational fractions
    An irrational ("not a ratio") number is one that cannot be written as a fraction, so there are no irrational fractions.
    To figure out an algorithm, figure out how you would do it yourself.

  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    1,283
    You'll also need to check for fractions that are exact decimal values, such as .1520000000. For these, you'll need to multiply by 10, then subtract the integer part to see if the fractional part is zero (or nearly zero, you'll need some tolerance here), and if not repeat process. In this case after 3 multiplies by 10, you get the integer 152, so the fraction is 152/1000, with a greatest common divisor of 8 resulting in 19/125.

  6. #6
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by rcgldr View Post
    You'll also need to check for fractions that are exact decimal values, such as .1520000000. For these, you'll need to multiply by 10, then subtract the integer part to see if the fractional part is zero (or nearly zero, you'll need some tolerance here), and if not repeat process. In this case after 3 multiplies by 10, you get the integer 152, so the fraction is 152/1000, with a greatest common divisor of 8 resulting in 19/125.
    That technique still needs to be applied in a case like 2/15:
    0.1333333333333333333
    So you could consider the first 0 in .1520000000 as being the repeating part.

    You may end up needing some big number math here if the fractional part of an irrational is given (no repeating part).

    Also, in general it's not possible to recover the fraction that was used to generate the float since the float's limited precision essentially represents the actual rationals in lumps, like the pixels on a screen represent space in lumps.

    I was thinking of another scheme, dividing the number (assumed to be < 1) into 1.
    If the result has no fractional part, the fraction is 1 over the result.
    Otherwise,
    * continue taking multiples of result until it has no fractional part;
    * the final result is the denominator and the number of the multiple is the numerator.

  7. #7
    Registered User
    Join Date
    Oct 2011
    Posts
    847
    I just wrote a roughly 120-line test program based on continued fractions, and Euclidean algorithm for removing common factors from the numerator and denominator.

    The only "extra" parameters it needs is the maximum number of factors, and the largest integer factor in the continued fraction. These determine the precision of the result.

    The idea is as follows.

    Split a positive value to integral and fractional parts (using e.g. modf()). This yields you
    value = integral + fractional
    Since the fractional part is always between zero and one (exclusive), you can approximate it with a reciprocal of an integer:
    value ≃ integral + 1/reciprocal
    Note that if the fractional part is zero, you have an exact representation. If the reciprocal is just an approximation, you can make it more precise by repeating the process:
    value ≃ a0 + 1/(a1 + 1/(a2 + ... 1/aN))
    Since the right-side values are all integers, you can combine them to the desired fractional representation:
    a0 + 1/a1 = (a0*a1+1)/a1
    a0 + 1/(a1 + 1/a2) = a0 + a2/(a1*a2+1) = (a0*(a1*a2+1)+a2) / (a1*a2+1)
    :
    and so on.

    The numerator and denominator often have common divisors, so you need to use the Euclidean algorithm to find the largest common divisor between the two, and divide both by it, to get the normal fractional form.

    Here is a worked-out example:
    Code:
    1.24 = 1 + 0.24
    1.24 = 1 + 1/(4 + 0.1666..)
    1.24 = 1 + 1/(4 + 1/6)
    
    Exact using three factors, 1, 4, 6, in a continued fraction.
    
    1.24 = 1 + 1/(4 + 1/6)
    1.24 = 1 + 1/(25/6)
    1.24 = 1 + 6/25
    1.24 = (25 + 6)/25
    1.24 = 31 / 25
    In practice, you'll have one loop that first deconstructs the value into the continued fraction form, using two or more integer factors as above. (If you only have one, then the solution is trivial and exact.)

    A second loop starts with the last two factors, assigns them as current numerator and denominator, and walks back the array of factors. (Just like you would on paper: start at the lower right column, step by step.) At each step, you need to use the Euclidean algorithm to remove common divisors from the numerator and denominator. I used the iterative version of the Stein algorithm.

    Finally, you'll want to add the original integral part of the value to the numerator and denominator, and adjust sign if necessary.

    Here are some test numbers and their results my program gets with maximum 8 coefficients (including the integral part of the original value), limiting the coefficients to less than 1000:
    Code:
    2.4 = 12 / 5
    2.91 = 291 / 100
    3.33 = 333 / 100
    8.458 = 4229 / 500
    3.333 = 3333 / 1000
    1.5221 = 7335 / 4819
    3.3333 = 10 / 3
    5.85537 = 1417 / 242
    1.934754 = 45577 / 23557
    8.1062270 = 279754 / 34511
    1.73530690 = 3986 / 2297
    4.849832125 = 5781 / 1192
    1.5186262650 = 2609 / 1718

  8. #8
    Registered User
    Join Date
    Oct 2011
    Posts
    847
    Quote Originally Posted by oogabooga View Post
    I was thinking of another scheme, dividing the number (assumed to be < 1) into 1.
    Also called an continued fraction, which I referred to post #3, and everyone completely ignored. Harrumph.

  9. #9
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by Nominal Animal View Post
    Also called an continued fraction, which I referred to post #3, and everyone completely ignored. Harrumph.
    I ended up reading the wikipedia link you gave, but not until after I posted. I realized that it was the same idea!

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    1,283
    Quote Originally Posted by Nominal Animal View Post
    I just wrote a roughly 120-line test program based on continued fractions, and Euclidean algorithm for removing common factors from the numerator and denominator.
    That's about the size I thought that continued fraction method would be. I was thinking the repeated decimal string method might take less code, but once all the variations are handled, it probably ends up taking even more code.

  11. #11
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by rcgldr View Post
    That's about the size I thought that continued fraction method would be. I was thinking the repeated decimal string method might take less code, but once all the variations are handled, it probably ends up taking even more code.
    My impl is just a few lines. I haven't tested it extensively, though.
    EDIT:
    Also, it doesn't need the gcd. It seems to be related to continued fractions, but is not really the same thing. I think it works, but it may not be too efficient.
    Last edited by oogabooga; 07-12-2013 at 12:25 AM.

  12. #12
    Registered User
    Join Date
    Oct 2011
    Posts
    847
    Quote Originally Posted by oogabooga View Post
    My impl is just a few lines.
    My verbose continued fraction function is 41 lines of code (not including comments or empty lines); the function dividing both numerator and denominator with their greatest common divisor is an additional 28 lines (not including comments or empty lines). The rest is command-line parameter parsing etc.

    I didn't bother to work out how to easily manage the overall precision, as my mind is not at its sharpest right now, but it shouldn't be too difficult. Double-precision random numbers seem to require up to 24 or so integer factors in the continuous fraction to yield a fraction within LSB of the original value, but the temporary results (multiplications and additions before using GCD to remove the greatest common divisor) tend to overflow even 64-bit integers sometimes; I used 16 iterations for the tests, for about ten-twelve digits of precision.

    My current function seens to take about 6000 clock cycles on x86-64 to determine 1.24 = 31/25, and between 5000 and 14000 cycles for random double-precision floating-point numbers. It is rare for there to be common divisors in the numerator and denominator -- I didn't encounter any test value where at any point during the computation the numerator and denominator shared a common divisor -- but the math indicates it might be needed; it's just rare.

    So, I'd say even the simple approach, generating the fraction and the value it represents for each increasing number of continuous fraction factors, and comparing the error between the result and the original value, should be quite fast enough for real world use cases. I'd estimate something of the order of 100,000 cycles for a simple, straightforward implementation; much less if you care to optimize the logic.

    This is simple enough that I do believe calculators etc. use an exact or at least very similar algorithm.
    Last edited by Nominal Animal; 07-12-2013 at 01:20 AM.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    I have a custom C++ fraction data type that does this using a fast convergence algorithm. Its loop contains just 1x fabs, 3x floor, 2x division, 2x multiplication, 2x addition, 2x subtraction, and 4x comparisons. It needs no special case code for mixed-numbers, a.k.a improper fractions, does not make use or recurring decimals, does not convert to string, and it has no multiplications or divisions by powers of ten. The gcd is not required for simplifying the fraction afterwards either.

    It has unit tests that prove the correct answer for every possible fraction where the numerator and denominator sum to under 2000 (my tests can go at least 10x higher but that takes a long time), where both are positive of course. e.g. this is no problem:
    Code:
    double val = 577.0 / 1361.0;
    fract fr = val;
    assert(fr.numer == 577 && fr.denom == 1361);
    So, um yes I know the ideal algorithm. If you search the next hard enough you'll find it.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Registered User
    Join Date
    Oct 2011
    Posts
    847
    Quote Originally Posted by iMalc View Post
    It needs no special case code for mixed-numbers, a.k.a improper fractions
    Does it yield a good approximation for those, or does it just punt? What does it yield for example for 0.9999127?

    Quote Originally Posted by iMalc View Post
    So, um yes I know the ideal algorithm. If you search the next hard enough you'll find it.
    Bold claim. Care to link to the basis (articles, references?) of that claim?

  15. #15
    Registered User
    Join Date
    Jun 2005
    Posts
    6,287
    Quote Originally Posted by acho.arnold View Post
    Please does anybody know an algorithm which can be used to convert a decimal to a fraction especially irrational fractions thanks.
    That's impossible. An irrational value, by definition, means it cannot be expressed as a fraction (i.e. in the form of one integer divided by another). If it could be expressed as a fraction, it would be a rational value, not an irrational value.

    Quote Originally Posted by acho.arnold View Post
    That is a programm that can convert to 0.333333333333333333333 to 1/3 like any scientific calculator does.
    Scientific calculators do not do that, not matter how it might seem.

    If you divide 1 by 3, you might get a value which looks like 0.3333333333333 but, depending on the program, it might remember the two values divided. So any imprecision is cancelled out. In other words, programs which do that work with fractions internally (alternatively, they may simply round up 0.9999999999 to 1, if the number of decimal places exceeds some specified value).

    In any event, the algorithm is the sum of each digit multiplied by 10^-n where n is the number of places the digit is after the decimal point.
    Last edited by grumpy; 07-12-2013 at 06:45 AM.
    Right 98% of the time, and don't care about the other 3%.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question regarding extraction of value from a decimal fraction
    By abhishekcoder in forum C Programming
    Replies: 2
    Last Post: 04-08-2012, 12:57 PM
  2. Convert Decimal IP To Dotted Decimal Notation
    By MaSSaSLaYeR in forum C Programming
    Replies: 11
    Last Post: 11-16-2011, 05:18 PM
  3. Replies: 15
    Last Post: 10-06-2009, 11:20 PM
  4. how to convert decimal to hexa decimal in C/
    By kalamram in forum C Programming
    Replies: 4
    Last Post: 09-03-2007, 07:39 AM
  5. Fraction outputted as decimal
    By blindman858 in forum C++ Programming
    Replies: 3
    Last Post: 06-04-2005, 01:17 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21