(12C) Decimal to Fraction

[Gamo]

Program to covert Decimal to Fraction.

This program still need improvement and still not a foolproof routine.
Anyone here got any idea is very welcome.

Example: example used FIX 4

3.1416 [R/S]

1250 [X<>Y] 3927 // Denominator <-> Numerator

Answer: 3927 / 1250

Program: Decimal to Fraction

Code:


01 ENTER
02   x
03  √x
04 STO 0
05   1
06 STO 1
07 R↓
08 1/x
09 STO x 1
10 ENTER
11 INTG
12   -
13 EEX
14   4
15 1/x
16 X≤Y
17 GTO 07
18 RCL 0
19 RCL 1
20 INTG
21   x
22 LSTx

Gamo

[Dieter]

(08-06-2018 12:33 PM)Gamo Wrote:  Program to covert Decimal to Fraction.

This program still need improvement and still not a foolproof routine.
Anyone here got any idea is very welcome.

The program only seems to return a result if the calculated fraction exactly (!) matches the input. But I am not sure if I really understand how it works.

But why don't you simply use the well-known continued fraction method?
Here is an adaptation for the 12C and its limited command set:

Code:

01 STO 0
02 STO 1
03 0
04 STO 2
05 1
06 RCL 0
07 INTG
08 RCL 2
09 x
10 +
11 STO 2
12 RCL 0
12 x
14 ,
15 5
16 +
17 INTG
18 STO 3
19 RCL 2
20 /
21 RND
22 RCL 0
23 RND
24 -
25 x=0?
26 GTO 35
27 R↓
28 RCL 2
29 X<>Y
30 RCL 1
31 FRAC
32 1/x
33 STO 1
34 GTO 07
35 RCL 2
36 RCL 3
37 GTO 00

The program stops if the fraction agrees with the (positive) input when rounded to display precision.

Example:
Determine a fraction that agrees with √2 in four decimals.

FIX 4
2 [√x] [R/S] => 239 [X<>Y] 169
Indeed the quotient is 1,414201183.

Or try pi to six decimals:

FIX 6
3,141592654 [R/S] => 355 [X<>Y] 113

The well known approximation 355/113 = 3,141592920.
That's 3,141593 when rounded to 6 decimals.

Finally your example: what's exactly 3,1416 ?

FIX 9
3,1416 [R/S] => 3927 [X<>Y] 1250

Dieter

[Albert Chan]

(08-06-2018 08:44 PM)Dieter Wrote:  Example:
Determine a fraction that agrees with √2 in four decimals.

FIX 4
2 [√x] [R/S] => 239 [X<>Y] 169
Indeed the quotient is 1,414201183.

Hi, Dieter:

Can the code changed to limit size of denominator instead ?

Above example, fractions using 6 digits only get 5 decimal digits accuracy.
Instead of 239/169, you are better off with 1.41421

these six digits are better: 816/577 = 1.414211438

Ideally, we like the fraction to generate better than decimals of same digits.
For example 355/113 is a great estimate of pi, accuracy almost to 8 digits.

[Dieter]

(08-07-2018 01:19 AM)Albert Chan Wrote:  Can the code changed to limit size of denominator instead ?

Sure it can be modified. The denominator is calculated in line 11 and stored in R2. You can change the program so that it checks whether this value is larger than a certain limit. In that case it may not store the new denominator (exceeds the limit) and return the last one from R2 instead. The following test whether the rounded fraction agrees with the input should then be removed.

(08-07-2018 01:19 AM)Albert Chan Wrote:  Above example, fractions using 6 digits only get 5 decimal digits accuracy.
Instead of 239/169, you are better off with 1.41421

these six digits are better: 816/577 = 1.414211438

Let me try to understand what you mean here. Maybe you want more correct digits in the approximation than used for numerator and denominator. This is not how the program works. Instead you say "give me a fraction with 5 correct decimals" and the program returns a result. You may simply adjust the display format to get even more accurate results. Or you change the program so that it limits the denominator. Or choose a completely different algorithm. ;-)

