Help with an algorithm for converting decimals to fractions

[Namir]

I posted an HP Prime program that calculates the integer fractions that approximate a number with decimals (for a user-specified 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 HP-7 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

[Paul Dale]

(08-27-2014 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

[Thomas Klemm]

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

Now you multiply each entry with the corresponding value of the sequence, add the value of the left and write it to the right:

Code:

  3  7  15    1  292  ...
0 1  3  22  333  355  ...
1 0  1   7  106  113  ...

Thus the approximations of \(\pi\) are \(\frac{3}{1}, \frac{22}{7}, \frac{333}{106}, \frac{355}{113}, \dots\)

Cheers
Thomas

[CosmicTruth]

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

[Joe Horn]

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.

[Joe Horn]

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(.);
\<<
  IF DEPTH 1. SAME
  THEN
    IF DUP TYPE 0. ==
    THEN 1.E50 * R\->I 50 ALOG /
    END PROPFRAC { 0 1 } { 1 0 }
  ELSE DROP 3. ROLL EVAL FXND SWAP OVER IDIV2 ROT SWAP / PROPFRAC 4. ROLLD OVER 4. ROLLD * ADD
  END DUP EVAL SWAP \->NUM SWAP /
\>>