Help with an algorithm for converting decimals to fractions

08272014, 08:55 PM
(This post was last modified: 08272014 08:56 PM by Namir.)
Post: #1




Help with an algorithm for converting decimals to fractions
I posted an HP Prime program that calculates the integer fractions that approximate a number with decimals (for a userspecified number of continued fraction coefficients). See the HP Prime listing if my description is ambiguous. The program uses an array to store the coefficients of the continued fraction. The program then uses the values in this array to calculate the final numerator and denominator that approximate the input decimal value.
The Math Pac for the HP7 has a program that performs a similar task. I believe it does its task WITHOUT using an array to store the coefficients of the continued fraction!! My question to you all (and especially Jo Horn) is, "What is the algorithm that converts decimals to fractions that does not use an array to store the coefficients of the continued fraction. I will be happy if you give me a general algorithm. I appreciate your input! :) Namir 

08272014, 10:12 PM
Post: #2




RE: Help with an algorithm for converting decimals to fractions
(08272014 08:55 PM)Namir Wrote: My question to you all (and especially Jo Horn) is, "What is the algorithm that converts decimals to fractions that does not use an array to store the coefficients of the continued fraction. I will be happy if you give me a general algorithm. The 34S doesn't hold the coefficients. See decn.c, function decNumber2Fraction. The code repeatedly takes the reciprocal of the fractional part and maintains a running fraction. I didn't analyse the stability of this approach but it seems okay enough.  Pauli 

08272014, 10:32 PM
(This post was last modified: 08282014 03:29 AM by Thomas Klemm.)
Post: #3




RE: Help with an algorithm for converting decimals to fractions
Let's assume you wan't to calculate the common fraction of the continued fraction of \(\pi\) = [3; 7, 15, 1, 292, ...].
Then you write this sequence down and below a matrix of 0 and 1: Code: 3 7 15 1 292 ... Code: 3 7 15 1 292 ... Cheers Thomas 

08282014, 12:51 AM
Post: #4




RE: Help with an algorithm for converting decimals to fractions
i used a array for my 50g because i wanted carpenter type fractions. i know this is just the opposite of what your looking for and i am interested in this answer too (for 50g).
Thanks ~~~~8< Art >8~~~~ PS: Please post more 50G stuff :) 

08282014, 06:03 AM
(This post was last modified: 08282014 06:59 AM by Joe Horn.)
Post: #5




RE: Help with an algorithm for converting decimals to fractions
Paul and Thomas are right. If you don't mind the inevitable accumulating roundoff errors, just keep reciprocating the fraction part of your input to generate the partial quotients of the continued fraction, and use them one by one to generate each successive convergent. However, if you express the input as an exact ratio (easy to do, e.g. 314159/100000), there will be no roundoff errors if you keep everything as a ratio of integers, as in the example below. There's no need to store anything other than the current and previous convergent, and the current fraction part. Always start with 0/1 as the initial "previous convergent" and 1/0 as the intitial "current convergent".
Example: Input (N) = 3+14159/100000 Previous Convergent (PC) = 0/1 Current Convergent (CC) = 1/0 N:=1/frac(N) = 7+887/14159 PC = 1/0 CC = (3*1+0) / (3*0+1) = 3/1 N:=1/frac(N) = 15+854/887 PC = 3/1 CC = (7*3+1) / (7*1+0) = 22/7 N:=1/frac(N) = 1+33/854 PC = 22/7 CC = (15*22+3) / (15*7+1) = 333/106 N:=1/frac(N) = 25+29/33 PC = 333/106 CC = (1*333+22) / (1*106+7) = 355/113 N:=1/frac(N) = 1+4/29 PC = 355/113 CC = (25*355+333) / (25*113+106) = 9208/2931 N:=1/frac(N) = 7+1/4 PC = 9208/2931 CC = (1*9208+355) / (1*2931+113) = 9563/3044 N:=1/frac(N) = 4 PC = 9563/3044 CC = (7*9563+9208) / (7*3044+2931) = 76149/24239 N:=1/frac(N) = infinity (we're done!) PC = 76149/24239 CC = (4*76149+9563) / (4*24239+3044) = 314159/100000, exact. Thus the principle convergents for 3.14159 are exactly: 3/1 22/7 333/106 355/113 9208/2931 9563/3044 76149/24239 314159/100000 ... and nothing was stored along the way other than N, PC, and CC. <0ɸ0> Joe 

08282014, 06:48 AM
(This post was last modified: 08282014 06:49 AM by Joe Horn.)
Post: #6




RE: Help with an algorithm for converting decimals to fractions
Here's a little HP 50g program that is a demo of the algorithm for converting a decimal into a fraction without storing the partial quotients of the expanded continued fraction.
Instructions: (1) Clear the stack. Put calculator in exact mode. (2) Place on level 1 of the stack either a decimal number, or an algebraic ratio of two integers, e.g. '123/234'. (3) Run the program repeatedly. Stop when level 4 shows infinity. Each iteration will display the following on the stack: 4: Current value of N. Stop when it's infinity. 3: Previous Convergent p/q in the form of { p q } 2: Current Convergent a/b in the form { a b } 1: Decimal evaluation of a/b Warning: Program must be loaded and run in exact mode. 'ITER8' ("Iterate") by Joe Horn Code: %%HP: T(3)A(R)F(.); <0ɸ0> Joe 

« Next Oldest  Next Newest »

User(s) browsing this thread: