(12C) Decimal to Fraction

08062018, 12:33 PM
(This post was last modified: 08062018 12:39 PM by Gamo.)
Post: #1




(12C) Decimal to Fraction
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:
Gamo 

08062018, 08:44 PM
(This post was last modified: 08062018 08:54 PM by Dieter.)
Post: #2




RE: (12C) Decimal to Fraction
(08062018 12:33 PM)Gamo Wrote: Program to covert Decimal to Fraction. 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 wellknown continued fraction method? Here is an adaptation for the 12C and its limited command set: Code: 01 STO 0 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 

08072018, 01:19 AM
Post: #3




RE: (12C) Decimal to Fraction
(08062018 08:44 PM)Dieter Wrote: Example: 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. 

08072018, 07:29 AM
(This post was last modified: 08072018 10:14 AM by Dieter.)
Post: #4




RE: (12C) Decimal to Fraction
(08072018 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. (08072018 01:19 AM)Albert Chan Wrote: Above example, fractions using 6 digits only get 5 decimal digits accuracy. 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 Now compare the seventh line with your result: Code: 577/408 1,414215686 2,12390 E6 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 

08072018, 09:29 AM
Post: #5




RE: (12C) Decimal to Fraction
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 

08072018, 11:38 AM
(This post was last modified: 08072018 11:51 AM by Dieter.)
Post: #6




RE: (12C) Decimal to Fraction
(08072018 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 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 

08072018, 12:49 PM
Post: #7




RE: (12C) Decimal to Fraction
(08072018 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.1239014e6 816/577 underestimated sqrt(2): 2.1238982e6 > 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 

08072018, 01:02 PM
Post: #8




RE: (12C) Decimal to Fraction
(08072018 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 

08072018, 01:52 PM
(This post was last modified: 08072018 03:37 PM by Albert Chan.)
Post: #9




RE: (12C) Decimal to Fraction
(08072018 12:49 PM)Albert Chan Wrote: Your Pi example illustrate even better, fraction with denominator <= 100: 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 underestimated (*) Any lowered k will underestimate 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 

08072018, 06:28 PM
Post: #10




RE: (12C) Decimal to Fraction
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 HP12C is left as an exercise for people with more patience with the 12C than I have.
<0ɸ0> Joe 

08072018, 07:10 PM
Post: #11




RE: (12C) Decimal to Fraction
(08072018 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 

08072018, 07:59 PM
Post: #12




RE: (12C) Decimal to Fraction
(08072018 07:10 PM)Dieter Wrote: But it's still RPL. For me one of the most obscure programming languages ever. #) 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 

08072018, 08:26 PM
Post: #13




RE: (12C) Decimal to Fraction
(08072018 07:59 PM)Albert Chan Wrote: Instead of reading RPL code, it might be easier to read Python fractions.py, function limit_denominator. If there only was a way to convert Python to RPN. 

08082018, 12:28 AM
(This post was last modified: 08082018 04:31 AM by Joe Horn.)
Post: #14




RE: (12C) Decimal to Fraction
(08072018 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. (08072018 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 bruteforce searching, which is why they limit the denominator to 4095. Sounds dubious to me, but that's what he said. <0ɸ0> Joe 

08082018, 06:05 PM
(This post was last modified: 08082018 07:51 PM by Thomas Klemm.)
Post: #15




RE: (12C) Decimal to Fraction
Here's a program for the HP11C:
Code: *LBL A It's the translation of this Python program: Code: from math import modf, ceil Which is based on Joe Horn's RPL program: Code: %%HP:T(3); 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 HP12C 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" 

08082018, 06:48 PM
Post: #16




RE: (12C) Decimal to Fraction
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 by these: Code: *LBL 4 And then remove that block at the end. This saves us two precious steps. 

08082018, 07:04 PM
(This post was last modified: 08082018 07:09 PM by Dieter.)
Post: #17




RE: (12C) Decimal to Fraction
(08082018 06:05 PM)Thomas Klemm Wrote: Here's a program for the HP11C: 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 

08082018, 07:31 PM
Post: #18




RE: (12C) Decimal to Fraction
(08082018 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:
But we also need: Code: x=y ; c = v ? We can switch the order: Code:  ; vc The function ABS is missing. But we can also compare the squares. Thus instead of: Code: ABS ; n/df 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 

08082018, 07:49 PM
Post: #19




RE: (12C) Decimal to Fraction
(08082018 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 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 

08082018, 09:44 PM
Post: #20




RE: (12C) Decimal to Fraction
(08082018 07:31 PM)Thomas Klemm Wrote: We can just inline these calls. I can't say for sure. Looks like you should do a complete 12C version and see if it runs. ;) (08082018 07:31 PM)Thomas Klemm Wrote: Good catch. And here we can shave off another 2 steps. But then... (08082018 07:49 PM)Thomas Klemm Wrote: The stack isn't lifted after the ENTER. Yes  as already mentioned: (08082018 07:04 PM)Dieter Wrote: ...can also be included in the subroutine itself (requires two ENTERs then). And finally: (08082018 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 

« Next Oldest  Next Newest »

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