50G fraction question Q-> function max denominator

[100LL]

Quick question on the 49G+/50G regarding fractions.

I like the 32S II fraction capability a lot when working in the lab because for deciphering dimensions. The 32SII allows you to convert a decimal to fraction and impose a maximum number for the denominator (handy because 64 is usually the highest desired).

Wondering if there's a way to get the 50G to do the same.

The manual doesn't show any options on Q-> other than decimal display accuracy.

[ijabbott]

You might be interested in the thread, "(50G) PDQ Algorithm in SRPL and URPL".

[burkhard]

That fraction capability (and ability to limit to 64ths or as I do, 32nds) is a wonderful thing on the 32SII, especially for American users.

One of the many great things I like about WP34S is that the developers included this capability and it's very workable and shop-handy. Considering that ALL three of the primary WP34S developers were from countries using French metric and not English fractional units, this was remarkably thoughtful of them!

Those of us in the USA, while we may exclusively use French units in our science and engineering jobs, are still forced to work with English fractional units at home. It's nothing to get on a soapbox over, but just a fact of life owing to the Industrial Revolution and development of standardized manufacturing and construction industries taking place here under that system. So us techie sorts wind up being fluid in both the French and English systems. A calculator that at least handles 1/2, 1/4, 1/8, 1/16, 1/32, 1/64 is a great boon.

[Joe Horn]

(10-24-2019 02:58 PM)100LL Wrote:  The 32SII allows you to convert a decimal to fraction and impose a maximum number for the denominator (handy because 64 is usually the highest desired).

Wondering if there's a way to get the 50G to do the same.

No, there's no way to specify a maximum denominator for the ->Q function, but here's a tiny program that does exactly what you seek. It's a flashback from way back in 1991 (HP 48 Goodies Disk #3). To make it work on an HP 50g, be sure to replace the SYSEVAL in the listing with the FLASHEVAL mentioned immediately above the listing. Enjoy!

Code:

DEC2FRAC for the HP 48SX/GX (faster and more complete than ->Q)
Improved Decimal-to-Fraction, by Joseph K. Horn, 21 March 1991

THE PROBLEM: The HP 48SX (->Q function) and HP 32SII (with maximum denominator
set) both miss many solutions, and slowly recalculate the summations for each
term rather than using a fast recursion formula to get each term from the
last two.

THE SOLUTION: This new algorithm finds the very best solution, very quickly.

ALGORITHM: Continued Fractions by fast recursion formula, then make a single
calculated jump backwards to the best possible fraction before the specified
maximum denominator.

Copyright (c) 1991 by Joseph K. Horn.  May be used freely in any application
that has no documentation.  May be in a documented application if the above
author is credited.

INPUT:

2: Decimal Number to be converted to a fraction
1: Maximum Allowed Denominator (a positive integer)

OUTPUT:

1: 'Numerator/Denominator'

Note: System flag -3 is cleared (to allow symbolic results).

EXAMPLE of completeness: What fraction is closest to the number "e", but with a
denominator not bigger than 20?

The HP 48SX and the HP 32SII say it's 19/7.  They both say that the next better
fraction is 87/32.  But there are two fractions between these which they
miss: 49/18 and 68/25.

Press 1 e^x 20 DEC2FRAC and see '49/18', the correct answer.

EXAMPLE of speed improvement: the golden ratio, (sqrt(5)+1)/2, which is
approximately 514229/317811.  This is found by the HP 48SX ->Q function in
3.23 seconds, and by DEC2FRAC in 1.29 seconds.

Note: The SYSEVAL in this program only works on the HP 48 (S/SX/G/GX).
It does not work in the HP 50g, which must use #162006h FLASHEVAL
instead of that SYSEVAL.

%%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.
\>>

[cdmackay]

(10-24-2019 09:59 PM)Joe Horn Wrote:  No, there's no way to specify a maximum denominator for the ->Q function, but here's a tiny program that does exactly what you seek.

…

[code]DEC2FRAC for the HP 48SX/GX (faster and more complete than ->Q)
Improved Decimal-to-Fraction, by Joseph K. Horn, 21 March 1991

thanks Joe; how does this compare to your PDQ program?

[Joe Horn]

(10-24-2019 11:02 PM)cdmackay Wrote:  thanks Joe; how does this compare to your PDQ program?

The main difference is that in DEC2FRAC, the user specifies a maximum denominator. In PDQ, the user specifies the error tolerance (the maximum difference between the input decimal and the output fraction).

Another difference is that DEC2FRAC is limited to the machine's floating-point precision for input and output (12 digits). PDQ has no limitations; its inputs and outputs can be of any desired length, and the tolerance can be any value.

[100LL]

Awesome Joe. Thanks !

[cdmackay]

thanks again Joe, and for the clarification, which I'd forgotten!

[100LL]

Is the port to the 49G+/50G really that simple by the way?

[Joe Horn]

(10-25-2019 09:42 PM)100LL Wrote:  Is the port to the 49G+/50G really that simple by the way?

Yes, although now that I think about it, I'd suggest replacing this:
# 5603Eh SYSEVAL
with this instead:
R\->I SWAP R\->I SWAP /
This eliminates all reliance on SYSEVAL or FLASHEVAL or any dangerous junk like that.

When that replacement is made in the HP 50g, the BYTES command (on the program by itself on the stack, not its name) returns 298.5, #ED4h. That's assuming that it was keyed in while the 50g was in exact mode, so the literal numbers in the program have no decimal points. If entered in approximate mode, BYTES returns 298.5, #8B6Bh.

I just tested it and it works on the 50g. Inputs: pi, 100. Output: 311/99.

[ijabbott]

(10-25-2019 11:42 PM)Joe Horn Wrote:  

(10-25-2019 09:42 PM)100LL Wrote:  Is the port to the 49G+/50G really that simple by the way?

Yes, although now that I think about it, I'd suggest replacing this:
# 5603Eh SYSEVAL
with this instead:
R\->I SWAP R\->I SWAP /
This eliminates all reliance on SYSEVAL or FLASHEVAL or any dangerous junk like that.

When that replacement is made in the HP 50g, the BYTES command (on the program by itself on the stack, not its name) returns 298.5, #ED4h. That's assuming that it was keyed in while the 50g was in exact mode, so the literal numbers in the program have no decimal points. If entered in approximate mode, BYTES returns 298.5, #8B6Bh.

I just tested it and it works on the 50g. Inputs: pi, 100. Output: 311/99.

It depends on the CAS mode though.

Code:

-2 CF -3 CF -105 CF π 100 DEC2FRAC

prompts to turn on Approx mode, and (after selecting 'Yes') outputs '311/99', and sets flag -105.

Code:

-2 CF -3 CF -105 SF π 100 DEC2FRAC

outputs a horrible, symbolic continued fraction.

Code:

-2 CF -3 SF -105 CF π 100 DEC2FRAC

outputs '311/99', and clears flag -3.

Code:

-2 CF -3 SF -105 SF π 100 DEC2FRAC

outputs '311/99', and clears flag -3.

Code:

-2 SF -3 CF -105 CF π 100 DEC2FRAC

outputs '311/99'.

Code:

-2 SF -3 CF -105 SF π 100 DEC2FRAC

outputs '311/99'.

Code:

-2 SF -3 SF -105 CF π 100 DEC2FRAC

outputs '311/99', and clears flag -3.

Code:

-2 SF -3 SF -105 SF π 100 DEC2FRAC

outputs '311/99', and clears flag -3.

In conclusion, setting flag -2 is a good idea!

[DavidM]

After thinking about this question a bit, a slightly different idea came to mind. I was wondering how I would determine which fraction whose denominator is a power of two would be the best fit for a given real number. I'm sure there's a more elegant way to do this, but I came up with the following brute-force approach which simply checks each possibility starting with "/2" and multiplying the denominator by 2 up to the specified limit. The closest combination is then returned as a symbolic number in the form "a+b/c" (or simply "b/c" as appropriate).

The code pertaining to the flags is to avoid the "Turn on approximate mode?" prompt that would result if you were in exact mode when the program was invoked.

Code:

\<<
   PUSH -105. SF
   2.
   \-> targ max cur
   \<<
      1. DUPDUP
      WHILE
         cur max \<=
      REPEAT
         cur DUP targ *
         0. RND DUP2 SWAP /
         targ - ABS

         4. PICK OVER >
         { 6. ROLL 6. ROLL 6. ROLL }
         IFT
         DROP2 DROP

         'cur' 2. STO*
      END
   \>>
   DROP SWAP R\->I SWAP R\->I
   OVER IDIV2 ROT
   -105. CF / +
   PROPFRAC PROPFRAC
   POP
\>>

Examples:

π 128 => '3+9/64'
π 32 => '3+5/32'
e 512 => '2+23/32'
0.5 8 => '1/2'
0.4 32 => '13/32'
-5 16 => -5
-1.4 128 => '-1+-51/128'

[DavidM]

Here's one last take on the "closest fraction with power-of-2 denominator" concept.

