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