Programming Exercise (HP15C, 15C LE  and others)

03162014, 02:17 AM
(This post was last modified: 03162014 02:29 AM by Gerson W. Barbosa.)
Post: #1




Programming Exercise (HP15C, 15C LE  and others)
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 HP15C LE (you might not try this on the classic HP15C 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 HP15C 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 HP15C (or HP11C, 12C, 41C and other 10 or 12digit RPN calculator). Tip: try to find an empirical relationship between the number of terms and the error. Only as a reference, my HP15C 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! 

03162014, 05:23 AM
Post: #2




RE: Programming Exercise (HP15C, 15C LE  and others)
(03162014 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 HP15C Minichallenge: Speeding it up ! Quote:I took your HP11C program that sums an alternating series ... cf. Summation of infinite, alternating series Cheers Thomas 

03162014, 02:44 PM
(This post was last modified: 03162014 02:51 PM by Gerson W. Barbosa.)
Post: #3




RE: Programming Exercise (HP15C, 15C LE  and others)
Yes, I was aware of Valentin's minichallenge 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 HP42S 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. 

03172014, 12:43 AM
(This post was last modified: 03172014 12:54 AM by Gerson W. Barbosa.)
Post: #4




RE: Programming Exercise (HP15C, 15C LE  and others)
(03162014 05:23 AM)Thomas Klemm Wrote: I'm lazy and just leave a link to the HP15C Minichallenge: Speeding it up ! To those who haven't followed the link, that was Paul Dale replying to Valentin about a modification for the HP42S 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 HP42S version might be interesting, but I guess it's gone by now. (03162014 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 ith 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 28step program (on the HP11C) 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 2term continued fraction to correct the sum. The correct value to 16digit accuracy is 0.6931471805599453. Cheers, Gerson. 

03172014, 07:14 AM
(This post was last modified: 03182014 02:32 AM by Gerson W. Barbosa.)
Post: #5




RE: Programming Exercise (HP15C, 15C LE  and others)
(03162014 05:23 AM)Thomas Klemm Wrote: I'm lazy and just leave a link to the HP15C Minichallenge: 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 repost of Valentin's minichallenge 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 textbooks and decided to check the sums on a 10digit RPN calculator. At first I used an HP12C. 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 HP15C, 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 minichallenge 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 speedingup). 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 minichallenge, 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:
Like the program for Ln(2), 66 terms are required for the best 10digit result for pi, 3.141592654. Just for the record, here are my programs (Dropbox link) Again, it was not my intention to consciously repost an old thirdparty 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 nonpublished HP42S 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. 

03212014, 01:52 AM
Post: #6




RE: Programming Exercise (HP15C, 15C LE  and others)
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.93097183E1.
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. 

03212014, 04:57 AM
(This post was last modified: 03212014 04:58 AM by Gerson W. Barbosa.)
Post: #7




RE: Programming Exercise (HP15C, 15C LE  and others)
(03212014 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 21step HP12C version takes 2 minutes on my HP12C+ (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 HP20S. Also, 10 minutes appear to be fast enough. Years ago a coworker offered me an HP20S in very good shape for a low price  I feel now I should have taken it. Thank you for the unexpected algebraic program! Gerson. 

03212014, 01:04 PM
Post: #8




RE: Programming Exercise (HP15C, 15C LE  and others)
(03212014 04:57 AM)Gerson W. Barbosa Wrote:(03212014 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. Strangely enough, I tried it again with the more straightforward 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 highlevel looping constructs at your disposal. 

03212014, 03:53 PM
Post: #9




RE: Programming Exercise (HP15C, 15C LE  and others)
(03212014 01:04 PM)Dave Britten Wrote:Dave/Gerson,(03212014 04:57 AM)Gerson W. Barbosa Wrote: I guess it should slower, considering the extra calculations involved. My 21step HP12C version takes 2 minutes on my HP12C+ (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). 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. 

03212014, 05:07 PM
Post: #10




RE: Programming Exercise (HP15C, 15C LE  and others)
(03212014 03:53 PM)Shawn Gibson Wrote: Dave/Gerson, 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. 

03212014, 06:28 PM
Post: #11




RE: Programming Exercise (HP15C, 15C LE  and others)  
03212014, 07:09 PM
(This post was last modified: 03212014 07:17 PM by Gerson W. Barbosa.)
Post: #12




RE: Programming Exercise (HP15C, 15C LE  and others)
(03212014 06:28 PM)Thomas Klemm Wrote:(03212014 03:53 PM)Shawn Gibson Wrote: I also "ported" Daves 20S program to my 34S: 22.2 seconds. A slight modification will drop this to 20.4 s: Code: LBL'SRS' Cheers, Gerson. 

03222014, 12:59 AM
Post: #13




RE: Programming Exercise (HP15C, 15C LE  and others)
(03212014 06:28 PM)Thomas Klemm Wrote: This might be a little faster: 22.2 seconds. A slight modification will drop this to 20.4 s: Code: LBL'SRS' Cheers, Gerson. [/quote] You guys are amazing! Now I have to go through your code to see how you did it. Best Regards Shawn 

03222014, 03:02 AM
Post: #14




RE: Programming Exercise (HP15C, 15C LE  and others)
(03222014 12:59 AM)Shawn Gibson Wrote: You guys are amazing! Now I have to go through your code to see how you did it. Well, mine was just a slight modification of Thomas Klemm's program. But we can easily break the 20second barrier on the WP 34S: Code:
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 HPonly calculators, here is the HP42S version, but it should take about 18 minutes to run: Code:
Best regards, Gerson. 

03222014, 05:12 AM
Post: #15




RE: Programming Exercise (HP15C, 15C LE  and others)  
03222014, 11:50 AM
Post: #16




RE: Programming Exercise (HP15C, 15C LE  and others)
Nice.
 Pauli 

03222014, 12:47 PM
Post: #17




RE: Programming Exercise (HP15C, 15C LE  and others)
(03222014 05:12 AM)Thomas Klemm Wrote:(03222014 03:02 AM)Gerson W. Barbosa Wrote: I guess the limit hasn't been reached yet  the WP 34S has a rich instruction setWhat about: 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:
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. 

03222014, 02:52 PM
Post: #18




RE: Programming Exercise (HP15C, 15C LE  and others)
Now I'm confused.
(03222014 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)? (03222014 12:47 PM)Gerson W. Barbosa Wrote:  a manual +/ is required;Here's another solution: Code: LBL 00 (03222014 12:47 PM)Gerson W. Barbosa Wrote:  it takes too long: 4 min 6 sec.That's a lot more that I had expected. (03222014 12:47 PM)Gerson W. Barbosa Wrote: Item (b) would be something likeI get: No such Label Even using \(\sum\) A doesn't make much sense. Cheers Thomas 

03222014, 05:17 PM
Post: #19




RE: Programming Exercise (HP15C, 15C LE  and others)
(03222014 02:52 PM)Thomas Klemm Wrote: Now I'm confused. 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. (03222014 02:52 PM)Thomas Klemm Wrote:(03222014 12:47 PM)Gerson W. Barbosa Wrote:  a manual +/ is required;Here's another solution: Sizewise, this is great! Too bad the long running time. (03222014 02:52 PM)Thomas Klemm Wrote:(03222014 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. (03222014 02:52 PM)Thomas Klemm Wrote:(03222014 12:47 PM)Gerson W. Barbosa Wrote: Item (b) would be something likeI get: No such Label 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. 

03222014, 09:05 PM
Post: #20




RE: Programming Exercise (HP15C, 15C LE  and others)
(03222014 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 performancewise for any given piece of code. Marcus von Cube Wehrheim, Germany http://www.mvcsys.de http://wp34s.sf.net http://mvcsys.de/doc/basiccompare.html 

« Next Oldest  Next Newest »

User(s) browsing this thread: