Help with an algorithm for converting decimals to fractions

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 

« Next Oldest  Next Newest »

Messages In This Thread 
Help with an algorithm for converting decimals to fractions  Namir  08272014, 08:55 PM
RE: Help with an algorithm for converting decimals to fractions  Paul Dale  08272014, 10:12 PM
RE: Help with an algorithm for converting decimals to fractions  Thomas Klemm  08272014, 10:32 PM
RE: Help with an algorithm for converting decimals to fractions  CosmicTruth  08282014, 12:51 AM
RE: Help with an algorithm for converting decimals to fractions  Joe Horn  08282014 06:03 AM
RE: Help with an algorithm for converting decimals to fractions  Joe Horn  08282014, 06:48 AM

User(s) browsing this thread: 1 Guest(s)