This one uses a SysRPL implementation, and instead of requiring the maximum denominator as a given argument, that value is obtained from a global variable named "MxDen". If that variable isn't found in the current path, a new one containing a default value of 64 is created for subsequent use. As such, there is only one argument required for this program: a value to be converted (either numeric or symbolic). The final result depends on which type is given as well as the value of MxDen.

When I was playing around with this, I realized that I often wanted to go back-and-forth between the symbolic and real/approximate representations of some value. So this version evolved to function as a "toggler" between those two forms. If given a real/approximate number, it is converted to the nearest rational form. If given a symbolic, it is converted to the nearest real form. In both cases, the result is based on the currently specified maximum denominator. This means that if you give the program an argument of π with a max denominator of 64, the result will be a decimal representation of the nearest "power of 2" rational that approximates π in that range (3+9/64): 3.140625. An exact integer is treated the same as a symbolic value; the result will be that same integer in approximate form.

The source code below is appropriate for the 50g's on-board MASD compiler (ASM from menu 256), and assumes you have the HP extable installed:

Code:

!NO CODE
!ASM
   DC Z0_            273AB
!RPL
DEFINE MaxDenominator ID MxDen
::
   CK1NOLASTWD

   ( validate/create max denominator value )
   ' MaxDenominator @
   ITE ::
      ( MaxDenominator found - check validity )
      ERRSET ::
         CKREAL
         %2 %< IT ERRJMP
      ;
      ERRTRAP ::
         "Bad MxDen Value" EXITMSGSTO
         #EXITERR ERRORSTO
         ERRJMP
      ;
   ;
   ::
      ( MaxDenominator not found - store default value )
      % 64 ' MaxDenominator STO
   ;

   ( main conversion routine - placed on return stack for later processing )
   ' ::
      ( setup locals )
      DUP %0< SWAP                  ( neg )
      %ABS %>%%                     ( target )
      MaxDenominator CKREAL %>%%    ( max )
      %%2                           ( current )
      3PICK                         ( numerator )
      %%1                           ( denominator )
      DUP                           ( delta )
      {{ delta denominator numerator current max target neg }}

      ( main loop - check all denominators up to max for closest fit )
      BEGIN
         current max %%<=
      WHILE ::
         ( determine current numerator )
         current target %%*      ( multiply target number by current denominator )
         %%>% %0 RNDXY %>%%      ( round the result to the nearest integer )

         ( determine current delta )
         DUP current %%/         ( divide test numerator by current denominator )
         target %%- %%ABS        ( delta = difference between current fraction and target )

         ( if stored delta is larger, update stored values )
         delta OVER %%>
         ITE ::
            !delta !numerator
            current !denominator
         ;
            2DROP

         ( increment current denominator to next power of 2 )
         current %%2 %%* !current
        ;
      REPEAT

      ( determine c,b,a for "a+b/c" )
      numerator denominator 2%%>%
      2DUP %MOD
      ROT OVER %- 3PICK %/

      ( convert to exact integers & reorder to a,b,c )
      FPTR2 ^R>Z UNROT
      FPTR2 ^R>Z SWAP
      FPTR2 ^R>Z

      ( convert a,b,c to formatted symbolic )
      3PICK Z0_ Z= ( is a=0? )
      3PICK Z0_ Z= ( is b=0? )
      ::
         ( a & b are 0: return 0 )
         2DUP ANDcase 4DROP

         ( only a is 0: return b/c )
         2DUP NOTAND case ::
            2DROP ROTDROP
            ' x/
            BINT3 SYMBN
         ;

         ( only b is 0: return a )
         SWAP NOTAND case 2DROP

         ( otherwise return a+b/c )
         ' x/ ' x+
         BINT5 SYMBN
      ;

      ( negate if appropriate )
      neg IT ::
         DUPTYPESYMB? ITE ::
            INNERCOMP
            ' xNEG SWAP
            #1+ SYMBN
         ;
            FPTR2 ^QNeg
      ;

      ( release locals )
      ABND
   ;
   >R

   CK&DISPATCH1

   ( real/approximate number: main routine will handle )
   real
      NOP

   ( exact integer: convert to real and leave on stack without further processing )
   BINT255d ::
      FPTR2 ^Z>R
      RDROP
   ;

   ( symbolic: ->NUM, process main routine, then ->NUM again for rounded result )
   symb ::
      CRUNCH
      R> EVAL
      CRUNCH
   ;
;
@

After compiling, store the code into a named variable (I call mine "Imp" for "Imperial") and you're all set! A zipped pre-compiled version is also attached.

