Help with an algorithm for converting decimals to fractions
08-28-2014, 06:03 AM (This post was last modified: 08-28-2014 06:59 AM by Joe Horn.)
Post: #5 Joe Horn Senior Member Posts: 1,628 Joined: Dec 2013
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 - 08-27-2014, 08:55 PM RE: Help with an algorithm for converting decimals to fractions - Paul Dale - 08-27-2014, 10:12 PM RE: Help with an algorithm for converting decimals to fractions - Thomas Klemm - 08-27-2014, 10:32 PM RE: Help with an algorithm for converting decimals to fractions - CosmicTruth - 08-28-2014, 12:51 AM RE: Help with an algorithm for converting decimals to fractions - Joe Horn - 08-28-2014 06:03 AM RE: Help with an algorithm for converting decimals to fractions - Joe Horn - 08-28-2014, 06:48 AM

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