akcs.Guest_@hpcvbbs.UUCP (Joseph K. Horn) (03/21/91)
%%HP:T(3);
@ DEC2FRAC for the HP 48SX (obsoletes ->Q)
@ Improved Decimal-to-Fraction, by Joseph K. Horn.
@
@ Faster & more complete than HP 48SX (->Q function) and HP 32SII
@ (with maximum denominator set), both of which 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.
@ This new algorithm finds the very best solution, very quickly.
@ Algorithm: Continued Fractions by fast recursion formula, then 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'
@
@ Example: What fraction is closest to the number "e", but
@ with a denominator not bigger than 20? It's 49/18.
@
@ The HP 48SX and the HP 32SII say it's 19/7. They say that the next
@ better fraction is 87/32. But there are two fractions between
@ these which are missed: 49/18 and 68/25.
@
@ Press 1 EXP 20 DEC2FRAC and see '49/18', the correct answer.
@
@ An example of speed increase is the golden ratio, (sqr(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.
@
@ Checksum = # 4F52h; Size on stack = 296.5 bytes.
@
\<< DUP2 @ Must be two arguments. Exit now if max denominator < 2, or
IF 1 > SWAP FP AND @ 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 # 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.
\>>akcs.joehorn@hpcvbbs.UUCP (Joseph K. Horn) (03/25/91)
re: DEC2FRAC by Joseph K. Horn, posted 21 March 1991. At the March 22nd meeting of the Orange/Los Angeles Counties Chapter of the HP-48 users club, Harry Bertucelli objected to my contention that DEC2FRAC finds ALL possible fractions. Harry is a professional mathematician, and accepts nothing without a formal proof. So he withdrew to a corner of the room and into a deeper corner of his mind, and in short order developed a complete proof that DEC2FRAC does in fact find all possible fractions (up to the point where the HP 48 begins to introduce round-off errors, of course). It made his day to see (and prove the validity of) a completely new algorithm in number theory. It made my day to know that the very first computer to run it was an HP 48SX. -- Joseph K. Horn -- Peripheral Vision, Ltd. --
akcs.joehorn@hpcvbbs.UUCP (Joseph K. Horn) (03/28/91)
re: DEC2FRAC by Joseph K. Horn, posted 21 March 1991. In a followup message, I said: > ... a completely new algorithm in number theory. It made my day > to know that the very first computer to run it was an HP 48SX. Well, darn it, this is only half true. It may well be that the 48 has the honors, but the algorithm IS NOT NEW. Bummer. I thought I'd discovered something new. Turns out that I was 102 years late!! In a book called _Textbook of Algebra_ by G. Chrystal, 1st edition in 1889, in Part II, Chapter 32, this improved continued fraction algorithm is presented and proven. Odd to tell, Chrystal speaks of it as if it were ancient knowledge. The original discoverer is not named, nor is the algorithm. Hmmm. Thanks to Harry Bertucelli for exhuming this obscure reference. In any case, it seems to have lay dormant for many years; it is not mentioned in modern books about number theory. It's time for us to revitalize it! An HP 48 Fraction Library could easily give us the same power over "fractional objects" that the UNITS menu gives over unit objects, plus the power of the HP 32SII's ability to handle fractions as single "objects". How would you like to be able to divide '2_hr+34_min+56.78_sec' by 4 and see '38_min+44.195_sec'? Sure, you can use the HMS-> and ->HMS functions... but why should PEOPLE do what a CALCULATOR should do for them??? An HP 48 Fraction Library should have: User-defined unit names and divisors. Lots of modes: show decimal after last unit; drop last unit remainder; round last unit; show last unit as a fraction; maximum allowable denominator; maximum allowable numerator; maximum allowable numerator AND denominator; force denomi- nator to always be n; force denominator to always be a factor of n; allow denominator to be whatever it takes to get the most accuracy; easy entry of decimal and fractional units... A few obvious applications are: yards, feet, inches (e.g. with denominator set to 16ths) days, hours, min, sec (100ths) inches, picas, points, HP PCL units (4ths) gallons, quarts, pints, cups pounds, shillings, pence, farthings (???) Everybody has their own messy fractions to deal with every day. The new thing this library will do is let you specify what YOU want. It'd make the old "postage stamp problem" trivial to solve. I just did a bulk rate mailing; 25 raffle tickets per book, two books per envelope, 10 envelopes per bundle, 20 bundles per sack. Juggling uneven sacks isn't difficult math... but I hate it! It's work that a machine should do, not a human mind, which should be concerned with things machines can't do, like what the accompanying letter should say! With a Fraction Library it'd be almost pleasant. If you have any ideas you'd like to see included in a Fraction Library like this, please post it soon, so that this doesn't become another dribbleware item. It'll be freeware, of course. Right now it's 100% vaporware, and will be available Real Soon Now. -- Joseph K. Horn -- Peripheral Vision, Ltd. --