The Museum of HP Calculators

HP Forum Archive 17

[ Return to Index | Top of Index ]

RPN versus ALG in programs
Message #1 Posted by Thomas Klemm on 25 Aug 2007, 9:07 p.m.

Just recently I stumbled across Katie Wasserman's fine article 99 Digits of PI on an HP 32SII which I apreciated a lot. It made me have a look again at the different algorithms to calculate Pi. After implementing a RPN-version of the Gauss AGM algorithm for the 35s I was curious on how to do the ALG-version. Here's the result of both:

RPN                            ALG

G001 LBL G H001 LBL H G002 1 H002 1>A G003 STO A H003 3>I G004 3 H004 SQRT(0.5>P>S)>B G005 STO I H005 S-SQ(A-B)*P>S G006 0.5 H006 2*P>P G007 STO P H007 (A+B)/2 G008 STO S H008 SQRT(A*B)>B G009 SQRT H009 REGY>A G010 STO B H010 DSE I G011 RCL- A H011 GTO H005 G012 x2 H012 SQ(A+B)/(2*S) G013 RCL* P H013 RTN G014 STO- S G015 RCL A LN=115 G016 RCL+ B G017 2 G018 STO* P G019 / G020 x<> A G021 RCL* B G022 SQRT G023 STO B G024 DSE I G025 GTO G011 G026 RCL+ A G027 x2 G028 RCL/ S G029 2 G030 / G031 RTN

LN=100

(inspired by algorithm 7.5 from Arndt & Haenel, Pi-unleashed)

Now if you run both variants you will find that H is about 4 times slower than G. Also H seems to use more memory than G. On the other hand H might be easier to read. But you have to scroll to be able to read the whole lines.

What I don't understand is why is H so slow? I mean both are kind of slow but H is realy bad. Hey, there are only 3 iterations and it takes about 4 seconds!

Being curious about the performance I implemented the same algorithm for my 11c as well:

01 LBL A                 21 SQRT
02 3                     22 x<>y
03 STO I                 23 R^
04 2                     24 x2
05 1/x                   25 RCL 1
06 STO 0                 26 *
07 STO 1                 27 STO- 0
08 SQRT                  28 RDN
09 ENTER                 29 2
10 ENTER                 30 STO* 1
11 ENTER                 31 /
12 1                     32 DSE
13 LBL 0                 33 GTO 0
14 -                     34 +
15 R^                    35 x2
16 LSTx                  36 RCL 0
17 +                     37 /
18 R^                    38 2
19 LSTx                  39 /
20 *                     40 RTN
Not to my surprise it's considerably slower taking about twice the time of H. But when I ran the same program on a 42s I was amazed: Though it's slower than G it beats H by far.

Twenty years later and not much improvement concerning the speed! Does anybody know why? Is it so difficult to construct a fast calculator?

I must admit that I'm quiet happy with the 35s in spite of the issues already mentioned in this forum. But I'd really like to have a calculator that is fast, e.g. counts to a million in less than a second.

In other interpreted languages it's possible:

> time perl -e 'for ($i=0; $i<1e6; $i++) {}'

real 0m0.219s user 0m0.199s sys 0m0.003s

So why can't we have that in a calculator as well?

Thomas

      
Re: RPN versus ALG in programs
Message #2 Posted by Jeff Kearns on 25 Aug 2007, 9:31 p.m.,
in response to message #1 by Thomas Klemm

Agreed. Calculators are still too slow for many 'routine' operations considering the fact that we are in 2007. I tried your interesting 11C program out on my 15C and have the following comment regarding step 32.

Quote:

Being curious about the performance I implemented the same algorithm for my 11c as well:

01 LBL A                 21 SQRT
02 3                     22 x<>y
03 STO I                 23 R^
04 2                     24 x2
05 1/x                   25 RCL 1
06 STO 0                 26 *
07 STO 1                 27 STO- 0
08 SQRT                  28 RDN
09 ENTER                 29 2
10 ENTER                 30 STO* 1
11 ENTER                 31 /
12 1                     32 DSE
13 LBL 0                 33 GTO 0
14 -                     34 +
15 R^                    35 x2
16 LSTx                  36 RCL 0
17 +                     37 /
18 R^                    38 2
19 LSTx                  39 /
20 *                     40 RTN


Step 32, above should read

032 - 42, 5,25 DSE I - at least in order to work on my 15C. Regards,

JeffK I

      
Re: RPN versus ALG in programs
Message #3 Posted by Dave Shaffer (Arizona) on 26 Aug 2007, 12:00 a.m.,
in response to message #1 by Thomas Klemm

Speed costs you in power.

Every time one of those CMOS gates changes state, a bit of your battery charge disappears. I guess you could have a faster machine, but you might have to change the battery more often than you'd appreciate. All those 11Cs and 15Cs that lasted for 15-20 years on the same battery weren't just dumb luck!

      
Re: RPN versus ALG in programs
Message #4 Posted by DaveJ on 26 Aug 2007, 2:54 a.m.,
in response to message #1 by Thomas Klemm

Quote:
Twenty years later and not much improvement concerning the speed! Does anybody know why? Is it so difficult to construct a fast calculator?

Power consumption is roughly proportional to processing speed, the tradeoff has to be made somewhere. And on top of that, the 35S is no doubt written in C, probably with a deal of thought toward code portability and re-use (that usually means bigger code), so that costs you in performance in two ways alone. Whereas the older machines were most likely hand coded in assembler and hence gave better bang-per-bucks on each clock cycle.

Dave.

      
Re: RPN versus ALG in programs
Message #5 Posted by Vieira, Luiz C. (Brazil) on 27 Aug 2007, 4:16 a.m.,
in response to message #1 by Thomas Klemm

Hi, Thomas;

(here I am at 4:50 AM feeling insomnia...)

many of us who not only use and deal with HP calculators but also try to go further to their 'guts' have probably read that RPN structures were achieved mostly in search of a resident 'proto', portable operating system that could fit in less ROM, OR could offer the most in the same available ROM space. So, RPN offers many intersting features BUT math precedence. I like to say that math precedence in RPN calculators must be provided by the user, who must master math prior to use an RPN calculator. That is why I think RPN is educative, but I'd rather not going ahead with that in order to avoid seeting fire in extinguished fireplaces...

To achieve algebric operation, it is mandatory to have at least a few registers to store the first keyed-in number and the code of the operation to be performed (for two-number sequences) so you can key in the second value and press [=] key. Keep in mind that there is no way to count on system 'memory' to hold necessary data if this memory has not yet been provided, meaning that, in any digital device, data must reside somewhere, and this 'somewhere' needs a very well defined address and physical circuits... Sorry if you already know about this.

RPN calculators demand no structure for precedence operators because whenever the operation key is pressed, the number(s) over which such operations will be performed must exist in the stack (in programs it happens the same). So they are already stored in X and Y registers and the system only needs to retrieve a copy of them and go ahead with the operations.

Consider line H008 SQRT(A*B)>B in your listing. You see, prior to get the resulting value from SQRT(A*B), the system must store the codes for:

SQRT( (a code for calling it, not the routine itself)
A
*
B  (in RPN/ALG HP calculators, shares X-register address)
A total of four registers taken from somewhere in RAM, meaning that it actually uses more memory as you noticed, indeed. When the ')' is found, the whole sequence is 'unloaded' and the result is found.

The system uses some cycles (clock) to store the intermediate codes, some others to 'unload' them and the actually necessary cycles to perform then. It may take almost three to four times more time when compared to the RPN version.

I may have left some considerations behind, but I guess the most important facts are described here already.

Hope this helps.

My 2.

Luiz (Brazil)

Edited: 27 Aug 2007, 4:39 a.m.


[ Return to Index | Top of Index ]

Go back to the main exhibit hall