Post Reply 
Little explorations with HP calculators (no Prime)
11-05-2017, 10:28 PM (This post was last modified: 11-05-2017 10:29 PM by Joe Horn.)
Post: #248
RE: Little explorations with HP calculators (no Prime)
(11-05-2017 04:05 PM)pier4r Wrote:  I am slowly continuing to explore the "integer numerator ranges that enclose pi" ...

... I am pretty sure other people could make the program way faster. Therefore I posted it because I am curious to see how it can be optimized.

Although the following does not "optimize" your code per se, but rather replaces its algorithm with a much faster one, it still might be of some interest to you. Given any decimal fraction in level 2, and a maximum denominator in level 1, it returns the best fraction, much faster than the brute-force search method.

Example:
pi, 1000, DEC2FRAC --> 355/113 in 0.39 seconds
pi, 100000, DEC2FRAC --> 312689/99532 in 0.43 seconds

This program is a slight modification of a program on HP48 Goodies Disk #3.

Everything after each "@" is a comment.

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 R\->I SWAP R\->I SWAP / @ 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.
\>>

HP 50g BYTES: 298.5 #ED4h

X<> c
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Little explorations with HP calculators (no Prime) - Joe Horn - 11-05-2017 10:28 PM



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