Edit:
The result 239/169 was obtained with a setting of four (!) decimals, or five significant digits, in FIX 4 mode. And that's exactly the target it meets. If you want six significant digits, or five decimals, set FIX 5 and see what you get. Maybe the following table gives some more insights here.

The algorithm used here generates the following fractions for √2:

Code:

fraction      result        error
-------------------------------------
    1/1       1             -4,1 E-1
    3/2       1,5            8,6 E-2
    7/5       1,4           -1,4 E-2
   17/12      1,416666667    2,5 E-3
   41/29      1,413793103   -4,2 E-4
   99/70      1,414285714    7,2 E-5
  239/169     1,414201183   -1,2 E-5
  577/408     1,414215686    2,1 E-6
 1393/985     1,414213198   -3,6 E-7
 3363/2378    1,414213625    6,3 E-8
 8119/5741    1,414213552    1,1 E-8
19601/13860   1,414213564    1,8 E-9
47321/33461   1,414213562    3,1 E-10

Now compare the seventh line with your result:

Code:

  577/408     1,414215686    2,12390 E-6
  816/577     1,414211438   -2,12390 E-6

Even with 12 digit precision the error of 577/408 produced by the program is the same as for 816/577. The former even has a lower denominator. In FIX 5 mode the result 577/408 is not returned only because the fifth decimal is rounded up (1,41422) so that it does not meet the implemented exit condition (rounded input = rounded fraction).

That's why I think the algorithm is not that bad at all. If you want to see all possible fractions, like the ones in the table above, the program can easily be adjusted accordingly.

By the way – I almost forget to mention this: the original program was a 15C version by Joe Horn, published in HP Solve. I did some optimizations and streamlined Joe's program a bit to get a <40 step version for the HP35s. This in turn was the base for the above 12C program which includes less "stackrobatics" and avoids the R↑ command which the 12C does not feature. It requires R0...R3, but with three more steps it can be adjusted so that only R0...R2 are used. After applying the 12C changes to the 35s again the latter was down to 32 steps.

Dieter

[Gamo]

Thanks Dieter
Your program is a lot better.

My program use this algorithm.

Convert 0.15625 to Fraction

0.15625 --> 1 / 0.15625 = 6.4

FRAC --> 0.4 --> 1 / 0.4 = 2.5

FRAC --> 0.5 --> 1 / 0.5 = 2

FRAC --> 0

Denominator: 6.4 x 2.5 x 2 = 32
Numerator: 0.15625 x 32 = 5

Gamo

[Dieter]

(08-07-2018 01:19 AM)Albert Chan Wrote:  Can the code changed to limit size of denominator instead ?

Here is a version that does it:

Code:

01 STO 0
02 STO 1
03 0
04 STO 2
05 1
06 RCL 0
07 INTG
08 RCL 2
09 x
10 +
11 RCL n
12 X<>Y
13 x≤y?
14 GTO 25
15 RCL 2
16 RCL 2
17 RCL 0
18 x
19 ,
20 5
21 +
22 INTG
23 STO 1
24 GTO 00
25 STO 2
26 R↓
27 R↓
28 RCL 2
29 X<>Y
30 RCL 1
31 FRAC
32 1/x
33 STO 1
34 GTO 07

Set the max. denominator using the 12C's [n] key.

Example:
Approximate pi with denominators up to 100 and 200.

100 [n]
3,141592654 [R/S] => 22 [X↔Y] 7

200 [n]
3,141592654 [R/S] => 355 [X↔Y] 113

Try √2 with at most six digits in numerator plus denominator.
This means the largest denominator is 999/√2 = 706,...

706 [n]
2 [√x] [R/S] => 577 [X↔Y] 408

[÷] => 1,414215686

BTW, on exit the numerator and denominator are stored in R1 and R2. The higher stack levels (Z and T) hold the next higher (better) denominator, i.e. the first one that exceeds the set limit. For the last example this is 985.

Dieter

[Albert Chan]

(08-07-2018 07:29 AM)Dieter Wrote:  Even with 12 digit precision the error of 577/408 produced by the program is the same as for 816/577. The former even has a lower denominator. In FIX 5 mode the result 577/408 is not returned only because the fifth decimal is rounded up (1,41422)

I made a mistake with 816/577. It is not a continued fraction of sqrt(2)

With this mistake, I discovered my misconception with continued fraction.
I thought "best" fraction with limited denominator is always a continued fraction ... FALSE

577/408 over - estimated sqrt(2): 2.1239014e-6
816/577 under-estimated sqrt(2): 2.1238982e-6 --> lowered error by by 0.00015%

Your Pi example illustrate even better, fraction with denominator <= 100:
continued fraction of pi => 22/7 = 3.142857
pi.limit_denominator => 311/99 = 3.141414 --> about 7X more accurate

[Dieter]

(08-07-2018 12:49 PM)Albert Chan Wrote:  I thought "best" fraction with limited denominator is always a continued fraction ... FALSE

OK then – so let's design a better algorithm. The continued fraction approach is known, what kind of different method would you suggest?

By the way, I just tried it on the HP35s:

706 [/c]
2 [√x] =>  1  239/577  (=816/577)

99 [/c]
[pi] =>  3  14/99   (=311/99)

;-)

Dieter

[Albert Chan]

(08-07-2018 12:49 PM)Albert Chan Wrote:  Your Pi example illustrate even better, fraction with denominator <= 100:
continued fraction of pi => 22/7 = 3.142857
pi.limit_denominator => 311/99 = 3.141414 --> about 7X more accurate

Peeking inside Python fractions.py, I learned the procedure: (limit_denominator method)
It is continued fractions ... with a twist

using above example, pi is bounded by 2 continued fractions, both with denomination below 100

3/1 < pi < 22/7

pi = (3 + 22k) / (1 + 7k) for some k (k=0, we get 3/1, k=infinity, we get 22/7)

if k is integer, the best is k=15, next continued fraction, 333/106, slightly under-estimated (*)
Any lowered k will under-estimate more, but perhaps better than 22/7

So, we solve for biggest denominator <= 100, we get k=14

(3+22*14)/(1+7*14) < pi < 22/7
311/99 < pi < 22/7

pick the one closest to pi, thus return 311/99

(*) actually, the best is when k=16, getting the ubiquitous 355/113.

Continued fraction coefficient only uses the integer part, and not the closest integer.
This setup guaranteed the value bounded between 2 continued fractions.
So, without using a calculator to confirm, 333/106 < pi < 355/113

[Joe Horn]

My DEC2FRAC program on Goodies Disk #3 (21 March 1991) for the HP 48 uses this algorithm: "Continued Fractions by fast recursion formula, then make a single calculated jump backwards to the best possible fraction before the specified maximum denominator." It gets the best possible answer even if it's NOT one of the principal convergents of the continued fraction, and does so very quickly. The RPL listing (linked above) is fully commented. Porting it to the HP-12C is left as an exercise for people with more patience with the 12C than I have.

[Dieter]

(08-07-2018 06:28 PM)Joe Horn Wrote:  It gets the best possible answer even if it's NOT one of the principal convergents of the continued fraction, and does so very quickly. The RPL listing (linked above) is fully commented.

But it's still RPL. For me one of the most obscure programming languages ever. #-)

I tried to understand the code in the .SRC file... but without success. So I would like to ask if you could provide the algorithm in a different (more readable) way. I did some tests on the 12C and some cases seem to work – while others don't.

BTW, I tried the "e" example in the textfile, with denominators up to 20. You said the 32s and 48 returned 19/7 while 49/18 is a (slightly) better match. Actually this is what the 35s displays, so it obviously uses the newer, upgraded algorithm.

Dieter

[Albert Chan]

(08-07-2018 07:10 PM)Dieter Wrote:  But it's still RPL. For me one of the most obscure programming languages ever. #-)

I tried to understand the code in the .SRC file... but without success. So I would like to ask if you could provide the algorithm in a different (more readable) way. I did some tests on the 12C and some cases seem to work – while others don't.

Instead of reading RPL code, it might be easier to read Python fractions.py, function limit_denominator.
On my machine, it is located at c:\python\lib\fractions.py

[Thomas Klemm]

(08-07-2018 07:59 PM)Albert Chan Wrote:  Instead of reading RPL code, it might be easier to read Python fractions.py, function limit_denominator.
On my machine, it is located at c:\python\lib\fractions.py

If there only was a way to convert Python to RPN.

[Joe Horn]

(08-07-2018 07:10 PM)Dieter Wrote:  I tried to understand the code in the .SRC file... but without success. So I would like to ask if you could provide the algorithm in a different (more readable) way.

I'll see what I can do. Unfortunately I think in RPL.

EDIT: Dang. I wish I'd kept the stack diagrams that must've been made while writing that program. Now I gotta reconstruct it using SST. Ugh.

(08-07-2018 07:10 PM)Dieter Wrote:  BTW, I tried the "e" example in the textfile, with denominators up to 20. You said the 32s and 48 returned 19/7 while 49/18 is a (slightly) better match. Actually this is what the 35s displays, so it obviously uses the newer, upgraded algorithm.

Both the 33S and 35s do find the intermediate convergents, which the 32SII misses, but Cyrille de Brebisson told everybody at an HHC conference a few years ago that those models do it by brute-force searching, which is why they limit the denominator to 4095. Sounds dubious to me, but that's what he said.

[Thomas Klemm]

Here's a program for the HP-11C:

Code:

  *LBL A
   STO 1        ; c f
   CLx          ; 0 f
   STO 2        ; u=0 f
   R↓           ; f
   STO 0        ; f
   1            ; 1 f
   STO 3        ; v=1 f
  *LBL 0        ; while
   RCL 1        ; c v f
   x≤y          ; c ≤ v ?
   GTO 1        ; done
   R↓           ; v f
   R↓           ; f
   x=0          ; f = 0 ?
   GTO 1        ; done
   1/x          ; 1/f
   FRAC         ; f'=frac(1/f)
   RCL 2        ; u f'
   LSTx         ; 1/f u f'
   INT          ; int(1/f) u f'
   RCL 3        ; v int(1/f) u f'
   STO 2        ; u'=v
   ×            ; v*int(1/f) f'
   +            ; u+v*int(1/f) f'
   STO 3        ; v'=u+v*int(1/f) f'
   GTO 0        ; while
  *LBL 1        ; done
   x=y          ; c = v ?
   GTO 2        ; no need to jump
   -            ; v-c
   RCL 2        ; u v-c
   ÷            ; (v-c)/u
   INT          ; int((v-c)/u)
   1            ; 1 int((v-c)/u)
   +            ; ceil((v-c)/u)
   RCL 2        ; u ceil((v-c)/u)
   ×            ; u*ceil((v-c)/u)
   STO - 3      ; v -= u*ceil((v-c)/u)
  *LBL 2        ; skip back
   RCL 2        ; u
   GSB 5        ; diff
   RCL 3        ; v
   GSB 5        ; diff
   x≤y 
   GTO 3
   RCL 2        ; u
   GTO 4
  *LBL 3
   RCL 3        ; v
  *LBL 4
   ENTER        ; q q
   GSB 6        ; p q
   RTN
  *LBL 5        ; diff
   ENTER        ; d d
   GSB 6        ; n d
   x<>y         ; d n
   ÷            ; n/d
   RCL 0        ; f n/d
   -            ; n/d-f
   ABS          ; |n/d-f|
   RTN          ; diff
  *LBL 6        ; round
   RCL 0        ; f d
   ×            ; f*d
   .            ;
   5            ; 0.5 f*d
   +            ; f*d+0.5
   INT          ; round(f*d)
   RTN

It's the translation of this Python program:

Code:

from math import modf, ceil

def diff(f, d):
    n = round(d * f, 0)
    return abs(f - n / d)

def dec2frac(f, c):
    if c < 2 and int(f) == f:
        return
    u, v, F = 0, 1, f
    while v < c and f:
        g = 1 / f
        f, _ = modf(g)
        u, v = v, u + v * int(g)
    if v > c:
        v  -= u * ceil((v - c) / u)
    q = u if diff(F, u) < diff(F, v) else v
    p = round(q * F, 0)
    return p, q

Which is based on Joe Horn's RPL program:

Code:

%%HP:T(3);
@ DEC2FRAC, by Joseph K. Horn
\<< DUP2 @ Must be two arguments.  Exit now if max denominator < 2,
  IF 1 > SWAP FP AND @ or if decimal fraction is an integer.
  THEN \-> f c @ Store decimal fraction, and max denominator.

    \<< 0 1 f @ Calculate only denominators.  Do numerator only at end.
      WHILE OVER c < OVER AND @ Do until bigger than max denominator
      REPEAT INV DUP FP 4 ROLLD IP OVER * ROT + ROT @ This is the
      END DROP DUP2 c @ recursion formula continued fraction expansion.

      IF DUP2 > @ Is there a possible "missing" fraction?
      THEN - OVER / CEIL * - @ This is the new, fast "jump backwards".
      ELSE 3 DROPN @ (Sometimes there's no need to jump.)
      END DUP2 1 2 @ Take the new denominator & the previous one, and

      START DUP f * 0 RND SWAP / f - ABS SWAP @ turn into fractions.
      NEXT @ See which one's closest to the original decimal fraction.

      IF > @ Compare the two solutions, and
      THEN SWAP @ pick the better one.
      END DROP DUP f * 0 RND SWAP @ Calculate the numerator.
    \>> @ End of real work; now clean up the output.

    IF DUP ABS 1 > @ Is the denominator greater than 1?
    THEN -3 CF # 5603Eh SYSEVAL @ If so, make output into 'A/B' form.
    ELSE DROP @ Otherwise, get rid of extraneous denominator,
    END @ and exit program.

  ELSE DROP @ If bad arguments, do nothing to "decimal fraction", but
  END @ get rid of "maximum denominator" and exit program.
\>>

You may have noticed that I skipped the initial test. But adding that is probably trivial.
Also I assume that this program can be easily adapted for the HP-12C and other models.

Examples

1 e^x 20 [A]
49
x<>Y
18
÷
2.7222

π 100 [A]
311
x<>y
99
÷
3.1414

Kind regards
Thomas

---

For those interested I've added the raw translation of the Python program using the Python to FOCAL Compiler:

Code:

LBL "DEC2FRA"
STO 01 ; c
RDN
STO 00 ; f
RDN
RCL 01 ; c
2
X<=Y?
GTO 00
RCL 00 ; f
INT
RCL 00 ; f
X#Y?
GTO 00
RTN
LBL 00
0
1
RCL 00 ; f
None
X<>Y
STO 02 ; u
RDN
STO 03 ; v
RDN
STO 04 ; F
RDN
LBL 01
RCL 03 ; v
RCL 01 ; c
X<=Y?
GTO 02
RCL 00 ; f
0
X=Y?
GTO 02
1
RCL 00 ; f
/
STO 05 ; g
RDN
RCL 05 ; g
None
STO 00 ; f
RDN
STO 06 ; _
RDN
RCL 03 ; v
RCL 02 ; u
RCL 03 ; v
RCL 05 ; g
INT
*
+
X<>Y
STO 02 ; u
RDN
STO 03 ; v
RDN
GTO 01
LBL 02
LBL 03
RCL 03 ; v
RCL 01 ; c
X>=Y?
GTO 04
RCL 03 ; v
RCL 02 ; u
RCL 03 ; v
RCL 01 ; c
-
RCL 02 ; u
/
XEQ CEIL
*
-
STO 03 ; v
RDN
GTO 04
LBL 04
RCL 04 ; F
RCL 02 ; u
XEQ DIST
RCL 04 ; F
RCL 03 ; v
XEQ DIST
X<=Y?
GTO 05
RCL 02 ; u
GTO 06
LBL 05
RCL 03 ; v
LBL 06
STO 07 ; q
RDN
RCL 07 ; q
RCL 04 ; F
*
0
RND
STO 08 ; p
RDN
RCL 08 ; p
RCL 07 ; q
RTN

This doesn't work but it gave me a skeleton which was helpful to start with.

[Thomas Klemm]

Just noticed that we could inline the round subroutine when it's called at the end of the program.
Thus you may just replace these lines:

Code:

  *LBL 4
   ENTER        ; q q
   GSB 6        ; p q
   RTN

by these:

Code:

  *LBL 4
   ENTER        ; q q
  *LBL 6        ; round
   RCL 0        ; f d
   ×            ; f*d
   .            ;
   5            ; 0.5 f*d
   +            ; f*d+0.5
   INT          ; round(f*d)
   RTN

And then remove that block at the end.
This saves us two precious steps.

[Dieter]

(08-08-2018 06:05 PM)Thomas Klemm Wrote:  Here's a program for the HP-11C:
...
It's the translation of this Python program:
...
Which is based on Joe Horn's RPL program:
...
Also I assume that this program can be easily adapted for the HP-12C and other models.

Fine, thank you very much. The translation for the 12C is a bit tricky since there are no subroutines. ;-)

Anyway, this afternoon I managed to do a version for the 35s. Seems to work, but I think I have to do some more tests. For the given examples the results are the same as yours. For √2 and denominators up to 700 the program does calculate 816/577 as a solution, but since with 12 digit precision the error is the same as for 577/408 the latter is returned.

I also would like use the program for the case where the approximation error is given, i.e. check whether the fraction agrees with the input when rounded to display precision. In a way it seems to work, but I'll have to take a closer look at this. ;-)

Finally I wanted to suggest an improvement regarding the GSB 6 subroutine, but you noticed this yourself. Since both calls are preceded by an ENTER the latter can also be included in the subroutine itself (requires two ENTERs then). It even looks like this way LBL 4 could be replaced with LBL 6. But this doesn't seem to save more steps.

Dieter

[Thomas Klemm]

(08-08-2018 07:04 PM)Dieter Wrote:  The translation for the 12C is a bit tricky since there are no subroutines. ;-)

We can just inline these calls.

There are only two tests:

• x≤y
• x=0
  

But we also need:

Code:

   x=y          ; c = v ?
   GTO 2        ; no need to jump
   -            ; v-c

We can switch the order:

Code:

   -            ; v-c
   x=0          ; c = v ?
   GTO 2        ; no need to jump

The function ABS is missing. But we can also compare the squares.

Thus instead of:

Code:

   ABS          ; |n/d-f|

We can just use:

Code:

   ENTER
   ×

Did I miss something?

Quote:Finally I wanted to suggest an improvement regarding the GSB 6 subroutine, but you noticed this yourself. Since both calls are preceded by an ENTER the latter can also be included in the subroutine itself (requires two ENTERs then). It even looks like this way LBL 4 could be replaced with LBL 6.

Good catch. And here we can shave off another 2 steps.

Thanks
Thomas

[Thomas Klemm]

(08-08-2018 07:31 PM)Thomas Klemm Wrote:  Good catch. And here we can shave off another 2 steps.

Zu früh gefreut:

Code:

  *LBL 4        ; round
   ENTER        ; d d
   RCL 0        ; f d d
   ×            ; f*d d
   .            ;
   5            ; 0.5 f*d d
   +            ; f*d+0.5 d
   INT          ; round(f*d) d
   RTN          ; n d

The stack isn't lifted after the ENTER.
So we need two ENTER statements.
Thus we can only get rid of the LBL 6.

Cheers
Thomas

[Dieter]

(08-08-2018 07:31 PM)Thomas Klemm Wrote:  We can just inline these calls.
...
There are only two tests
...
The function ABS is missing. But we can also compare the squares.
...
Did I miss something?

I can't say for sure. Looks like you should do a complete 12C version and see if it runs. ;-)

(08-08-2018 07:31 PM)Thomas Klemm Wrote:  Good catch. And here we can shave off another 2 steps.

But then...

(08-08-2018 07:49 PM)Thomas Klemm Wrote:  The stack isn't lifted after the ENTER.
So we need two ENTER statements.

Yes - as already mentioned:

(08-08-2018 07:04 PM)Dieter Wrote:  ...can also be included in the subroutine itself (requires two ENTERs then).
...But this doesn't seem to save more steps.

And finally:

(08-08-2018 07:49 PM)Thomas Klemm Wrote:  Thus we can only get rid of the LBL 6.

Which also means that GSB 6 becomes GSB 4.

Dieter