(12C) Decimal to Fraction - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Software Libraries (/forum-10.html) +--- Forum: General Software Library (/forum-13.html) +--- Thread: (12C) Decimal to Fraction (/thread-11178.html) Pages: 1 2 3 (12C) Decimal to Fraction - Gamo - 08-06-2018 12:33 PM 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 RE: (12C) Decimal to Fraction - Dieter - 08-06-2018 08:44 PM (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 RE: (12C) Decimal to Fraction - Albert Chan - 08-07-2018 01:19 AM (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. RE: (12C) Decimal to Fraction - Dieter - 08-07-2018 07:29 AM (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 RE: (12C) Decimal to Fraction - Gamo - 08-07-2018 09:29 AM 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 RE: (12C) Decimal to Fraction - Dieter - 08-07-2018 11:38 AM (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 RE: (12C) Decimal to Fraction - Albert Chan - 08-07-2018 12:49 PM (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 RE: (12C) Decimal to Fraction - Dieter - 08-07-2018 01:02 PM (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 RE: (12C) Decimal to Fraction - Albert Chan - 08-07-2018 01:52 PM (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 RE: (12C) Decimal to Fraction - Joe Horn - 08-07-2018 06:28 PM 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. RE: (12C) Decimal to Fraction - Dieter - 08-07-2018 07:10 PM (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 RE: (12C) Decimal to Fraction - Albert Chan - 08-07-2018 07:59 PM (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 RE: (12C) Decimal to Fraction - Thomas Klemm - 08-07-2018 08:26 PM (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. RE: (12C) Decimal to Fraction - Joe Horn - 08-08-2018 12:28 AM (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. RE: (12C) Decimal to Fraction - Thomas Klemm - 08-08-2018 06:05 PM 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 ex 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. RE: (12C) Decimal to Fraction - Thomas Klemm - 08-08-2018 06:48 PM 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. RE: (12C) Decimal to Fraction - Dieter - 08-08-2018 07:04 PM (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 RE: (12C) Decimal to Fraction - Thomas Klemm - 08-08-2018 07:31 PM (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 RE: (12C) Decimal to Fraction - Thomas Klemm - 08-08-2018 07:49 PM (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 RE: (12C) Decimal to Fraction - Dieter - 08-08-2018 09:44 PM (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