Programming Exercise (HP-15C, 15C LE - and others)

[Gerson W. Barbosa]

1) Do only item (b) of the following exercise, taken from the book Systematic Programming, An Introduction, by Niklaus Wirth (but feel free to do them all, if you wish :-)

It should take under one minute to sum all 10 thousand terms on an HP-15C LE (you might not try this on the classic HP-15C as it would take around 2 and a half hours).

I don't remember what I used in 1984, but the pencil annotation in my printed copy of the book matches the HP-15C result, at least for item (b) (I haven't checked the other items).

2) As you can see, this series for ln(2) is very slowly convergent (10^4 terms yield only 3 significant digits). Modify your program so that it can compute the constant under one minute on a classic HP-15C (or HP-11C, 12C, 41C and other 10 or 12-digit RPN calculator). Tip: try to find an empirical relationship between the number of terms and the error.

Only as a reference, my HP-15C programs for items 1) and 2) are 15 and 24 steps long, respectively. Remember, this is an exercise, not a challenge. All solutions are welcome, not only the shorter and faster ones.

Have fun!

[Thomas Klemm]

(03-16-2014 02:17 AM)Gerson W. Barbosa Wrote:  by Niklaus Wirth

He has recently celebrated his 80th birthday.

I'm lazy and just leave a link to the HP-15C Mini-challenge: Speeding it up !

Quote:I took your HP-11C program that sums an alternating series ...

cf. Summation of infinite, alternating series

Cheers
Thomas

[Gerson W. Barbosa]

Yes, I was aware of Valentin's mini-challenge on a similar series for pi. It took me quite a while to find it yesterday, BTW. I'd thought of including it in my post, but that would've bee kind of a spoiler. But no problem, this may lead to better solutions (one for the HP-42S would be particularly appreciated, since now Free42 has 34 digits of precision). I did forget to include the link to the Wikipedia Article on Niklaus Wirth, however. Here it is:

http://en.wikipedia.org/wiki/Niklaus_Wirth

I'll post the 39 steps I mentioned later :-) These include two pairs of LBL/RTN instructions.

Cheers,

Gerson.

[Gerson W. Barbosa]

(03-16-2014 05:23 AM)Thomas Klemm Wrote:  I'm lazy and just leave a link to the HP-15C Mini-challenge: Speeding it up !

Quote:I took your HP-11C program that sums an alternating series ...

To those who haven't followed the link, that was Paul Dale replying to Valentin about a modification for the HP-42S of his (Valentin's) generic program for summing alternating series. That was not posted because it didn't meet Valentin's size requirement, I think. That HP-42S version might be interesting, but I guess it's gone by now.

(03-16-2014 05:23 AM)Thomas Klemm Wrote:  cf. Summation of infinite, alternating series

Quoting from Valentin's article:

"Find the sum of S = 1 -1/2 + 1/3 - 1/4 + 1/5 - ...

- we define the i-th term = 1/(1+i):

GTO B, P/R, 1, +, 1/x, RTN, P/R

- we'll use PSum = 10, NDif = 7 for maximum accuracy:

10, ENTER, 7, A

- after just one minute, we get the sum = 0.693147182 in the display. The
theoretically correct value is Ln(2) = 0.693147181, so we've got 9 decimals accuracy."

My 28-step program (on the HP-11C) returns 0.69314271805 in 51 seconds, after summing the first 66 of the series and doing the necessary correction. But mine is specific program while Valentin's is a generic program. Also, I've used just a 2-term continued fraction to correct the sum.

The correct value to 16-digit accuracy is 0.6931471805599453.

Cheers,

Gerson.

[Gerson W. Barbosa]

(03-16-2014 05:23 AM)Thomas Klemm Wrote:  I'm lazy and just leave a link to the HP-15C Mini-challenge: Speeding it up !

Hello Thomas,

Sorry for yet another reply to the same part of your post, but it just happens I finally understood what you meant by being "lazy" (I am sometimes rather slow at understanding such things). You must have thought this was just a re-post of Valentin's mini-challenge in disguise, so it was not worth any effort of your part or anyone else's (hence your posting of the above link), mustn't you?

The fact is that I found the above problem in one of my old text-books and decided to check the sums on a 10-digit RPN calculator. At first I used an HP-12C. A very simple problem indeed, 21 or 22 steps in my first attempt. But I thought trying to use the least number of steps would be an interesting exercise. For this task I switched to the HP-15C, because of DSE and recall arithmetic and managed to save a few steps. Then I decided to search for correct term or factor. The first thing I tried worked nicely:


30 f A CHS --> 0.676758138 ; sum of the first 30 terms
CHS 2 LN + 1/x --> 61.01637576 ; this means the first term of the cont'd fraction is 61
f FRAC 1/x --> 61.06586809 ; the second term of the cont'd fraction is also 61

That is,

Ln(2) ~ Sum(1..30,(-1)^(n - 1)/n) + 1/(61 + 1/61) = 0.693147176

Further tests have finally allowed for the generalization

Ln(2) ~ Sum(1..N,(-1)^(n - 1)/n) + 1/((2*N + 1) + 1/(2*N + 1))

At this point I remembered of an old challenge or mini-challenge by Valentin on the acceleration of a slowly convergent series for pi. As I said, it took me quite a while to find it (I was searching for acceleration instead of speeding-up). I read briefly through his commented solution but failed to notice it was essentially the same thing. He had noticed many matching digits of the constant for certain N, which I did not, and found suitable correction terms based on his observations. Also, I didn't notice his mention of other constants like Ln(2) at the end. As I had used a different approach, I thought this would be a valid exercise and decided not to included the link to Valentin's mini-challenge, as it prevent the solutions I was expecting to appear. But again, no problem!

As I am at it, I decided to apply the same approach to Valentin's problem. The continued fraction correction term is even more simple and easy to implement using a few steps:

1/(N + 1/(4*N))

Valentin's original program (two correction terms) can be rewritten using the same number of steps:

Code:


# --------------------------------------------
# HEWLETT·PACKARD 15C Simulator program
# Created with version 3.3.00
# --------------------------------------------
# --------------------------------------------

   000 {             } 
   001 {    42 21 11 } f LBL A
   002 {          36 } ENTER
   003 {       44 25 } STO I
   004 {    44 40 25 } STO + I
   005 {           4 } 4
   006 {       44  0 } STO 0
   007 {          20 } ×
   008 {          15 } 1/x
   009 {          40 } +
   010 {          15 } 1/x
   011 {           0 } 0
   012 {    42 21  0 } f LBL 0
   013 {    42  5 25 } f DSE I
   014 {       45  0 } RCL 0
   015 {          16 } CHS
   016 {       44  0 } STO 0
   017 {    45 10 25 } RCL ÷ I
   018 {          40 } +
   019 {    42  5 25 } f DSE I
   020 {       22  0 } GTO 0
   021 {          40 } +
   022 {       43 32 } g RTN

# --------------------------------------------

Like the program for Ln(2), 66 terms are required for the best 10-digit result for pi, 3.141592654.

Just for the record, here are my programs (Dropbox link)

Again, it was not my intention to consciously re-post an old third-party problem. At least in one occasion I tried to solve a problem I didn't had solved at the time, but then I would make it explicitly clear (as in message #20 of this thread)

Best regards,

Gerson.

P.S.: This correction term will give 10 correct digits for only 22 terms of the series for pi, same as in Paul Dale's non-published HP-42S program:

1/(88 + 1/(22 + 1/22))

The first terms of the continued fraction term for the series for pi appear to be:

1/(4*N + 1/(N + 1/(N + (9/(4*N + 16/N)))))

For N = 1000, this correction term will give 30+ correct digits.

[Dave Britten]

Just for fun, here it is for the 20S, a (GASP!) algebraic model. Whenever I code for the 20S, I usually end up having to abuse its features/quirks in unusual ways, and this one is no different. It's been a couple years since I dug into it, though, so there's probably still room for improvement. This completed in just under 10.5 minutes, and yielded a result of 6.93097183E-1.

01- LBL A
02- CLRG
03- 1
04- STO 0
05- E
06- 4
07- STO 4 (Prepare the trickery)
08- LBL 0
09- x
10- RCL 0
11- +/-
12- STO 0
13- =
14- 1/x
15- STO+ 1
16- SIGMA- (Trickery)
17- x=0?
18- GTO 1
19- GTO 0
20- LBL 1
21- RCL 1
22- RTN

Basically, I'm banking on SIGMA- being faster than 1, +/-, RCL+ 4, STO 4. I haven't actually tested that hypothesis yet, mind you.

[Gerson W. Barbosa]

(03-21-2014 01:52 AM)Dave Britten Wrote:  Basically, I'm banking on SIGMA- being faster than 1, +/-, RCL+ 4, STO 4. I haven't actually tested that hypothesis yet, mind you.

I guess it should slower, considering the extra calculations involved. My 21-step HP-12C version takes 2 minutes on my HP-12C+ (not the fastest one around). Using Sigma- to decrease the counter made it 52 seconds slower (and one step longer, but that was a quick modification).
Anyway, that was a nice trick to save a few steps on the HP-20S. Also, 10 minutes appear to be fast enough. Years ago a co-worker offered me an HP-20S in very good shape for a low price - I feel now I should have taken it.

Thank you for the unexpected algebraic program!

Gerson.

[Dave Britten]

(03-21-2014 04:57 AM)Gerson W. Barbosa Wrote:  

(03-21-2014 01:52 AM)Dave Britten Wrote:  Basically, I'm banking on SIGMA- being faster than 1, +/-, RCL+ 4, STO 4. I haven't actually tested that hypothesis yet, mind you.

I guess it should slower, considering the extra calculations involved. My 21-step HP-12C version takes 2 minutes on my HP-12C+ (not the fastest one around). Using Sigma- to decrease the counter made it 52 seconds slower (and one step longer, but that was a quick modification).
Anyway, that was a nice trick to save a few steps on the HP-20S. Also, 10 minutes appear to be fast enough. Years ago a co-worker offered me an HP-20S in very good shape for a low price - I feel now I should have taken it.

Thank you for the unexpected algebraic program!

Gerson.

Strangely enough, I tried it again with the more straight-forward approach (1, STO- 4, RCL 4), and it runs in pretty much the same amount of time.

The 20S is a pretty nice machine with some cool tricks up its sleeve. It's a shame they don't make it anymore, because it's really good for a simple algebraic model.

To go even further off the beaten path, here it is again for the 17BII solver:

X=\SIGMA(N:10000:1:-1:INV(N)*(-1)^(N+1))

Nice and concise, and it runs in about 8.5 minutes (I was expecting it to be quicker than that, though, with the tight inner loop presumably being handled by SysRPL code).

And of course, the RPL version, which runs in 5.5 minutes on my 48SX:

\<< 0 10000 1 FOR N N INV -1 N 1 + ^ * + -1 STEP \>>

Everything gets so much simpler when you have high-level looping constructs at your disposal.

[Shawn Gibson]

(03-21-2014 01:04 PM)Dave Britten Wrote:  

(03-21-2014 04:57 AM)Gerson W. Barbosa Wrote:  I guess it should slower, considering the extra calculations involved. My 21-step HP-12C version takes 2 minutes on my HP-12C+ (not the fastest one around). Using Sigma- to decrease the counter made it 52 seconds slower (and one step longer, but that was a quick modification).
Anyway, that was a nice trick to save a few steps on the HP-20S. Also, 10 minutes appear to be fast enough. Years ago a co-worker offered me an HP-20S in very good shape for a low price - I feel now I should have taken it.

Thank you for the unexpected algebraic program!

Gerson.

Strangely enough, I tried it again with the more straight-forward approach (1, STO- 4, RCL 4), and it runs in pretty much the same amount of time.

The 20S is a pretty nice machine with some cool tricks up its sleeve. It's a shame they don't make it anymore, because it's really good for a simple algebraic model.

To go even further off the beaten path, here it is again for the 17BII solver:

X=\SIGMA(N:10000:1:-1:INV(N)*(-1)^(N+1))

Nice and concise, and it runs in about 8.5 minutes (I was expecting it to be quicker than that, though, with the tight inner loop presumably being handled by SysRPL code).

And of course, the RPL version, which runs in 5.5 minutes on my 48SX:

\<< 0 10000 1 FOR N N INV -1 N 1 + ^ * + -1 STEP \>>

Everything gets so much simpler when you have high-level looping constructs at your disposal.

Dave/Gerson,
I ran Daves 20S code on my 20S and came up with the same result but it took 13 minutes. Does execution time depend on battery value?

I also "ported" Daves 20S program to my 34S:
LBL 'SRS'
CLRREGS
1
STO 00
EEX
4
STO 04
LBL '00'
ENTER
RCL 00
+/-
STO 00
*
1/x
STO+ 01
1
1/X
RCL+ 04
STO 04
X=0?
GTO '01'
GTO '00'
LBL '01'
RCL 01
END

On the WP34S it ran in 27 seconds.

[Dave Britten]

(03-21-2014 03:53 PM)Shawn Gibson Wrote:  Dave/Gerson,
I ran Daves 20S code on my 20S and came up with the same result but it took 13 minutes. Does execution time depend on battery value?

That's interesting. I've never heard of that happening, but it's certainly a possibility.

Other factors to consider: this was the only program I had in memory, and display settings were all at default, except for setting ALL mode (I had just put in new batteries after it had been dormant for some time).

As an addendum, I ran the 17BII solver equation on my 200LX (stock CPU speed), and got a result in about 3.25 minutes. I'll probably try it on my 19BII later just to be more thorough than necessary.

[Thomas Klemm]

(03-21-2014 03:53 PM)Shawn Gibson Wrote:  I also "ported" Daves 20S program to my 34S:
(...)
On the WP34S it ran in 27 seconds.

This might be a little faster:

Code:

LBL'SRS'
0
RCL Y
EVEN?
+/-
1/x
+
DSZ Y
BACK 006
END

Cheers
Thomas

[Gerson W. Barbosa]

(03-21-2014 06:28 PM)Thomas Klemm Wrote:  

(03-21-2014 03:53 PM)Shawn Gibson Wrote:  I also "ported" Daves 20S program to my 34S:
(...)
On the WP34S it ran in 27 seconds.

This might be a little faster:

Code:

LBL'SRS'
0
RCL Y
EVEN?
+/-
1/x
+
DSZ Y
BACK 006
END

Cheers
Thomas

22.2 seconds.

A slight modification will drop this to 20.4 s:

Code:

LBL'SRS'
0
RCL Y
(-1)ˣ
RCL/ Z
+
DSZ Y
BACK 005
+/-
END

Cheers,

Gerson.

[Shawn Gibson]

(03-21-2014 06:28 PM)Thomas Klemm Wrote:  This might be a little faster:

Code:

LBL'SRS'
0
RCL Y
EVEN?
+/-
1/x
+
DSZ Y
BACK 006
END

Cheers
Thomas

22.2 seconds.

A slight modification will drop this to 20.4 s:

Code:

LBL'SRS'
0
RCL Y
(-1)ˣ
RCL/ Z
+
DSZ Y
BACK 005
+/-
END

Cheers,

Gerson.
[/quote]
You guys are amazing! Now I have to go through your code to see how you did it.
Best Regards
Shawn

[Gerson W. Barbosa]

(03-22-2014 12:59 AM)Shawn Gibson Wrote:  You guys are amazing! Now I have to go through your code to see how you did it.
Best Regards
Shawn

Well, mine was just a slight modification of Thomas Klemm's program. But we can easily break the 20-second barrier on the WP 34S:

Code:


001 LBL A
002 0
003 #001
004 +/- 
005 RCL/ Z
006 STO+ Y
007 x<> L
008 DSE Z
009 BACK 005
010 x<> Y
011 END

Unlike Thomas Klemm's original program, N has to be even otherwise the sign of the result will be inverted.

10000 A --> 0.6930971830599453 (16.9 seconds, but I guess the limit hasn't been reached yet -- the WP 34S has a rich instruction set)

Back to HP-only calculators, here is the HP-42S version, but it should take about 18 minutes to run:

Code:


00 { 27-Byte Prgm }
01>LBL "S"
02 1E4
03 0
04 1
05>LBL 00
06 +/-
07 RCL÷ ST Z
08 STO+ ST Y
09 Rv
10 LASTX
11 DSE ST Z
12 GTO 00
13 X<>Y
14 .END.

Best regards,

Gerson.

[Thomas Klemm]

(03-22-2014 03:02 AM)Gerson W. Barbosa Wrote:  I guess the limit hasn't been reached yet -- the WP 34S has a rich instruction set

What about:

Code:

LBL 00
(-1)ˣ
RCL/ L
END

10000.001
\(\sum\) 00

[Paul Dale]

Nice.


- Pauli

[Gerson W. Barbosa]

(03-22-2014 05:12 AM)Thomas Klemm Wrote:  

(03-22-2014 03:02 AM)Gerson W. Barbosa Wrote:  I guess the limit hasn't been reached yet -- the WP 34S has a rich instruction set

What about:

Code:

LBL 00
(-1)ˣ
RCL/ L
END

10000.001
\(\sum\) 00

Hello Thomas,

Only some observations:
- this is item (a) of the original exercise;
- a manual +/- is required;
- it takes too long: 4 min 6 sec.

Because of its conciseness that's what I had been using for testing purposes until your reply to Shawn's post (I remember you suggested me a similar sequence for evaluating a summation, early this year).

It returns 0.6930971830599453, however, same as before. (I think that's because the extra 18 guarding digits in single precision mode).

Item (b) would be something like

Code:


LBL A
+/-
RCL+ 00
(-1)ˣ
RCL/ L
END

10001 STO 00
10.001
\(\sum\) 00
+/-

will return 0.6930971830599452 in single precision mode after 4 min 11 sec.

A greater difference between both results should be expected in double precision mode, thus demonstrating Dr. Wirth's point in his exercise.

Cheers,

Gerson.

[Thomas Klemm]

Now I'm confused.

(03-22-2014 12:47 PM)Gerson W. Barbosa Wrote:  - this is item (a) of the original exercise;

10000.001
\(\sum\) 00
This counts down from 10000 to 1. Isn't that what we want in (b)?

(03-22-2014 12:47 PM)Gerson W. Barbosa Wrote:  - a manual +/- is required;

Here's another solution:

Code:

LBL 00
EVEN?
+/-
1/x
END

(03-22-2014 12:47 PM)Gerson W. Barbosa Wrote:  - it takes too long: 4 min 6 sec.

That's a lot more that I had expected.

(03-22-2014 12:47 PM)Gerson W. Barbosa Wrote:  Item (b) would be something like

Code:


LBL A
+/-
RCL+ 00
(-1)ˣ
RCL/ L
END

10001 STO 00
10.001
\(\sum\) 00
+/-

I get: No such Label
Even using \(\sum\) A doesn't make much sense.

Cheers
Thomas

[Gerson W. Barbosa]

(03-22-2014 02:52 PM)Thomas Klemm Wrote:  Now I'm confused.

(03-22-2014 12:47 PM)Gerson W. Barbosa Wrote:  - this is item (a) of the original exercise;

10000.001
\(\sum\) 00
This counts down from 10000 to 1. Isn't that what we want in (b)?

My mistake, sorry!

The summation syntax is neatly explained in Walter's printed manual, at page 124/244, I should have checked instead of assuming it worked the way I imagined. I would quote it here for the benefit of others who, like me, are not familiarized with it, but there's a copyright notice that prevents me from doing so without prior written permission from the author (I think I've unwillingly infringed this in a couple of occasions). Anyway, this might match the previous pdf version publicly available at SourceForge.

(03-22-2014 02:52 PM)Thomas Klemm Wrote:  

(03-22-2014 12:47 PM)Gerson W. Barbosa Wrote:  - a manual +/- is required;

Here's another solution:

Code:

LBL 00
EVEN?
+/-
1/x
END

Size-wise, this is great! Too bad the long running time.

(03-22-2014 02:52 PM)Thomas Klemm Wrote:  

(03-22-2014 12:47 PM)Gerson W. Barbosa Wrote:  - it takes too long: 4 min 6 sec.

That's a lot more that I had expected.

I take you're using the emulator. In this case, an "actual calculator speed" option would be nice.

(03-22-2014 02:52 PM)Thomas Klemm Wrote:  

(03-22-2014 12:47 PM)Gerson W. Barbosa Wrote:  Item (b) would be something like

Code:


LBL A
+/-
RCL+ 00
(-1)ˣ
RCL/ L
END

10001 STO 00
10.001
\(\sum\) 00
+/-

I get: No such Label
Even using \(\sum\) A doesn't make much sense.

Summation and label copied & pasted from your post without adaption. This should have been
...
10000.001
\(\sum\) A
...

Well, it would make sense if summation worked like I imagined it did :-)

Cheers,

Gerson.

[Marcus von Cube]

(03-22-2014 05:17 PM)Gerson W. Barbosa Wrote:  I take you're using the emulator. In this case, an "actual calculator speed" option would be nice.

No chance! We do not emulate the real hardware or processor. Instead, the same C code base has been compiled on different platforms (Windows, Linux, MacOS, ARM). In fact, the Windows version predates the actual hardware port. So there is no way to determine how the hardware would behave performance-wise for any given piece of code.