CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7
  1. #1
    Join Date
    Oct 2002
    Posts
    70

    Talking Convert double to fraction (a/b)

    Hi,

    I need to convert a double (1.31564 or whatever) to the format (a/b).

    Does anyone knows a simple function I can use????

    Thanks a lot

  2. #2
    Join Date
    Sep 2002
    Posts
    1,747
    Just use the standard continued fraction algorithm recursively with cutoff.
    In other words, create your continued fraction by:
    • strip off integer part
    • invert (1/x)
    • repeat until cutoffs exceeded (integer part or epsilon)

    then convert your continued fraction to a standard fraction.
    */*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/

    "It's hard to believe in something you don't understand." -- the sidhi X-files episode

    galathaea: prankster, fablist, magician, liar

  3. #3
    Join Date
    Oct 2002
    Posts
    70

    I don't get it

    Sorry, can you give me a simple example???

    Thanks

  4. #4
    Join Date
    Sep 2002
    Posts
    1,747

    sure

    A continued fraction in an expression like a0 + 1/(a1 + 1/(a2 + 1/(a3 + ...))). Its usually written more compactly like [a0; a1, a2, a3, ...]. To get a continued fraction, you perform the steps as mentioned above. Here's an illustration:
    • Start with your double (say 1.75).
    • Strip off integer part (a0 = 1) leaving working double 0.75.
    • Inverting gives 1.33. (repeated 3s)
    • Strip off integer part (a1 = 1) leaving 0.33.
    • Inverting gives 3.0 (plus or minus a very small amount due to floating point errors).
    • Strip off integer (a2 = 3) leaves a very small number.
    • Now just check this with some built in cutoff you create to give your accuracy a check (say 10^-8 -- but thats just an example -- experiment for best results). Do this check after each stripping. It fails here.
    • So now you have the continued fraction [1; 1, 3]. This is equivalent to 1 + 1/(1 + 1/3) which equals 1 + 1/(4/3) or 1 + 3/4 or 7/4. Which is correct for 1.75!

    So basically, you want a continued fraction vector of integer types (of whatever accuracy you find appropriate) which you populate in a (recursive or iterated) continued fraction algorithm method. Then you need a continued fraction to standard fraction simplification method. I do not know what design you are using to implement your fraction objects, so I couldn't give you more information about where to place these methods, but generally placing them in the class that handles your fractions is good (perhaps as private methods called by specific ctors and assignment operators). Its often good to put the cutoff as a member variable that you can change through some public "SetCutoff" type methods to allow for experimentation on good values for various tasks. You will also want to check to see if your continued fraction has become too long (maybe 20 elements long -- also experiment) because some doubles may not have enough information in them to give you a fractional equivalent that meets the first cutoff criteria.

    In general, this is the methodology used by many calculators and such to give this type of conversion, as it is the fastest converging means. However, it is important to realize that decimal representations that are not exact (like 0.33) cannot ever be fully represented by a machine, and so exact conversion would give something like 3333333333/10000000000 give or take some digits which is not what one usually wants. This is the reason for the cutoff, but it is even better for such calculations to keep fraction representations when possible and only convert to double or other floating point representations when absolutely needed.
    */*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/

    "It's hard to believe in something you don't understand." -- the sidhi X-files episode

    galathaea: prankster, fablist, magician, liar

  5. #5
    Join Date
    Oct 2002
    Posts
    70

    Thanks a lot

    Thanks, your information was very helpfull!!!

  6. #6
    Join Date
    Oct 2002
    Posts
    70

    Extract the numerator and denominator from the vector

    Hi,

    I have already created my vector, now, how can I get the numerator and the denominator from that vector??

    Thanks

  7. #7
    Join Date
    Sep 2002
    Posts
    1,747

    another recursion

    Basically, you start from the end. The [...a(N-1), aN] means something that looks like .../(a(N-1) + 1/aN). So the simplification becomes (a(N-1) * aN + 1)/aN. Now in general, you keep moving from the end of the vector forward, storing the intermediate fraction a/b which becomes inverted and added to the next vector element forward. Or say you have simplified forward to aM + 1/(a/b). Then that becomes (aM * a + b)/a. Repeat until you finish the vector.
    */*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/

    "It's hard to believe in something you don't understand." -- the sidhi X-files episode

    galathaea: prankster, fablist, magician, liar

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured