CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

Thread: Convert double to fraction (a/b)

1. Member
Join Date
Oct 2002
Posts
70

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. 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.

3. Member
Join Date
Oct 2002
Posts
70

I don't get it

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

Thanks

4. 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:
• 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.

5. Member
Join Date
Oct 2002
Posts
70

6. Member
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. 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.

Posting Permissions

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