[Albert Chan]

(10-29-2019 02:16 PM)DavidM Wrote:  After thinking about this question a bit, a slightly different idea came to mind. I was wondering how I would determine which fraction whose denominator is a power of two would be the best fit for a given real number. I'm sure there's a more elegant way to do this, but I came up with the following brute-force approach which simply checks each possibility starting with "/2" and multiplying the denominator by 2 up to the specified limit. The closest combination is then returned as a symbolic number in the form "a+b/c" (or simply "b/c" as appropriate) ...

For x best estimate with maximum denominator D, *AND* final denominator divides D, simply calculate round(x D) / D

Example:

x = e, D=512 => round(e * 512) / 512 = 1392 / 512 = 2 + 23/32
x = Pi, D=3600 => round(Pi * 3600) / 3600 = 11310 / 3600 = 3 + 17/120

[DavidM]

(11-08-2019 07:01 PM)Albert Chan Wrote:  For x best estimate with maximum denominator D, *AND* final denominator divides D, simply calculate round(x D) / D

Example:

x = e, D=512 => round(e * 512) / 512 = 1392 / 512 = 2 + 23/32
x = Pi, D=3600 => round(Pi * 3600) / 3600 = 11310 / 3600 = 3 + 17/120

Which is certainly another variation on the theme, but not quite the same thing I was focusing on (denominators whose value is specifically an integral power of 2).

The context I'm thinking of here is something like a ruler which has score marks at 1, 1/2, 1/4, 1/8, 1/16, and 1/32 intervals for the units in question (for non-American viewers, this how most of our inch-based rulers are scored). Chain calculations with mixed decimals and fractions can be streamlined with a utility that provides this kind of function.

I'm sure the brute-force method can be improved upon, but I would prefer an approach which gives the same kind of solution, ie. the closest approximation with the lowest power-of-2 denominator (up to the max allowed, of course).

I realize this is a highly-specific application, but I believe it's still in the spirit of the original poster's intent.

[Joe Horn]

(11-08-2019 08:43 PM)DavidM Wrote:  

(11-08-2019 07:01 PM)Albert Chan Wrote:  For x best estimate with maximum denominator D, *AND* final denominator divides D, simply calculate round(x D) / D

Example:

x = e, D=512 => round(e * 512) / 512 = 1392 / 512 = 2 + 23/32
x = Pi, D=3600 => round(Pi * 3600) / 3600 = 11310 / 3600 = 3 + 17/120

Which is certainly another variation on the theme, but not quite the same thing I was focusing on (denominators whose value is specifically an integral power of 2).

Albert's method automatically does that, if you use a power of 2 for D, no?

[Albert Chan]

(11-08-2019 08:43 PM)DavidM Wrote:  I'm sure the brute-force method can be improved upon, but I would prefer an approach which gives the same kind of solution, ie. the closest approximation with the lowest power-of-2 denominator (up to the max allowed, of course).

x' = round(x D) / D will gives you the same answer (for this case D = 2^n)

Perhaps it is easier to visualize if you consider denominator as the maximum D
In other words, fraction is not (yet) allowed to be simplified

x = (x D) / D = y / D

x' = y' / D, y' an integer

Now, what integer value of y' will minimize error ? y' = round(y)

error = |x - x'| = |y - y'| / D ≤ 0.5 / D

[DavidM]

(11-08-2019 09:01 PM)Joe Horn Wrote:  Albert's method automatically does that, if you use a power of 2 for D, no?

(11-08-2019 10:05 PM)Albert Chan Wrote:  x' = round(x D) / D will gives you the same answer (for this case D = 2^n)

Perhaps it is easier to visualize if you consider denominator as the maximum D
In other words, fraction is not (yet) allowed to be simplified

x = (x D) / D = y / D

x' = y' / D, y' an integer

Now, what integer value of y' will minimize error ? y' = round(y)

error = |x - x'| = |y - y'| / D ≤ 0.5 / D

OIC (Oh, I see!)

So changes are in order for my last program:
1) The maximum denominator (D in your explanation) will need to be "pinned" to the greatest power-of-2 ≤ the given value
2) After determining a,b,c in 'a+b/c', the GCD for b and c will be used to simplify the rational

I'm building the rational manually instead of using the CAS so that the program is flag-agnostic (I want it to behave the same way regardless of flag settings). I also prefer -(1+1/2) to -1+-1/2 when displaying negative symbolics, which is easily done by placing the negation as its final component. I find the former easier to read than the latter when on the stack.

Thanks to both of you for the education!