48/49: Best Fraction Challenge

91 views
Skip to first unread message

Joseph K. Horn

unread,
Oct 11, 2003, 4:02:42 PM10/11/03
to
The "Best Fraction Challenge"
(An Extremely Difficult Challenge Disguised as a Mini-Challenge)

DEFINITION OF "BEST FRACTION": What fraction is equal to 0.5? There
are, of course, infinitely many correct answers to that question. If
we limit the answers to ratios of positive integers, there are still
infinitely many answers: 1/2, 2/4, 3/6 ... 1234/2468 ... all evaluate
to 0.5 on a calculator. But the *smallest* integers (more precisely,
the least non-negative integers), with a ratio of 0.5, are 1 and 2.
In this sense, the "best fraction" for 0.5 is 1/2.

CHALLENGE: Write a program (none such has ever been published!) that
inputs any positive decimal number, and outputs the "best fraction"
for it on the HP48 or HP49, that is, the smallest integers which, when
divided on the calculator, yield exactly the same number as the input,
in 5 seconds or less for any input, in 100% User RPL.

Hundreds of *similar* programs have been written over the years. In
fact, the ->Q function is similar. But NONE of these meet the "Best
Fraction Challenge". All of them yield some answers not exactly equal
to the input, or some answers that aren't the "best".

WARNING! I have posted this challenge here (in various forms) over the
past 13 years, and almost every time some people responded with
haughty disdain, crowing that it's a trivial and already-solved
problem... but of course, when taken to task, they all failed to post
a program that would have proved them right. If you really think that
the above is as easy as it sounds, then to save face *please* code it
up and test it on the following examples before bragging here about
how easily you could do it if you only had the time or some other
transparent excuse. Thank you.

EXAMPLES of inputs and CORRECT outputs (NOT ->Q outputs!) for the
HP48/49:

Input: 2 SIN (in RAD mode)
Output: 1029101 / 1131754

Input: 6.0030000004 (the strange number on the HP38G case)
Output: 14823406 / 2469333

Input: 0.999999999975 (the "worst case" ->Q number)
Output: 39215686274 / 39215686275

Input: 0.9498580222 (my telephone number!)
Output: 1306259 / 1375215

Input: 50000.00005
Output: 999050001 / 19981

Input: 0.500000000001
Output: 166666666668 / 333333333335

Input: 0.69999937
Output: 777777/1111111

Input: 0.903493239856
Output: 528118/584529

Of course, the program must also be able to handle ordinary inputs,
0.5 etc.

Yes, I've done it. I showed it off at HHC 2003... but I didn't give
copies of the program to anybody, for reasons to be revealed soon. If
ANYBODY can meet or beat my program, it will be of monumental
importance to me and to all users of calculator fractions.

Good luck! Happy Programming!

-Joe-
Joseph K. Horn
p...@holyjoe.us

James

unread,
Oct 11, 2003, 4:44:56 PM10/11/03
to
On Sat, 11 Oct 2003 13:02:42 -0700, Joseph K. Horn wrote:

> The "Best Fraction Challenge"
> (An Extremely Difficult Challenge Disguised as a Mini-Challenge)
>

> CHALLENGE: Write a program (none such has ever been published!) that
> inputs any positive decimal number, and outputs the "best fraction" for
> it on the HP48 or HP49, that is, the smallest integers which, when
> divided on the calculator, yield exactly the same number as the input,
> in 5 seconds or less for any input, in 100% User RPL.

Pardon my ignorance, but can't this already be accomplished using the XQ
function? I worked through some of your example problems with it, and they
seemed to be properly reduced.

James

FX-502P Geek

unread,
Oct 11, 2003, 4:52:18 PM10/11/03
to
I do not deny that the problem is very difficult - I tried it on the Casio
FX-502P back in the 80s (except I preferred the output in vulgar fractions),
but by simple inspection of your challenge you've got the wrong answer for
the 5th example. The fractional part of 50000.0005 is clearly 1/20000 and so
your correct answer should be 1000000001/20000 as given by ->Q of a HP48.
Incidentally the program that I wrote for the FX-502P is available at
www.fx502p.pwp.blueyonder.co.uk and gives the correct answer of
50000+1/20000. I would not pretend however that the program would be up to
the challenge in general. I would of course like to see your HP48 program...
especially when it is fixed.

Peter.

"Joseph K. Horn" <joe...@holyjoe.net> wrote in message
news:87233f9e.03101...@posting.google.com...

Tony Hutchins

unread,
Oct 11, 2003, 7:02:38 PM10/11/03
to
-=[ Sun, 12.10.03 11:48 a.m. +1300 (NZDT) ]=-

Hi FX-502P Geek ! <use_th...@mysite.co.uk>

01h56m ago, on Sat, 11.10.03 at 9:52 p.m. +0100, you wrote
in message ID <H0_hb.1364$ny5...@news-binary.blueyonder.co.uk> :

> I do not deny that the problem is very difficult - I
> tried it on the Casio FX-502P back in the 80s (except I
> preferred the output in vulgar fractions), but by simple
> inspection of your challenge you've got the wrong answer
> for the 5th example. The fractional part of 50000.0005
> is clearly 1/20000 and so your correct answer should be
> 1000000001/20000 as given by ->Q of a HP48.

That is thw whole point of the challenge - here is Joe's answer:

Input: 50000.00005
Output: 999050001 / 19981

And 19981 is LESS than 20000.
Joe's answer is surprisingly correct :)
Not only "better" than the 20000 denominator, but he claims it
to be the "best" - quite sensational. I can't wait to see
where his program will be published. It must be a totally new
approach.

> Incidentally the program that I wrote for the FX-502P is
> available at www.fx502p.pwp.blueyonder.co.uk and gives
> the correct answer of 50000+1/20000. I would not pretend
> however that the program would be up to the challenge in
> general. I would of course like to see your HP48 program...
> especially when it is fixed.

I suspect that it won't need fixing<G>. Although a real
counter-example would no doubt be welcomed.

- Tony

BlackLotus

unread,
Oct 11, 2003, 8:02:12 PM10/11/03
to

"Tony Hutchins" <jus...@csi.com> a écrit dans le message de
news:1078940...@news.cis.dfn.de...

> -=[ Sun, 12.10.03 11:48 a.m. +1300 (NZDT) ]=-
>
> Hi FX-502P Geek ! <use_th...@mysite.co.uk>
>
> 01h56m ago, on Sat, 11.10.03 at 9:52 p.m. +0100, you wrote
> in message ID <H0_hb.1364$ny5...@news-binary.blueyonder.co.uk> :
>
> > I do not deny that the problem is very difficult - I
> > tried it on the Casio FX-502P back in the 80s (except I
> > preferred the output in vulgar fractions), but by simple
> > inspection of your challenge you've got the wrong answer
> > for the 5th example. The fractional part of 50000.0005
> > is clearly 1/20000 and so your correct answer should be
> > 1000000001/20000 as given by ->Q of a HP48.
>
> That is thw whole point of the challenge - here is Joe's answer:
>
> Input: 50000.00005
> Output: 999050001 / 19981
>
> And 19981 is LESS than 20000.
> Joe's answer is surprisingly correct :)

It is because of a tiny approximation error. I checked it on a Math soft on
the PC, which performs "exact" calculation, and substracting the two
fractions shows an error of 19/399620000. So, no, Joe's answer's
mathmatically wrong, it's just a twist from the HP48/49 that makes it
"right" (4E-8 is neglected in regard to the number of digits and their order
in 50000.00005 as "too small to be significant")

I'm still curious as to how you achieved that, though.

BlackLotus

unread,
Oct 11, 2003, 8:44:37 PM10/11/03
to

"Joseph K. Horn" <joe...@holyjoe.net> a écrit dans le message de

news:87233f9e.03101...@posting.google.com...
> The "Best Fraction Challenge"

Here's how I'd do it, assuming I had a previous prime algorithm: (I'll call
it PP, I suppose Joe has that somewhere for the 48, but I can't find it, and
I think Erable has it in built-in for the 49)

Input: Positive integer
Output:

<< -> X
<< X ->Q OBJ-> DROP DROP SWAP DROP
'Q' STO Q 'R' STO
WHILE Q X * 0 RND Q / X ==
REPEAT Q DUP 'R' STO PP 'Q' STO
END
"'"
Q R * 0 RND + "/" + R + "'" + OBJ->
>>
>>

Needless to say (and as I stated in another post), this should give (I can't
test it) the best fraction that will return a correct result in the HP48/49
(and I insist, it only works because of how the ints are in the HP48/49)

BlackLotus

unread,
Oct 11, 2003, 8:46:02 PM10/11/03
to
Oops. I forgot a bit. xD

Output: Fraction


Tony Hutchins

unread,
Oct 11, 2003, 8:50:51 PM10/11/03
to
-=[ Sun, 12.10.03 1:36 p.m. +1300 (NZDT) ]=-

Hi BlackLotus ! <black...@nospam.me>

34m ago, on Sun, 12.10.03 at 02:02 a.m. +0200, you wrote
in message ID <bma5m5$76e$1...@news-reader4.wanadoo.fr> :

news client =Microsoft Outlook Express 6.00.2800.1158
previous messages in thread =3 + 1 for your message
tot ref chars=133
chars per id =44.3333333333333
Top Thread id=<87233f9e.03101...@posting.google.com>
Organisation =Wanadoo, l'internet avec France Telecom

--
Tony Hutchins
Wellington
New Zealand

#113 Fate often saves a warrior when his courage
endures. Beowolf

Joseph K. Horn

unread,
Oct 11, 2003, 10:47:06 PM10/11/03
to
James wrote:

> Pardon my ignorance, but can't this already be
> accomplished using the XQ function?

No. XQ has the same faults as ->Q, namely, it gets answers that are
either (a) not the best, (b) not equal to the input, or (c) both of
the above.

> I worked through some of your example problems
> with it, and they seemed to be properly reduced.

Umm... No. Look again. XQ gets horribly wrong answers for all of
the examples except 50000.00005 which it can't even handle ("XQ Error:
Overflow"!!!). Compare the answers you get with the answers that I
listed with each example. None match, and some are WAY off. ->Q is
better than XQ, but even that fails to get the right answer to ANY of
my examples.

Peter wrote:

> ... by simple inspection of your challenge you've


> got the wrong answer for the 5th example. The
> fractional part of 50000.0005 is clearly 1/20000
> and so your correct answer should be
> 1000000001/20000 as given by ->Q of a HP48.

Ummm... No. Look again. I want the BEST FRACTION (not the obvious
one), with BEST FRACTION being defined as "the ratio of the smallest
two integers which, when divided ON AN HP48 or HP49, yield exactly the
input."

Yes, 50000.00005 can be represented by 1000000001/20000, but please
look closer at the answer I gave. It has a SMALLER numerator and
denominator, AND it evaluates to the same thing as the input ON AN
HP48 or HP49. Therefore it is a "better" answer. And since there are
no smaller integers that work, it's the "best fraction" for the input.

Recap:

1000000001 / 20000 = 50000.00005 on an HP48/49, but
999050001 / 19981 = 50000.00005 on an HP48/49 too.
So the latter is better.
Nothing is better than it, so it's the best fraction.

> Incidentally the program that I wrote for the FX-502P
> is available at www.fx502p.pwp.blueyonder.co.uk and
> gives the correct answer of 50000+1/20000.

The "correct" answer depends on the machine, just like "the correct
sine of 2" depends on the machine. If you tell me how many digits the
FX-502P calculates with, and whether it truncates or rounds the last
digit, then I can tell you what it should return for the examples.

BRIEF VERSION OF THE CHALLENGE: I have a decimal fraction. I want to
divide two integers ON AN HP48 or HP49 and get EXACTLY that decimal
fraction. What are the SMALLEST two integers that'll work?

> I would of course like to see your HP48 program...
> especially when it is fixed.

It is working perfectly... unlike any other "decimal to fraction"
program or function that I know of. It'll be posted here after this
challenge has had enough time to simmer.

HOMEWORK: What is the BEST fraction for sqrt(LOG(2)) on an HP48 or
HP49?

-Joe-

Virgil

unread,
Oct 12, 2003, 12:22:00 AM10/12/03
to
In article <87233f9e.03101...@posting.google.com>,

joe...@holyjoe.net (Joseph K. Horn) wrote:


>
> HOMEWORK: What is the BEST fraction for sqrt(LOG(2)) on an HP48 or
> HP49?
>
> -Joe-

For LOG, base 10, I get 998995/1820784, which works but may not be
best.

For LN, base e, I get 462042/554969, which also works, but may not
be best.

James

unread,
Oct 12, 2003, 1:56:26 AM10/12/03
to
On Sat, 11 Oct 2003 19:47:06 -0700, Joseph K. Horn wrote:

> HOMEWORK: What is the BEST fraction for sqrt(LOG(2)) on an HP48 or
> HP49?
>
> -Joe-

On my 49g+, using XQ: 29422/53625

Tony Hutchins

unread,
Oct 12, 2003, 5:45:41 AM10/12/03
to
-=[ Sun, 12.10.03 10:36 p.m. +1300 (NZDT) ]=-

Hi Virgil ! <vmh...@comcast.net>

05h14m ago, on Sat, 11.10.03 at 10:22 p.m. -0600, you wrote
in message ID <vmhjr2-016FFC....@news.newsguy.com> :

> For LOG, base 10, I get 998995/1820784, which works but
> may not be best.

FWIW that gets my vote as well. I haven't a clue how to get
there is less than 5 seconds though. The continued fraction
method leapfrogs way over that.

--
Tony Hutchins
New Zealand

#71 All computers wait at the same speed.

Eddy Hondo

unread,
Oct 12, 2003, 1:06:03 PM10/12/03
to
Hi>

joe...@holyjoe.net (Joseph K. Horn) wrote in message news:<87233f9e.03101...@posting.google.com>...
> James wrote:

>
> The "correct" answer depends on the machine, just like "the correct
> sine of 2" depends on the machine. If you tell me how many digits the
> FX-502P calculates with, and whether it truncates or rounds the last
> digit, then I can tell you what it should return for the examples.


How many digits does the 49g calculate with?? Does it truncate or
round the last digit??

Need that for a shot at the program. TY

Joseph K. Horn

unread,
Oct 12, 2003, 2:53:46 PM10/12/03
to
Virgil wrote:

>> HOMEWORK: What is the BEST fraction for
>> sqrt(LOG(2)) on an HP48 or HP49?
>

> For LOG, base 10, I get 998995/1820784,
> which works but may not be best.
>
> For LN, base e, I get 462042/554969,
> which also works, but may not be best.

Congrats! You got the best fractions for both cases!

PUH-LEEEEEZE tell me how you did it! Did you use an HP48 or 49? How
long did it take? I'm dying to know!!!

For what it's worth, my program converts sqrt(LOG(2)) into
998995/1820784 in 0.745 seconds on an hp49g+, and runs unmodified on
an HP48GX.

-Joe-

FX-502P Geek

unread,
Oct 12, 2003, 3:02:24 PM10/12/03
to

"Joseph K. Horn" <joe...@holyjoe.net> wrote in message
news:87233f9e.03101...@posting.google.com...

OK Joseph I see what mean, although I'm not sure that it is useful. I
suspect that the System RPL of '->Q' calculates errors on the at a higher
accuracy than is returned to the user and so the denominator is closer to
the true answer of the input number. Your answer is also valid for your
interpretation on the FX-502P which also returns exactly 50000.00005 for
999050001/19981.

>
> > Incidentally the program that I wrote for the FX-502P
> > is available at www.fx502p.pwp.blueyonder.co.uk and
> > gives the correct answer of 50000+1/20000.
>
> The "correct" answer depends on the machine, just like "the correct
> sine of 2" depends on the machine. If you tell me how many digits the
> FX-502P calculates with, and whether it truncates or rounds the last
> digit, then I can tell you what it should return for the examples.

This is not straight forward. The FX-502P works to 12 places (but truncates
to 10 if you put a value in a memory!). It truncates to 12 places... unless
the last 2 digits are greater than 49 and the 8th, 9th & 10th digits are 999
in which case it rounds up the 9s to carry forward into the 7th digit. This
rather dubious logic prevents decimal errors leading to .99999... when the
next integer is the correct answer.


>
> BRIEF VERSION OF THE CHALLENGE: I have a decimal fraction. I want to
> divide two integers ON AN HP48 or HP49 and get EXACTLY that decimal
> fraction. What are the SMALLEST two integers that'll work?
>
> > I would of course like to see your HP48 program...
> > especially when it is fixed.
>
> It is working perfectly... unlike any other "decimal to fraction"
> program or function that I know of. It'll be posted here after this
> challenge has had enough time to simmer.

I look forward to it.

Joseph K. Horn

unread,
Oct 12, 2003, 3:20:18 PM10/12/03
to
James wrote:

>> What is the BEST fraction for sqrt(LOG(2))

> On my 49g+, using XQ: 29422/53625

Close, but no cigar. 29422/53625 is not EQUAL to sqrt(LOG(2)) on the
HP48/49. The challenge, as clearly stated, requires that the fraction
evaluate to EXACTLY the same number as the input. Using your
solution, the input and output are, respectively:

.548662004939
.548662004662 (compare last three digits)

Even being off by 1 digit in the last place invalidates a solution;
this answer is off by 277 digits in the last place. Not acceptable.

XQ answers a diferent question than my challenge. XQ is meant for the
removal of "noise" in numbers that are known to be clean ratios. For
example, suppose you see a reference in a book to "0.8947368421" and
the context makes it clear that they're talking about some kind of
ratio of reasonably small integers. They obviously rounded it off to
10 digits, but HP uses 12 digits, so applying ->Q to that decimal
yields a ratio of two huge integers... clearly not what we're looking
for. Applying XQ yields the nice answer of 17/19.

WHICH ANSWER IS "RIGHT" DEPENDS ON THE QUESTION.

If the question is instead, "What are the smallest two integers which
divide on the HP48 or HP49 to get a result of exactly 0.8947368421?"
then the best answer is neither what ->Q yields nor what XQ yields,
but is instead 8171112721/9132420100 (obtained on my hp49g+ in 1.12
seconds).

-Joe-
"It is difficult to answer when one does not understand the question."
-- Sarek (Star Trek IV)

BlackLotus

unread,
Oct 12, 2003, 3:26:27 PM10/12/03
to
Ok, I tested it since yesterday, and it appears it's useless.

I searched for other solutions, and it puzzles me how you can do that in
less than 5 seconds. Here's why:
Bruteforcing my way down a big problem: it can take a lot of time if ->Q
gives a wrong result (one that once ->NUMed is different from the input).
sqrt(ln(2)) is a good example. Another problem is a stopping condition, if I
start from a valid ->Q result, I can tell it to keep lowering Q until it
reaches a Q that makes Q X * 0 RND Q / different from X
A less calculating method seems to be, starting from the "right" fraction
(not the best):
Let's call the fraction Q/D (not best) and Qb/Db (best).
If you divide Q by d from D going down, the stop point is the result which
has the lowest number of digits, while still having RND(d*X)/d == X As you
can guess, the problem is to have Q and D to start with, since ->Q can gives
wrong results, and so does a continuous fraction method (tried it, it fails
because of the approximation, I might retry it with different parameters
than the one I found (it was a VB algorithm) to see if I can adjust it to
the HP's precision).
In both cases, what really kills me is how to find a starting point that's
close enough and/or a method to converge faster to a solution.


"BlackLotus" <black...@nospam.me> a écrit dans le message de
news:bma85n$rgf$1...@news-reader2.wanadoo.fr...

Rafael Mill?n

unread,
Oct 12, 2003, 3:34:41 PM10/12/03
to
"BlackLotus" <black...@nospam.me> wrote in message news:<bma5m5$76e$1...@news-reader4.wanadoo.fr>...

> It is because of a tiny approximation error. I checked it on a Math soft on
> the PC, which performs "exact" calculation, and substracting the two
> fractions shows an error of 19/399620000. So, no, Joe's answer's
> mathmatically wrong, it's just a twist from the HP48/49 that makes it
> "right" (4E-8 is neglected in regard to the number of digits and their order
> in 50000.00005 as "too small to be significant")

The 49 CAS itself (in exact mode) will do:

'1000000001/20000 - 999050001/19981' EVAL
'-19/399620000'

But the challenge does not ask for a mathematically exact result, but
an exact result when the fraction is approximated to a 48 or 49 real.

RaM.

Virgil

unread,
Oct 12, 2003, 3:10:15 PM10/12/03
to
In article <pan.2003.10.12....@ham.org>,
James <nos...@ham.org> wrote:

On my 49, in approximate mode,

'SQRT(LOG(2,)' evaluates to .548662004939
but
'29422/53625' evaluates to .548662004662.

Virgil

unread,
Oct 12, 2003, 3:42:40 PM10/12/03
to
In article <87233f9e.0310...@posting.google.com>,

joe...@holyjoe.net (Joseph K. Horn) wrote:

> Virgil wrote:
>
> >> HOMEWORK: What is the BEST fraction for
> >> sqrt(LOG(2)) on an HP48 or HP49?
> >
> > For LOG, base 10, I get 998995/1820784,
> > which works but may not be best.
> >
> > For LN, base e, I get 462042/554969,
> > which also works, but may not be best.
>
> Congrats! You got the best fractions for both cases!
>
> PUH-LEEEEEZE tell me how you did it! Did you use an HP48 or 49? How
> long did it take? I'm dying to know!!!

I used a very primitive and very slow method based on Farey
fractions. as outlined below.

Let x be the decimal number to be aproximated, and assume it is not
already an integer.
Find integers n1 < x and n2 > x, and start with fractions n1/d1 and
n2/d2 where d1 = d2 = 1.

Then decrease the interval by taking n/d in place of the appropriate
endpoint, where n = n1 + n2 and d = d1 + d2.

Eventually, but very slowly, n/d gives the correct decimal on the
49, at least for all the decimals I have tried. I also did several
tests using reals for which XQ gives the wrong values without
getting any wrong answers.

A variant on continued fractions should give the same results in
considerably less time, but I haven't got the bugs worked out of it
yet.

>
> For what it's worth, my program converts sqrt(LOG(2)) into
> 998995/1820784 in 0.745 seconds on an hp49g+, and runs unmodified on
> an HP48GX.
>
> -Joe-

My program on my 49 takes about 53 seconds for the same result.

BlackLotus

unread,
Oct 12, 2003, 5:15:58 PM10/12/03
to

"Virgil" <vmh...@comcast.net> a écrit dans le message de
news:vmhjr2-C09590....@news.newsguy.com...

> I used a very primitive and very slow method based on Farey
> fractions. as outlined below.
>
> Let x be the decimal number to be aproximated, and assume it is not
> already an integer.
> Find integers n1 < x and n2 > x, and start with fractions n1/d1 and
> n2/d2 where d1 = d2 = 1.
>
> Then decrease the interval by taking n/d in place of the appropriate
> endpoint, where n = n1 + n2 and d = d1 + d2.
>
> Eventually, but very slowly, n/d gives the correct decimal on the
> 49, at least for all the decimals I have tried. I also did several
> tests using reals for which XQ gives the wrong values without
> getting any wrong answers.
>
> A variant on continued fractions should give the same results in
> considerably less time, but I haven't got the bugs worked out of it
> yet.
>

Thank you so much. I finally managed to get something that works.
I thought about that problem all day long, and I never came to think about
that. Maybe I should have taken maths and not economics. :p

> My program on my 49 takes about 53 seconds for the same result.

It takes less than 3 seconds on my HP48 using the method you described; my
program takes 357 bytes.


Joseph K. Horn

unread,
Oct 13, 2003, 1:46:06 AM10/13/03
to
Eddy Hondo wrote:

> How many digits does the 49g calculate with??
> Does it truncate or round the last digit??

User RPL calculates internally with a truncated 15-digit mantissa,
then rounds that down to 12 digits and returns that to the user as the
final answer.

-Joe-

Sam Hughes

unread,
Oct 13, 2003, 7:17:05 AM10/13/03
to
James <nos...@ham.org> wrote in message news:<pan.2003.10.11....@ham.org>...

Try it with one of his examples...

0.69999937 XQ produces '111106/158723'. Then pressing ->NUM produces
the decimal .699999369972, which means that XQ's result is not the
best possible fraction. The best fraction, of course, is
'777777/1111111'.

reth

unread,
Oct 13, 2003, 8:37:12 AM10/13/03
to
what about 3.14159265359?


Veli-Pekka Nousiainen

unread,
Oct 13, 2003, 8:54:13 AM10/13/03
to
"reth" <re...@nospan.com.at> wrote in message
news:3f8a9c77$1...@dnews.tpgi.com.au...
> what about 3.14159265359?
pi is a special case.
It is taken into consideration as a 15-nibble version internally
and the 12 number version si actually 13 digits precise:
3.14159265358979
15 => round to 13
3.141592653590
BUT what is the answer, Joe?
VPN


BlackLotus

unread,
Oct 13, 2003, 11:49:13 AM10/13/03
to

"reth" <re...@nospan.com.at> a écrit dans le message de

news:3f8a9c77$1...@dnews.tpgi.com.au...
> what about 3.14159265359?
>
1146408/364913

>


Tony Hutchins

unread,
Oct 13, 2003, 12:21:29 PM10/13/03
to
-=[ Tue, 14.10.03 04:50 a.m. +1300 (NZDT) ]=-

Hi reth ! <re...@nospan.com.at>

03h13m ago, on Mon, 13.10.03 at 10:37 p.m. +1000, you wrote
in message ID <3f8a9c77$1...@dnews.tpgi.com.au> :

> what about 3.14159265359?

I the ->Q answer for that (1146408/364913) satisfies the
challenge.

Like others, I lost a few hours yesterday, but the challenge
did come with a warning<G>. My result works well on most
examples, but fails *miserably* on .50000000001 and also the
HP38G number. I start with a continued fraction method and so
lose the last "1" as .500000000001 1/X 1/X = .5 only :(
Maybe I need a MANT somewhere. But, where?<G>. I look forward
to seeing Joe's code :)



--
Tony Hutchins
New Zealand

#2 Save whales - collect the whole set.

BlackLotus

unread,
Oct 13, 2003, 1:37:47 PM10/13/03
to
I have a question here, because I lack the mathematical knowledge to solve a
part of the problem.

I tried Virgil's method, and it seemed to work fine until I tried a number
like 50000.00005. There it kind of killed my hopes, because it takes
horribly long to get the answer. I looked a little, and it seems it chockes
on the limit cases such as 0.001 (it requires 999 iterations), especially
when it uses all the digits and a lot of them are similar. I think my
iterations can go up to (1/X)-1 (or 1/(1-X)-1), which means close 1E11
iterations to reach a result for 0.999999999975. Way too long.
I spent a good while trying to figure how to get the solution with as little
iterations as possible, and while some CF algorithms looked nice, they often
return the exact result, not the best result. I tried changing the way the
interval is shrunk, but it doesn't cut much time.
I looked deeper and tried to find what is special with the result we want,
and I found a few things.
First, if X is my number, and Q/D the fraction I'm looking for, then it
appears that D*X <> Q, but Q/X = D, due to rounding. We know X, we'll search
Q, then. Also, the Q/X we're looking for has to particualrity of being an
integer, which means that CEIL(Q/X)=FLOOR(Q/X)=IP(Q/X)=Q/X. How does that
help? Well, the Q that we're looking for is the smallest Q so that
IP(Q)/CEIL(Q/X)=X (or FLOOR(Q/X)/CEIL(Q/X)=1, with Q an integer. The problem
is, the 48's built-in solver stops on extremums or sign changes, or leaps
over the solution.
So, you guessed it, my problem is to find the solution to that fairly simple
equation, given that the built-in solver chokes (not to say "is useless"),
and that derivation won't work. So, the possibilities I see are these:
Either I can find a solving algorithm and chances are it will go faster than
the convergence I used so far, or I can find a derivable mathematical
formula that says exactly the same as my IP(Q)/CEIL(Q/X)-X=0, except without
IP and CEIL, since the HP won't derivate them.
I don't know if they're the way Joe chose (I doubt it, I usually find the
most complicated solution to a problem), but I'd like to explore it, and I
don't have the knowledge to solve that equation. I figured it could be
interesting, since ideally, finding a solution would take pretty much the
same time regardless of the starting value.


Joseph K. Horn

unread,
Oct 13, 2003, 2:29:28 PM10/13/03
to
"reth" wrote:

> what about 3.14159265359?

The best fraction for pi on an HP 12-digit calculator is what ->Q
returns for it in STD mode: 1146408/364913.

Same is true for pi^e, which for all I know is a rational number,
though I doubt it.

-Joe-

Tony Hutchins

unread,
Oct 13, 2003, 2:33:30 PM10/13/03
to
-=[ Tue, 14.10.03 07:13 a.m. +1300 (NZDT) ]=-

Hi BlackLotus ! <black...@nospam.me>

35m ago, on Mon, 13.10.03 at 7:37 p.m. +0200, you wrote
in message ID <bmentb$84o$1...@news-reader5.wanadoo.fr> :

> I have a question here, because I lack the mathematical
> knowledge to solve a part of the problem.

I lack the knowledge of how to differentiate those "IP"
functions as well - you have step functions there. Possibly
there is no classical way to handle them.

> I tried Virgil's method, and it seemed to work fine until
> I tried a number like 50000.00005. There it kind of killed
> my hopes, because it takes horribly long to get the answer.

The CF algorithm really helps on that one - it gives the 20000
denominator instantly. AFAIK the only way to test if smaller
denominators work is to decrement the 20000 by 1 until it
doesn't work. It doesn't take long. I suspect some process
like this is what makes Joe's algorithm sometimes take 5
seconds, instead of under 1 second.

> I looked a little, and it seems it chockes on the limit cases
> such as 0.001 (it requires 999 iterations), especially when
> it uses all the digits and a lot of them are similar. I
> think my iterations can go up to (1/X)-1 (or 1/(1-X)-1),
> which means close 1E11 iterations to reach a result for
> 0.999999999975. Way too long. I spent a good while trying
> to figure how to get the solution with as little iterations
> as possible, and while some CF algorithms looked nice, they
> often return the exact result, not the best result.

But CF is great to get near the best answer - I think
successive results always bound the answer. The trick is not to
let the CF go too far. A good place to stop is when
Denominator*X=Numerator, which often happens before the exact
result.
[...]

BlackLotus

unread,
Oct 13, 2003, 3:01:33 PM10/13/03
to

"Tony Hutchins" <jus...@csi.com> a écrit dans le message de
news:1049541...@news.cis.dfn.de...

> -=[ Tue, 14.10.03 07:13 a.m. +1300 (NZDT) ]=-
>
> The CF algorithm really helps on that one - it gives the 20000
> denominator instantly. AFAIK the only way to test if smaller
> denominators work is to decrement the 20000 by 1 until it
> doesn't work. It doesn't take long. I suspect some process
> like this is what makes Joe's algorithm sometimes take 5
> seconds, instead of under 1 second.
>
But for example, on sqrt(log(2)), the CF algorithm I still have returns
418507862138/762779012161, which is far from the best solution (and lower
than the exact solution), and going your way down from here is going to take
long. On the same idea, I realized that sometimes the exact fraction and the
best fraction are such that there's a set of values where the fraction is
true, then a set of value where it's false (I used that as a stopping
condition in the first try I made) and then back to a set where it's true
again like with sqrt(log(2)).

Virgil

unread,
Oct 13, 2003, 2:53:13 PM10/13/03
to
In article <3f8a9c77$1...@dnews.tpgi.com.au>,
"reth" <re...@nospan.com.at> wrote:

> what about 3.14159265359?
>
>

1146408/364913?

Tony Hutchins

unread,
Oct 13, 2003, 3:45:47 PM10/13/03
to
-=[ Tue, 14.10.03 08:31 a.m. +1300 (NZDT) ]=-

Hi BlackLotus ! <black...@nospam.me>

29m ago, on Mon, 13.10.03 at 9:01 p.m. +0200, you wrote
in message ID <bmesqe$846$1...@news-reader1.wanadoo.fr> :

> But for example, on sqrt(log(2)), the CF algorithm I still have returns
> 418507862138/762779012161,

Calling that N/D, and the target X, I stop CF when I have D*X=N
This happens when D=470069 I think. This really helps in most
of the examples, but not all ... so it is not the "key" by any
means<G>

FX-502P Geek

unread,
Oct 13, 2003, 4:12:47 PM10/13/03
to
"reth" <re...@nospan.com.at> wrote in message
news:3f8a9c77$1...@dnews.tpgi.com.au...
> what about 3.14159265359?
>
>

The FX-502P actually has it built in pi wrong at 3.14159265358 i.e.
truncated to 12 places rather than rounded to 3.14159265359. Casio even got
it successor the FX-602P wrong with 3.14159265360!

Peter.

BlackLotus

unread,
Oct 13, 2003, 4:22:37 PM10/13/03
to

"Tony Hutchins" <jus...@csi.com> a écrit dans le message de
news:1057436...@news.cis.dfn.de...

> -=[ Tue, 14.10.03 08:31 a.m. +1300 (NZDT) ]=-
>
> Calling that N/D, and the target X, I stop CF when I have D*X=N
> This happens when D=470069 I think. This really helps in most
> of the examples, but not all ... so it is not the "key" by any
> means<G>
Just for the record, 470069*sqrt(log(2)) is an integer (257909), but
257909/470069 is different (by 1E-12, the last digit) from sqrt(log(2)).

And I know it's not the perfect solution, which puzzles me as how Joe did
it.

Tony Hutchins

unread,
Oct 13, 2003, 5:22:26 PM10/13/03
to
-=[ Tue, 14.10.03 09:43 a.m. +1300 (NZDT) ]=-

Hi BlackLotus ! <black...@nospam.me>

21m ago, on Mon, 13.10.03 at 10:22 p.m. +0200, you wrote
in message ID <bmf1ie$ovm$1...@news-reader4.wanadoo.fr> :

> Just for the record, 470069*sqrt(log(2)) is an integer (257909), but
> 257909/470069 is different (by 1E-12, the last digit) from sqrt(log(2)).

Yup the CF method is pretty good at getting close, quickly.
What eludes me is a general rule :(

I tried lots of variations hoping that one would suddenly work
for all examples, and then I could see if I could understand
it by general reasoning, after playing about. I learned to
program quickly, and it was fun - I like working with the
49g+. It seems I was lucky there as my keyboard is fine. No
keys stand out as non-functional, and I don't use a hammer<G>.

> And I know it's not the perfect solution, which puzzles me
> as how Joe did it.

It will be very interesting to see the answer-the logic, and
the implementation.

I can't even do that example of .5 + E-12 - I keep losing the
E-12 <G>... and CF jumps to D=250,000,000,001 on the second
term!! If I divide that by 15 I get close. I almost have a
different program for each example<G>. I reckon if I could see
how to do that one ... I might see how to find 2 denominators
D1,D2 such that I know the answer is D1,D2 or something bigger
like D1+D2. Then if an answer is found it always needs
checking in case there is a lower equivalent, separated by
1,2,3 etc. Also I may be totally wrong about everything <G>.
What we need is probably a number theory expert. But it sounds
like Joe himself has broken new ground here!

Joseph K. Horn

unread,
Oct 13, 2003, 7:16:05 PM10/13/03
to
Tony Hutchins wrote:

> ... AFAIK the only way to test if smaller


> denominators work is to decrement the 20000
> by 1 until it doesn't work. It doesn't take
> long. I suspect some process like this is
> what makes Joe's algorithm sometimes take 5
> seconds, instead of under 1 second.

You're hot on the trail, but FYI I'm pretty sure that the slowest
input for my program is the "worst case" number 0.999999999975, which
takes 1.25 seconds (on a 49g+).

> But CF is great to get near the best answer -
> I think successive results always bound the
> answer. The trick is not to let the CF go too
> far.

That's one of the charms of my program: it never introduces ANY
roundoff error at any point, not even with 1/x. It is partly based on
continued fractions, but it does NOT use FP(1/x) [like everybody else
does] because that loses information at every iteration. My method
loses NO information, and in fact marches inexorably towards the best
fraction every time, with at most a handful of iterations, even with
inputs that are pure evil, such as the ones with large partial
quotients such as .500000000001, whose continued fraction expansion is
exactly [0; 1, 1, 249999999999, 2].

MASSIVE HINT: Write a program that converts any input number to its
*exact* continued fraction expansion, and vice versa. From there to
the solution to this Best Fraction Challenge is just a hop, skip and a
jump. Literally.

In case it helps, here are the *EXACT* continued fraction expansions
of the examples that have appeared in this thread so far. Instead of
the usual notation [integer part; partial quotient, pq, pq, ...], I'll
just show 'em in a list, HP style. Remember, the operative word here
is EXACT! For example, pi is not exactly equal to
314159265359/100000000000, but HP's version of pi *is* exactly equal
to that, mathematically. Let's call it "HP pi".

HP 2 SIN (in RAD mode) =
{ 0 1 10 39 1 12 1 2 1 45 1 25 1 22 14 1 1 24 }

6.0030000004 =
{ 6 333 3 2499 1 2 333 }

0.999999999975 =
( 0 1 3999999999 }

0.9498580222 =
{ 0 1 18 1 16 1 1 1 12 1 3 24 3 6 5 1 14 2 }

50000.00005 =
{ 50000 20000 }

0.500000000001 =
{ 0 1 1 249999999999 2 }

0.69999937 =
{ 0 1 2 3 15872 1 2 1 1 12 3 2 }

0.903493239856 =
{ 0 1 9 2 1 3 4 1 2 6 1 5 1 6 7 1 11 15 18 4 }

HP sqrt(LOG(2)) = 0.548662004939 =
{ 0 1 1 4 1 1 1 3 7 7 9 1 6 1 5 1 1 2 3 10 2 20 1 7 2 2 }

HP sqrt(LN(2)) = 0.832554611158 =
{ 0 1 4 1 34 1 5 6 3 1 1 9 6 1 14 1 6 1 1 178 1 2 }

0.8947368421 (almost 17/19) =
{ 0 1 8 2 526315789 }

17/19 (*not* HP 17/19, but the real thing) =
{0 1 8 2 }

HP pi =
{ 3 7 15 1 292 1 1 1 2 1 4 1 1 1 1 1 3 1 68 2 4 2 }

HP pi^e = 22.4591577184 =
{ 22 2 5 1 1 1 1 1 3 2 1 1 3 8 1 8 1 11 1 3 4 2 }

-Joe-

Tony Hutchins

unread,
Oct 13, 2003, 9:17:37 PM10/13/03
to
-=[ Tue, 14.10.03 1:11 p.m. +1300 (NZDT) ]=-

Hi Joseph K. Horn ! <joe...@holyjoe.net>

55m ago, on Mon, 13.10.03 at 4:16 p.m. -0700, you wrote
in message ID <87233f9e.03101...@posting.google.com> :
[...]


> even with inputs that are pure evil, such as the ones
> with large partial quotients such as .500000000001,
> whose continued fraction expansion is exactly [0; 1, 1,
> 249999999999, 2].

I get [0; 1,2], which converts back to .666', so indeed it is
pure evil, evil extended <G>.[1]

Many many thanks for your tips Joe! I see the problem I now
have to deal with. I seem to have to do reciprocals - I can
see how to recover lost digits (DUP 1/x 1/x - for example),
but I can't see what to do with them yet - especially with the
above example I want a reciprocal of the .500000000001 that is
at least under 2. A nice puzzle - how to adjust a reciprocal.

> MASSIVE HINT: Write a program that converts any input number
> to its *exact* continued fraction expansion, and vice versa.
> From there to the solution to this Best Fraction Challenge
> is just a hop, skip and a jump. Literally.

MANY THANKS!!!!

Literally? I can't find these hop,skip & jump functions in user
RPL <G>

That should keep me on the straight and narrow over the next
month ;-)

Today, for the first time, I really followed the continued
fraction notation - in the past all those divisions made me
dizzy <G>

I already tried to reverse the process but failed there too -
with the evil one above - going backwards in RPN style from
the end of the fraction, I lost significance at the first
+ below:
2 1/x 249999999999 + 1/x 1 + 1/x 1 + 1/x 0 +

... and I just end up with .5 again. Still that's better than
.666<G>[1]. Once I crack this I'll be on the way, I hope.

So, I have to find a way to avoid reciprocals - but this looks
rather tricky, given the usual simple continued fraction
notation :)

No, no, I just need accurate reciprocals.
Or somehow turn everything on its head.



> In case it helps, here are the *EXACT* continued fraction expansions
> of the examples that have appeared in this thread so far.

[...]

Thanks for the detailed notation and description - I can now
follow what you mean!

I'll be working on this on the train and hope to soon see the
49g+ march ineluctably to the correct answers - after I figure
out the hop and the skip and the jump :) I can almost imagine
I will have to hop to the right denominator interval, and
maybe skip to one end and jump about a bit in the interval -
*that* part I have been doing already<G>.

This is a terrific challenge - although I consider it
recreational I feel it also might have uses in computer
science - hope it does!

[1] Oops I see I made a mistake above - for the .500000000001 I
get [0;2], not [0;1,2] which converts back to .5, not .666'. Unintentional.
I was learning the notation as I wrote.

--
Tony Hutchins
Wellington
New Zealand

#248 I praise loudly; I blame softly. Queen
Catherine II

Tony Hutchins

unread,
Oct 14, 2003, 5:30:58 AM10/14/03
to
-=[ Tue, 14.10.03 9:32 p.m. +1300 (NZDT) ]=-

Hi Joseph K. Horn ! <joe...@holyjoe.net>

09h16m ago, on Mon, 13.10.03 at 4:16 p.m. -0700, you wrote
in message ID <87233f9e.03101...@posting.google.com> :
[...]

Joe, me again. I made progress :)

> inputs that are pure evil, such as the ones with large partial
> quotients such as .500000000001, whose continued fraction expansion is
> exactly [0; 1, 1, 249999999999, 2].

I can do this now. Took me a while to un-confuse myself<G>

> MASSIVE HINT: Write a program that converts any input number to its
> *exact* continued fraction expansion, and vice versa. From there to
> the solution to this Best Fraction Challenge is just a hop, skip and a
> jump. Literally.

I seem to have a problem doing the reverse - getting back to
the exact number..see below

[...]


> For example, pi is not exactly equal to
> 314159265359/100000000000,

*That* is what gave me the clue to doing the expansion - I
don't start with .500000000001 but that*E12 /E12 - I start
with an integral numerator and a denominator. Thanks for that
hidden tip!!

Than I saw a worked example of old Euclid's algorithm for GCD
and that gave me another hint. This is stuff I never studied
at school.

[...]

The problem:
Input: 0.500000000001
Output: 166666666668 / 333333333335

The expansion in partial quotients:

[0; 1, 1, 249999999999, 2].

a0 a1,a2, a3 , a4 (notation)

To reverse the process I assume I calculate successive
"convergents":p1/q1,p2/q2,p3/q3 and p4/q4.

I thought p4/q4 would give me the original .500000000001

p0=a0=0 p(-1)=1 q0=1 q(-1)=0
p1=a1*p0+p(-1)=1*0+1 =1
q1=a1*q0+q(-1)=1*1+0 =1 p1/q1=1/1=1

p2=a2*p1+p0=1*1+0 =1
q2=a2*q1+q0=1*1+1 =2 p2/q2=1/2=.5

p3=a3*p2+p1=249999999999*1+1 =250000000000
q3=a3*q2+q1=249999999999*2+1 =499999999998
Oh!!! I see the error!! q3 sb=499999999999
p3/q3=.500000000001

Yeah!

p4=a4*p3+p2=2*250000000000+1 =500000000001
q4=a4*q3+q2=2*499999999999+2 =E12
p4/q4=.500000000001 - exactly.

OK, I think I can now do the reversal.

I seem to be stumped as to how to "hop, skip and jump" to
near the 33333333335 denominator.

Is there a different way to do the convergents?
Maybe backwards?

You can tell I haven't the foggiest idea how to be sure I am
homing in on the Best Fraction for the HP48/49. For all I know
it could be lurking almost anyware<G>.

However I do have p3/q3. So I must check backwards with
smaller denominators until I find the earliest example where
the "p/q" equals our value, on the HP48/49.

Ahha .. maybe it is as I once suspected that there is a whole
series of *consecutive* results that give the answer. So,
maybe I:

1. hop to the first endpoint that gives the answer.
2. That means the previous convergent doesn't give the
answer<G>. So I just skip to the denominator in the middle,
and check that out.
3. This way I establish a new interval to look in, and I jump
to that one :)

Yup, successive bisection - might be a general method.

Joe, in writing this I think I found my way! I started to
write because I was stumped.

I'm still a bit worried that somehow an earlier value may
exist - but although the results go up and down in a sawtooth
like way, overall they are probably well-behaved.

Thanks so much for the tips!!!!!

--
Tony Hutchins
Wellington
New Zealand

#77 Allen's Axiom: When all else fails, follow instructions.

Sam Hughes

unread,
Oct 14, 2003, 5:15:53 PM10/14/03
to
In article <87233f9e.0310...@posting.google.com>, Joseph K.
Horn says...

> For what it's worth, my program converts sqrt(LOG(2)) into
> 998995/1820784 in 0.745 seconds on an hp49g+, and runs unmodified on
> an HP48GX.

How long does it take to run on a 48GX, or on a 49G?

Joseph K. Horn

unread,
Oct 14, 2003, 7:08:42 PM10/14/03
to
Tony Hutchins wrote:

> > For example, pi is not exactly equal to
> > 314159265359/100000000000,
>
> *That* is what gave me the clue to doing
> the expansion - I don't start with .500000000001
> but that*E12 /E12 - I start with an integral
> numerator and a denominator. Thanks for that
> hidden tip!!

That's the trick for avoiding the 1/FP(x) roundoff errors that have
plagued decimal-to-fraction algorithms forever.

"You have taken your first steps into a larger world."
-- Obi-Wan Kenobi

> I seem to be stumped as to how to "hop, skip
> and jump" to near the 33333333335 denominator.

MASSIVE HINT (spoiler, actually) #2: With the list of partial
quotients handy, examine the *differences* between successive
intermediate convergents' numerators. Now do the same for their
denominators. When the pattern hits you, it'll hit you hard, so be
sure to be sitting down!

> Yup, successive bisection - might be a general method.

Put that together with the previous paragraph, and you have my
program, sans bells & whistles.

> although the results go up and down in a sawtooth
> like way, overall they are probably well-behaved.

Indeed they are. Have fun!

-Joe-

Tony Hutchins

unread,
Oct 14, 2003, 11:32:44 PM10/14/03
to
-=[ Wed, 15.10.03 3:48 p.m. +1300 (NZDT) ]=-

Hi Tony Hutchins ! <jus...@csi.com>

17h17m ago, on Tue, 14.10.03 at 10:30 p.m. +1300 (NZDT), you wrote
in message ID <1147579...@news.cis.dfn.de> :

> Joe, me again. I made progress :)

Joe, I can now make all the examples work. The final hopping
skipping and jumping *did* stump me - took about 5 attempts.
I have it working, based on sort of heuristic theory ;-)

eg .500000000001 BF leaves this in the stack:
166666666668
333333333335

Here is BF, with some comments where the line begins with '

<<
' don't allow negative input
ABS 'Z' STO
' create partial quotients, and the convergents
Z MAN MPQN
'could use PN QN / and a counter

'now, HOP to the first convergent which produces
'an "exact-HP48/49 result"
' This is called N2/D2 & the previous one is NJ/DJ
' DJ is actually the JUMPING unit

1 'D2' STO
PN 1 GET 'N2' STO
1 'K' STO
WHILE N2 D2 / Z NOTEQUAL (i.e. "=/=" )
REPEAT
K 1 + 'K' STO
N2 'NJ' STO
PN K GET 'N2' STO
D2 'DJ' STO
QN K GET 'D2' STO
END

' now we do the jumping backwards from N2/D2
' we start about the middle of the whole interval 0->D2
' There, we find D3 and N3
' The trick is that we hop back from D2
' in steps of DJ
' If N3/D3 is indeed a BETTER FRACTION candidate we use D3
' as D2 - otherwise we shift D1 up to D3, and work
' from the middle of the new D1->D2
' J is the distance from 'D3 to D2' measured in steps of
' DJ
0 'D1' STO
D2 DJ / 2 / IP 'J' STO
WHILE J 0 >
REPEAT
D2 DJ J * - 'D3' STO
N2 NJ J * - 'N3' STO
N3 D3 / Z ==
<<N3 'N2' STO D3 'D2' STO>>
<<D3 'D1' STO>>
IFTE
D2 D1 - DJ / 2 / IP 'J' STO
END
N2 D2
>>


MAN - this makes the AN list
of partial quotients
for a positive fraction Z
I make the list end with a 0.

<< ->Z
<< {} Z IP + 'AN' STO
E12 DUP Z FP *
WHILE DUP 0 >
REPEAT
DUP 'D1' STO NDQR
SWAP AN SWAP + 'AN' STO
D1 SWAP
END
AN 0 + 'AN' STO
>>
>>

NDQR (used by MAN)

takes positive integers N D in stack and outputs integers Q R
where N=Q*D + R and R is less than D, and not negative.
The bit before the WHILE is to quickly get a good first guess
for Q.
This puts Q and R on the stack as well as making global
variables for them - I'm in a hurry<G>

<< -> N D
<< N D / IP DUP 0 > <<1 ->>IFT 'Q' STO
N D Q * - 'R' STO
WHILE R D >=
REPEAT
R D - 'R' STO
Q 1 + 'Q' STO
END
Q R
>>
>>

Here is the last piece -

MPQN: uses AN (list of partial quotients)
and produces PN and QN - lists of pk and qk
such that pk/qk is kth convergent.
<<
1 'P0' STO 0 'Q0' STO
AN 1 GET 'P1' STO 1 'Q1' STO
{} P1 + 'PN' STO
{} Q1 + 'QN' STO
AN 2 GET 'AK' STO 2 'K' STO
WHILE AK 0 >
REPEAT
AK P1 * P0 + 'P2' STO
AK Q1 * Q0 + 'Q2' STO
P1 'P0' STO P2 'P1' STO
Q1 'Q0' STO Q2 'Q1' STO
PN P2 + 'PN' STO
QN Q2 + 'QN' STO
K 1 + 'K' STO
AN K GET 'AK' STO
END
>>

None of the examples take more than 3-4 seconds, on a 49g+,so it
is 3-4 times slower than your program Joe.
I only just got this functional, with what I am sure is a very
limited subset of RPL<G>
I see now I could calculate pk/qk as I go, calculating the ak
and can stop as soon as I have the first "exact HP48/49"
result. Also, I make far too many global variables. But, I'm
just so pleased to see it working :)

Really great challenge - thanks!
I'm not really sure about my jumping unit, but, as it does
'hit' on the likely candidates, there must be something to
it<G>. I soon realised I couldn't just look at all
possibilities, unless of course the prior convergent has
denominator 1. The likely candidates are more or less
"quantized" by the prior convergent.

- Tony

Tony Hutchins

unread,
Oct 15, 2003, 2:24:31 AM10/15/03
to
-=[ Wed, 15.10.03 6:40 p.m. +1300 (NZDT) ]=-

Hi Joseph K. Horn ! <joe...@holyjoe.net>

1 day 06h24m ago, on Mon, 13.10.03 at 4:16 p.m. -0700, you wrote
in message ID <87233f9e.03101...@posting.google.com> :

> In case it helps, here are the *EXACT* continued fraction
> expansions of the examples that have appeared in this thread
> so far.

It did help :)
Now I have it all at least functional (in case anyone keys in
the programs from my last post, the MAN can do with a DROP
DROP at the end), I've been experimenting.

The square root of 3 is fascinating - on the HP48/49 it
produces nearly 30 partial quotients!!!! Starting with 9 pairs
of 1 2. I get 716035/413403 for the best fraction.

Joe, you must tell us the story as to how you came to
investigate this - .. if there is a story :-)
Is it part of a book/paper you intend to publish?

--
Tony Hutchins
Wellington
New Zealand

#252 What you will do matters. All you need is to
do it. Judy Grahn

Joseph K. Horn

unread,
Oct 15, 2003, 9:55:10 AM10/15/03
to
Sam Hughes writes:

>> For what it's worth, my program converts
>> sqrt(LOG(2)) into 998995/1820784 in 0.745
>> seconds on an hp49g+, and runs unmodified on
>> an HP48GX.
>
> How long does it take to run on a 48GX,
> or on a 49G?

It takes approximately 3 times longer, for almost any input.

-Joe-

Joseph K. Horn

unread,
Oct 15, 2003, 3:25:34 PM10/15/03
to
Congratulations to Tony Hutchins! He wins the Best Fraction
Challenge! In fact, he's the first person to post a program that
finds the two smallest integers which divide to any given decimal in
less than 5 seconds! Well done!

> Joe, you must tell us the story as to
> how you came to investigate this -
> .. if there is a story :-) Is it part
> of a book/paper you intend to publish?

Sorry, no story. Just one of the things I've stumbled into while
playing around with numbers and HP calculators for the past 27 years.
However, I'm currently working with HP to see that this algorithm,
which I call the PDQ algorithm ("P Divided by Q"), will be used in
place of the current ->Q algorithm in future models. However, my
proposal goes beyond that, allowing the accuracy to be specified
several ways: by a maximum tolerable error, or maximum tolerable
denominator, or minimum exact-match decimal places, or real-world
tolerance by a user-specified scalar. Finally, some sort of Fraction
Hunter application (Fraction Ranger? Fraction Scout? Best Fraction
Finder? PDQ?) would allow the user to see simultaneously the input,
the output, the previous and next fraction (if any), their respective
errors, and real-world scalar error, with options to single-step and
back-step through the continued-fraction convergents and/or
intermediate convergents. This would be helpful in many real-world
applications that rely on precise tolerances, and it would also be
ideal for teaching fractions, decimals, continued fractions, rationals
and irrationals, and many other concepts.

If HP doesn't bite the bait, I'll just "publish" it all on the web for
all to see and use as they wish. Meanwhile, have fun with it!

Legal Fine Print for TI, Casio, Sharp et al: The PDQ Algorithm is the
intellectual property of Joseph K. Horn. Ownership was demonstrated
at HHC 2003 on September 21, 2003, in front of dozens of witnesses,
and the entire proceedings are available on videotape. Any use of
this algorithm for commercial purposes without proof of prior
ownership or written permission of Joseph K. Horn would be a Bad
Thing. You Have Been Warned.

-Joe-
Joseph K. Horn
p...@holyjoe.us

Gerald Squelart

unread,
Oct 15, 2003, 6:52:40 PM10/15/03
to
"Joseph K. Horn" <joe...@holyjoe.net> wrote:
[...]

> The PDQ Algorithm is the
> intellectual property of Joseph K. Horn. Ownership was demonstrated
> at HHC 2003 on September 21, 2003, in front of dozens of witnesses,
> and the entire proceedings are available on videotape. Any use of
> this algorithm for commercial purposes without proof of prior
> ownership or written permission of Joseph K. Horn would be a Bad
> Thing. You Have Been Warned.
> -Joe-
> Joseph K. Horn
> p...@holyjoe.us

Hi Joe!

AFAIK, unless you patent your algorithm for every possible way it may be
used, anybody may use it. All you own at the moment is the program you wrote
(that uses this algorithm) and I guess it could be named 'Horn Algorithm' if
it's truly new. So if you don't want others to freely use your algorithm,
patent it or keep it for yourself; Both being Bad Things anyway in my
opinion.
IANAL, of course, so prove me wrong if I am ;-)

HAGD,
G.


Tony Hutchins

unread,
Oct 15, 2003, 8:45:13 PM10/15/03
to
-=[ Thu, 16.10.03 12:39 p.m. +1300 (NZDT) ]=-

Hi Joseph K. Horn ! <joe...@holyjoe.net>

1 day 30m ago, on Tue, 14.10.03 at 4:08 p.m. -0700, you wrote
in message ID <87233f9e.03101...@posting.google.com> :

> > *That* is what gave me the clue to doing


> > the expansion - I don't start with .500000000001
> > but that*E12 /E12 - I start with an integral
> > numerator and a denominator. Thanks for that
> > hidden tip!!
>
> That's the trick for avoiding the 1/FP(x) roundoff errors that have
> plagued decimal-to-fraction algorithms forever.

They have indeed - I looked into decimal->fraction using
continued fractions earlier this year. And everything I saw
used the 1/x. I started with the PPC ROM version - always a
good place to start :)

Joe, I don't know how, but I missed this post yesterday -
despite eagerly looking out for another hint!!

> "You have taken your first steps into a larger world."
> -- Obi-Wan Kenobi

Indeed, the wholesome world of integers :)

> > I seem to be stumped as to how to "hop, skip
> > and jump" to near the 33333333335 denominator.
>
> MASSIVE HINT (spoiler, actually) #2: With the list of
> partial quotients handy, examine the *differences* between
> successive intermediate convergents' numerators. Now do
> the same for their denominators. When the pattern hits
> you, it'll hit you hard, so be sure to be sitting down!

Ahha! I missed this spoiler, and I only started looking at
this out of desperation<G>. I noticed one example by chance -
that 2 LOG SQRT case. I got there by trial and error with
little understanding. But, what a thrill to see it work for
all cases! Actually successive convergents are very closely
related - multiplying numerators by the others denominators
and taking the difference one seems to get 1!!!
[...]


> > although the results go up and down in a sawtooth
> > like way, overall they are probably well-behaved.
>
> Indeed they are. Have fun!

I did - and now I might try and improve the RPL by using INCR
and STO+ etc and see how many globals I can just keep on the
stack instead. And I should prove to myself that there are no
other better candidates lurking.

Thanks for your more recent post too - telling about "PDQ" :)
Fascinating. It has a certain beauty and simplicity, once one
sees it :) Thanks for sharing it with us!

--
Tony Hutchins
Wellington
New Zealand

#229 It's not over till it's over. Yogi Berra

Rodger Rosenbaum

unread,
Oct 15, 2003, 10:57:38 PM10/15/03
to
Joe defines a "best fraction" for the purposes of this challenge as:

"the smallest integers which, when

divided on the calculator, yield exactly the same number as the input."

Let us call this a Best(JH) fraction. There might be other "best" fractions which are not
Best(JH). To use one of Joe's examples:

"Input: 6.0030000004 (the strange number on the HP38G case)"
"Output: 14823406 / 2469333"

Two other fractions which both evaluate to 6.0030000004 on the HP48 are:

15009499/2500333 and 15195592/2531333

They have special properties; who can characterize them?

I think one might say that "best" is in the eye of the user.

For example, suppose one were designing a synthesiser to generate a 6.0030000004 Hertz
frequency. One way to do it would be to buy a crystal oscillator running at a frequency
of 14823406 Hertz and divide that output by 2469333; this would be the Best(JH) way to do
it, but would it be the "best" way? What does "best" mean for you?

Joe's challenge is fascinating and difficult, but I'm not sure that the Best(JH) fraction
is the "best" except in curiosity and educational value.

Can anybody think of a situation where 14823406/2469333 would be preferred to
15009499/2500333 as an approximation to 6.0030000004? When would the slightly smaller
numerator and denominator of 14823406/2469333 compared to 15009499/2500333 be of value,
given the special property of 15009499/2500333 (said property to be determined by the
audience). The ->Q function on the HP48 gives 15003496/2499333 for 6.00300000004 (in STD
mode), which lacks the special property that 15009499/2500333 has.

This posting is not meant to belittle or minimize this latest excellent challenge of Joe
Horn (who is a friend of mine). :-)

Tony Hutchins

unread,
Oct 16, 2003, 1:45:49 AM10/16/03
to
-=[ Thu, 16.10.03 6:07 p.m. +1300 (NZDT) ]=-

Hi Joseph K. Horn ! <joe...@holyjoe.net>

09h42m ago, on Wed, 15.10.03 at 12:25 p.m. -0700, you wrote
in message ID <87233f9e.03101...@posting.google.com> :

> Congratulations to Tony Hutchins! He wins the Best Fraction


> Challenge! In fact, he's the first person to post a program that
> finds the two smallest integers which divide to any given decimal in
> less than 5 seconds! Well done!

Thanks Joe!

I'll still be looking at this till Christmas I think.
My old paper HP49G Advanced User's Guide (the one with the
black cover - must be rare<G>), just told me that IDIV2 does
exactly what my 'NDQR' code does. And it works great too - eg
E12 500000000001 IDIV2 gives 1 and 499999999999 - even in
"approx" mode (contrary to the manual).

> > Joe, you must tell us the story as to
> > how you came to investigate this -
> > .. if there is a story :-) Is it part
> > of a book/paper you intend to publish?
>
> Sorry, no story. Just one of the things I've stumbled into
> while playing around with numbers and HP calculators for
> the past 27 years. However, I'm currently working with HP
> to see that this algorithm, which I call the PDQ algorithm
> ("P Divided by Q"), will be used in place of the current
> ->Q algorithm in future models.

Great idea!!! I look forward to that. It might even be in a
future 49g+ ROM :)

> However, my proposal goes beyond that, allowing the
> accuracy to be specified several ways: by a maximum
> tolerable error, or maximum tolerable denominator,
> or minimum exact-match decimal places, or real-world
> tolerance by a user-specified scalar.

Terrific. I see the old ->Q in there somewhere ;-)

> Finally, some sort of Fraction Hunter application (Fraction
> Ranger? Fraction Scout? Best Fraction Finder? PDQ?)

HP can invent a name :)
Harvester ?
Picker?

Your PDQ is so thorough in finding excellent and useful
fractions. And surprising fractions! It is almost forensic.
It finds new fractions. And it works right up to the limits of
the HP48/49 precision, because of that 15 digit thing you
mentioned, and the internal rounding.

> would allow the user to see simultaneously the input,
> the output, the previous and next fraction (if any), their
> respective errors, and real-world scalar error, with options
> to single-step and back-step through the continued-fraction
> convergents and/or intermediate convergents.

Will be very educational.

I hope there is also a built-in partial quotient generator.
They are so interesting. And the reverse. ->PQ and PQ-> :)
GCD must already do something like that internally.

> This would be helpful in many real-world applications that
> rely on precise tolerances, and it would also be ideal for
> teaching fractions, decimals, continued fractions, rationals
> and irrationals, and many other concepts.

Indeed. Now I know why your domain is holyjoe - you like whole
numbers :)

> If HP doesn't bite the bait, I'll just "publish" it all on
> the web for all to see and use as they wish. Meanwhile, have
> fun with it!

*I* am sure HP will use it :)
And soon, I hope.

I looked up my old 1965 Encyclopedia Britannica - it has a
great article on Partial Fractions. But everything I see even
there jumps to more complex features.

> Legal Fine Print
[...]
Hehe I have done you a favour then - anybody studying my code
would just get very confused - no chance of translating it :)

It's amazing the piracy that happens in business circles
though - recently I was pointed to an *non hp* financial
calculator which seems to be a 12C clone!!!!! (I ordered
one<G>).

Tony Hutchins

unread,
Oct 16, 2003, 2:42:23 AM10/16/03
to
-=[ Thu, 16.10.03 6:51 p.m. +1300 (NZDT) ]=-

Hi Tony Hutchins ! <jus...@csi.com>

05h06m ago, on Thu, 16.10.03 at 1:45 p.m. +1300 (NZDT), you wrote
in message ID <1090147...@news.cis.dfn.de> :

> Joe, I don't know how, but I missed this post yesterday -
> despite eagerly looking out for another hint!!

I figured it out now - I missed 11 consecutive articles -
about the time I did a chkdsk /f and found cross-linked files.
My poor old DOS machine was the problem, not cis.dfn.de, nor
my home-grown newsreader. First time I have seen this -
everything looked like it was working fine, but ... the
articles came in and I'm not sure where they went<G>.

- Tony

Gjermund Skailand

unread,
Oct 16, 2003, 3:02:28 AM10/16/03
to
Hi
"Joseph K. Horn" <joe...@holyjoe.net> wrote in message
news:87233f9e.03101...@posting.google.com...

> Congratulations to Tony Hutchins! He wins the Best Fraction
> Challenge! In fact, he's the first person to post a program that
> finds the two smallest integers which divide to any given decimal in
> less than 5 seconds! Well done!

I still havent got it right with the "Evil" ones,
But for what it is worth, in my longfloat (arbitrary precision) library
there are
3 simple commands
- for converting a longreal to a simple fraction
- for converting a simple fraction to a continued fraction
- for converting a continued fraction to a simple fraction

The continued fractions use lists. But no "minimum fractions":-(

Best regards
Gjermund Skailand


Werner Huysegoms

unread,
Oct 16, 2003, 12:09:40 PM10/16/03
to
Here's the first subprograms needed (working on the rest):

@ IDIV2 - Quotient and Remainder
@
@ bytes: 30.0
@ check: #C142h (48)
@ not needed on 49
@
@ In: 2: a
@ 1: b
@
@ Out: 2: q
@ 1: r
@
@ so that b*q + r = a
@
\<< DUP2 MOD ROT OVER - ROT / SWAP \>>

@ \->CF - Create Simple Continued Fraction
@
@ bytes: 98.0 (48)
@ 96.0 (49)
@ check: #E52Bh (48)
@ #5800h (49)
@
@ In: 1: x
@
@ Out: 1: { a0 a1 .. an }, ai integer (any i), and ai>0 for i>0
@
@ x = a0 + 1/(a1 + 1/(.. + 1/an))
@
\<<
DEPTH
\-> D
\<<
@ turn x into p/q
DUP MANT 1E11 * OVER / SWAP OVER *
@ stack holds 2:q 1:p, with ri = p/q
WHILE
@ calculate ai
OVER IDIV2 DUP
REPEAT @ stop when remainder is zero
@ calculate ri+1
ROT
END
ROT DROP2
D DEPTH SWAP - \->LIST
\>>
\>>

Cheers,
Werner

Tony Hutchins

unread,
Oct 16, 2003, 2:58:56 PM10/16/03
to
-=[ Fri, 17.10.03 07:25 a.m. +1300 (NZDT) ]=-

Hi Werner Huysegoms ! <werner-h...@freegates.be>

02h16m ago, on Thu, 16.10.03 at 09:09 a.m. -0700, you wrote
in message ID <44ec85ff.03101...@posting.google.com> :

> Here's the first subprograms needed (working on the rest):

Thanks Werner - they are so ** elegant ** !

> @ IDIV2 - Quotient and Remainder
> @
> @ bytes: 30.0
> @ check: #C142h (48)
> @ not needed on 49
> @
> @ In: 2: a
> @ 1: b
> @
> @ Out: 2: q
> @ 1: r
> @
> @ so that b*q + r = a
> @
> \<< DUP2 MOD ROT OVER - ROT / SWAP \>>

I *never* realized that MOD would do the job there.
I did wonder, but never tested it.
Great - you have made an IDIV2 for the 48 :)

This is much better than my current version:
<< DUP IP 1 ->LIST SWAP E12 SWAP FP OVER *
WHILE DUP 0 >
REPEAT DUP 4 ROLLD IDIV2 3 ROLLD + 3 ROLLD
END * +
>>

This returns a zero on the last position (that last * + does
that), but I can see you will use DEPTH with your string to
figure out how far to go with it.

Interesting how you use the stack - I must expand my
imagination - it only extends to a 4 levels <G>

I really look forward to your next instalment :)

I will try your ->CF today.
It is a work of ART!!! I wondered about MANT as well.
Your MANT E11 * is probably better than FP E12 *
- then your OVER / creates a perfect E12 :)

Very interesting.
Is it true that I could take your text above, store it in a
file on the desktop and then transfer it to a HP48/49 and it
would work?

Could you point me to something at www.hpcalc.org that
explains this format, especially the "@" for comments ?

Joseph K. Horn

unread,
Oct 16, 2003, 5:27:38 PM10/16/03
to
Tony Hutchins wrote:

> I *never* realized that MOD would do the job there.

Is there any other way? Any other method (e.g. / IP first) gets
roundoff errors.

> Your MANT E11 * is probably better than FP E12 *
> - then your OVER / creates a perfect E12 :)

Because of MOD's accuracy, you don't need to turn the input into a
ratio of huge integers; just start with the unmodified input as the
numerator, 1 as the denominator, and start looping. Cool, huh? It's
*mathematically* identical to what you were doing, but faster and just
as accurate, thanks to HP's MOD code.

-Joe-

Joseph K. Horn

unread,
Oct 16, 2003, 5:49:43 PM10/16/03
to
Gerald Squelart writes:

> AFAIK, unless you patent your algorithm for
> every possible way it may be used, anybody
> may use it. All you own at the moment is the
> program you wrote (that uses this algorithm)
> and I guess it could be named 'Horn Algorithm'
> if it's truly new. So if you don't want
> others to freely use your algorithm, patent it
> or keep it for yourself; Both being Bad Things
> anyway in my opinion.

I agree that keeping it to myself would be a Bad Thing, which is why I
(a) presented it at HHC 2003, (b) indirectly presented in this thread
and will post it in full shortly, and (c) took a vow never to do that
with anything. ;-)

As for patenting it, wouldn't it be a Good Thing IF I did that AND (a)
either gave or licensed it to HP for them do put it into their
calculators, and (b) released it for free use by everybody EXCEPT as a
built-in feature of any handheld device? That way, everybody would
benefit, even TI and their ilk could offer it as add-on software.
Only HP would be able to advertise "the best fraction calculators"
where "best" refers to the fractions, not to the calculators, of
course. >:-O

Since all this is currently being appraised by Powers That Be,
*please* advise if I'm blissfully strolling down a primrose path,
since I am not familiar with the legalities involved.

If it DOES get patended, it will be known as the PDQ Algorithm, not
the Horn Algorithm. As I told the HHC 2003 assemblage, "No way!
Students would see a button that says HORN, and they'd push it, and
complain that it doesn't work." The preceding is a printable
paraphrase of what was actually said. ;-)

I'll bet anybody here up to $1.53 that it is in fact a new algorithm.
This offer will stand until the first time I lose the bet, at which
time all bets are off. :-b

-Joe-

Joseph K. Horn

unread,
Oct 16, 2003, 7:23:33 PM10/16/03
to
Rodger Rosenbaum writes:

> I think one might say that "best" is in the eye of the user.

Hurwitz and most other mathematicians agree with you. In fact, my
full PDQ package outputs the "Hurwitz Accuracy" of each convergent
(calculated as the actual error times the denominator squared times
the square root of five) so that the user can base his or her decision
on that, if they wish.

Loosely, the Hurwitz Accuracy of a convergent is a kind of ratio of
the number of digits of input over the number of digits of output. If
making gears, for example, it would make no sense to go from a 22/7
gear ratio to a 179/57 gear ratio in an attempt to approximate pi,
because even though 179/57 is a "better fraction" for pi, it offers
only 0.0000227 increase in accuracy, roughly 2 centimeters per
kilometer! This can be seen easily by looking at the Hurwitz Accuracy
of 22/7 for pi (namely, -0.138546713972020) versus the Hurwitz
Accuracy of 179/57 (namely 9.021486720965779). Hurwitz proved that
any convergent with an Hurwitz Accuracy less than 1 (absolute value)
must be a continued fraction convergent, and not "merely" one of the
intermediate convergents.

In brief, the continued fraction convergents yield the "best"
fractions IF AND ONLY IF the "bang per buck" is considered, that is,
the number of digits you get out compared to the number of digits you
put in. In this sense, there is no "better" fraction than 355/113 for
pi until you get out to something 440 digits. The calculation of that
fraction is left as an exercise for the reader. ;-)

Hurwitz Accuracy is only one kind of accuracy. There are others, each
appropriate for some particular tasks. I discussed several in my
conference paper.

> What does "best" mean for you?

As I hope I explained during this thread already, it means different
things for different *purposes*. If one's task demands a complete and
accurate examination of ALL the fractions that approach any given
decimal number, then every fraction in that list is a "best" fraction,
and the PDQ Algorithm is the only way to find all of them.

On the other hand, if one has no need of precision or completeness,
then the age-old continued-fraction-only algorithm based on 1/FP(x)
will suffice, such as HP's ->Q.

> Joe's challenge is fascinating and difficult,
> but I'm not sure that the Best(JH) fraction
> is the "best" except in curiosity and
> educational value.

Thank you. I can think of no loftier objectives than those. ;-)

"Fun and learning. Everything comes down to those two."
-- Donald Shimoda, reluctant messiah.

PDQ solves a previously unsolved problem. Why? Because it was there,
and nobody else was trying to solve it. Amen.

> Can anybody think of a situation where
> 14823406/2469333 would be preferred to
> 15009499/2500333 as an approximation to
> 6.0030000004?

Yes! HP *claimed* to offer "the smallest fraction equal to the
displayed decimal number" with the ->Q function. It cannot read your
mind to know what YOU mean by "best", so it simply churned out the
smallest fraction equal to the input (in STD mode)... or at least it
was SUPPOSED to. PDQ does exactly what ->Q claimed to do but never
did.

> When would the slightly smaller numerator and
> denominator of 14823406/2469333 compared to
> 15009499/2500333 be of value, given the special
> property of 15009499/2500333 (said property to
> be determined by the audience).

Is "said property" that the latter has a much better Hurwitz Accuracy,
namely 0.7447095671868303496, as compared to -67.732319542344457 for
the former? If that's not the one you had in mind, it's still true.

> The ->Q function on the HP48 gives
> 15003496/2499333 for 6.00300000004
> (in STD mode), which lacks the special
> property that 15009499/2500333 has.

The former has a Hurwitz Accuracy of -1.491059671430066483, which also
not as good as the latter's (given above).

Something that Hurwitz seemed not to notice (or care about) is that
his definition of "best" omits not only all of the intermediate
convergents (as it seems you too would prefer to do) but also all the
regular ones based on a partial quotient that is smaller than the
largest one so far. This would mean that pi only has 3/1, 22/7, and
355/113 as "best" fractions, with the next "best" fraction having
something around 440 digits in it. An algorithm that spits out THOSE
fractions is trivial, and pretty useless considering the paucity of
fractions it generates. It doesn't find ANY for the square root of 3
(other than 2/1, which is not very satisfying!).

> This posting is not meant to belittle
> or minimize this latest excellent challenge
> of Joe Horn (who is a friend of mine). :-)

You, Bob Wilson, and Bob Hall have given me no end of delightful food
for thought for many years. This thread is my way of saying "Thank
You" to y'all!

"The best payment for a good idea is another good idea."
-- Richard J. Nelson

-Joe-

Tony Hutchins

unread,
Oct 16, 2003, 8:33:50 PM10/16/03
to
-=[ Fri, 17.10.03 12:59 p.m. +1300 (NZDT) ]=-

Hi Joseph K. Horn ! <joe...@holyjoe.net>

02h31m ago, on Thu, 16.10.03 at 2:27 p.m. -0700, you wrote
in message ID <87233f9e.03101...@posting.google.com> :

> Tony Hutchins wrote:
>
> > I *never* realized that MOD would do the job there.
>
> Is there any other way? Any other method (e.g. / IP first) gets
> roundoff errors.

There was another way <VBG>
I did it my way with IP first.
This was my "IDIV2":

<< N D / IP DUP 0 > <<1 ->>IFT 'Q' STO
N D Q * - 'R' STO
WHILE R D >=
REPEAT
R D - 'R' STO
Q 1 + 'Q' STO
END
Q R
>>

If my IP was positive I took 1 away from it, and then, I gave
it back if it were needed. Hehe. Rather pointless I admit,
given that we have MOD ;-)

LOL! You should have seen my first version - it built up the
'Q', one by one, from zero, but it was a bit slow<G>.



> > Your MANT E11 * is probably better than FP E12 *
> > - then your OVER / creates a perfect E12 :)
>
> Because of MOD's accuracy, you don't need to turn the input into a
> ratio of huge integers; just start with the unmodified input as the
> numerator, 1 as the denominator, and start looping. Cool, huh? It's
> *mathematically* identical to what you were doing, but faster and just
> as accurate, thanks to HP's MOD code.

WOW is all I can say. The code shrinks<G>. IDIV2 is not needed
(well, can't be used then). MOD gives the remainder to carry
forward - meanwhile we need to reconstruct the integral quotient that
we capture: N D MOD gives R, and Q=(N/D -R)/D which will be an
exact integer, thanks to the MOD :)

Thanks! BTW I received my DataFile today and it has Richard's
HHC2003 conference report in, with a fascinating paragraph or
two about PDQ :)

--
Tony Hutchins
Wellington
New Zealand

#191 Whom God wishes to destroy, he first makes
mad. Proverb

Tony Hutchins

unread,
Oct 16, 2003, 9:22:20 PM10/16/03
to
-=[ Fri, 17.10.03 2:05 p.m. +1300 (NZDT) ]=-

Hi Tony Hutchins ! <jus...@csi.com>

31m ago, on Fri, 17.10.03 at 1:33 p.m. +1300 (NZDT), you wrote
in message ID <1088903...@news.cis.dfn.de> :
[...]


> WOW is all I can say. The code shrinks<G>. IDIV2 is not needed
> (well, can't be used then). MOD gives the remainder to carry
> forward - meanwhile we need to reconstruct the integral quotient that
> we capture: N D MOD gives R, and Q=(N/D -R)/D which will be an
> exact integer, thanks to the MOD :)

Whoops! Q=(N-R)/D

--
Tony Hutchins
Wellington
New Zealand

#302 When you win, nothing hurts. Joe Namath

Werner Huysegoms

unread,
Oct 17, 2003, 1:38:24 AM10/17/03
to
Tony Hutchins <jus...@csi.com> wrote in message news:<1088903...@news.cis.dfn.de>...

>
> > > Your MANT E11 * is probably better than FP E12 *
> > > - then your OVER / creates a perfect E12 :)
> >
> > Because of MOD's accuracy, you don't need to turn the input into a
> > ratio of huge integers; just start with the unmodified input as the
> > numerator, 1 as the denominator, and start looping. Cool, huh? It's
> > *mathematically* identical to what you were doing, but faster and just
> > as accurate, thanks to HP's MOD code.
>

[To Joe:] Ah yes of course!

> WOW is all I can say. The code shrinks<G>. IDIV2 is not needed
> (well, can't be used then). MOD gives the remainder to carry
> forward - meanwhile we need to reconstruct the integral quotient that
> we capture: N D MOD gives R, and Q=(N/D -R)/D which will be an
> exact integer, thanks to the MOD :)
>

[To Tony:] well, both of these combined is what IDIV2 does... so I keep it in.

Cheers,
Werner

Werner Huysegoms

unread,
Oct 17, 2003, 1:50:41 AM10/17/03
to
(follow up to the previous message, posted too quickly)

.. but of course, I cannot call it IDIV2 any more as on the 49, IDIV2
will accept only integers. let's call it QUOTREM, then.

Werner

Rodger Rosenbaum

unread,
Oct 17, 2003, 2:34:01 AM10/17/03
to
On 16 Oct 2003 16:23:33 -0700, joe...@holyjoe.net (Joseph K. Horn) wrote:


>Yes! HP *claimed* to offer "the smallest fraction equal to the

^^^^^!!


>displayed decimal number" with the ->Q function. It cannot read your
>mind to know what YOU mean by "best", so it simply churned out the
>smallest fraction equal to the input (in STD mode)... or at least it
>was SUPPOSED to. PDQ does exactly what ->Q claimed to do but never
>did.
>

Did HP actually say just as you have quoted? This a pretty bold statement; I can't find
it in any of my manuals. Where did they say that?