HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution (/thread-232750.html) HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution - Jeff O. - 10-11-2012 The HHC 2012 RPN Programming Contest seems to be the gift that keeps on giving, for me at least. Despite doubts expressed in my "...Conundrum" thread regarding improving on my previous 12-step best, let alone equaling or bettering Paul's 11-step program, I was able to do both. I obviously failed miserably regarding my intention to stop trying. My 12-step previous best was based on the following equation: steps between two points = (D2+D1) * (D2-D1+1)/2 - (y1 - y2) - D1 where D2 = x2+y2 and D1= x1 + y1 This can be transformed into the following equation: steps between two points = (D2^2 - D1^2 + D2 - D1)/2 + y2 - y1 I managed to write a 10 step program implementing the above as follows: ``` X Y Z T L I beginning values in stack -> y2 x2 y1 x1 - - 001 <>YTXZ re-order stack for next step, enables x2 x1 y2 y1 - - complex add to create D1 and D2 simultaneously 002 CPX+ Complex add to create D2 in X, D2 D1 y2 y1 x2 x1 D1 in Y, y2 and y1 still in Z and T 003 CPX x^2 create D2^2-D1^2 in X (also 2xD1xD2 in D2^2-D1^2 2D1*D2 y2 y1 D2 D1 Y, not needed) 004 RCL+L Add D2 from register L (Last X) D2^2-D1^2+D2 2D1*D2 y2 y1 D2^2-D1^2 D1 005 RCL-I subtract D1 which is still in register I D2^2-D1^2+D2-D1 2D1*D2 y2 y1 D2^2-D1^2+D2 D1 (Last Y from CPX x^2 operation) 006 <>XZTY re-order stack D2^2-D1^2+D2-D1 y2 y1 2D1*D2 D2^2-D1^2+D2 D1 007 2 enter 2 2 D2^2-D1^2+D2-D1 y2 y1 D2^2-D1^2+D2 D1 008 / divide by 2 (D2^2-D1^2+D2-D1)/2 y2 y1 y1 2 D1 009 + add y2 D2^2-D1^2+D2-D1)/2+y2 y1 y1 y1 (D2^2-D1^2+D2-D1)/2 D1 010 RCL-Y subtract y1 (D2^2-D1^2+D2-D1)/2+y2-y1 ``` I guess the only new technique used above, or at least a technique which I do not believe was used in any other solutions, is taking advantage of the fact that complex operations copy the Y value into I but subsequent real operations do not alter the I register, so it can be used later. Also, was there a consensus reached that L (and hopefully by extension I) count as stack registers and so the above would be considered all-stack?? Of course my original equation can also be transformed into the above form, so I might have gotten there eventually had I not read and gained insights from the Forum posts. But I doubt it. I also fully acknowledge that Paul or Dave or many others could have gotten to 10 steps had they kept at it as long as I did. Hopefully, this will be my last word. Thanks for the challenge Gene. .. Re: HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution - Eddie W. Shore - 10-11-2012 Is this with the WP34? Re: HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution - Gerson W. Barbosa - 10-11-2012 Quote: I guess the only new technique used above, or at least a technique which I do not believe was used in any other solutions, is taking advantage of the fact that complex operations copy the Y value into I but subsequent real operations do not alter the I register, so it can be used later. Great insight! I'll use your technique in my previous 11-step solution in order to make it one step shorter: ```001 y<> Z 002 CSTO 00 003 C+ 004 Cx2 005 RCL+ L 006 RCL- I 007 2 008 / 009 RCL+ 00 010 RCL- 01 ``` Gerson. Re: HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution - Gerson W. Barbosa - 10-11-2012 Or, using only the stack: ```001 y<> YTXZ 002 C+ 003 Cx2 004 RCL+ L 005 RCL- I 006 y<> T 007 2 008 / 009 RCL+ Z 010 RCL- Y ``` P.S.: Turns out this is now equivalent to Jeff's!!! Edited: 11 Oct 2012, 10:44 a.m. Re: HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution - Jeff O. - 10-11-2012 Yes, wp34s. Re: HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution - Jeff O. - 10-11-2012 Quote: Turns out this is now equivalent to Jeff's!!! I would say that great minds think alike, but that would give me far too much credit! Re: HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution - David Hayden - 10-11-2012 Fantastic solution, Jeff! One possibility that I haven't seen is using the summation functions in a creative way to solve this problem. Has anyone taken that approach? As for the I and L registers, since they get clobbered regularly by stack operations, I think that using them counts in the spirit of an "all stack" solution. After all, the benefit of using only the stack is that you don't have to use any of the global registers 00-99. And while we're on the subject of not using registers 00-99, if you haven't discovered local registers yet (see the LocR command) you should check them out. There's little reason to use global registers for temporary storage in programs at all now. Dave Re: HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution - Gerson W. Barbosa - 10-11-2012 Quote: but that would give me far too much credit! It surely is the other way around, but thanks anyway :-) Belated 9-Step Solution (BLTN:-) - Gerson W. Barbosa - 10-11-2012 ```001 y<> YTXZ 002 C+ 003 Cx2 004 RCL+ L 005 RCL- I 006 STO Y 007 || 008 + 009 RCL- Y ``` Won't work when x1 = x2 and y1 = y2 though. Edited: 11 Oct 2012, 12:36 p.m. after one or more responses were posted Re: Belated 9-Step Solution (BLTN:-) - Jeff O. - 10-11-2012 The parallel function! That's the way to divide by 2 without entering a 2 and dividing (or enter # 0.5 and multiplying)! I knew there had to be a way. Surely no 8 step is possible... Re: Belated 9-Step Solution (BLTN:-) - Gerson W. Barbosa - 10-11-2012 There is an issue, however. See my edited post above. Nice try, anyway :-) Re: Belated 9-Step Solution (BLTN:-) - Jeff O. - 10-11-2012 So close, but yes, that will cause a divide by zero. But perhaps there still a 9 step solution that accepts all arguments out there. Re: HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution - Jeff O. - 10-11-2012 Thanks Dave. Regarding use of the summation function, Gerson used it here in a 15C solution. It would be worth a look for a wp34s solution. I agree about the L and I registers, since they are updated by operations on the stack without any active user STO operations, they count as stack registers. Entirely in the XYZT stack might be called an “XYZT”-only solution. As for the use of local registers, I will admit to having not discovered them. I sort-of tuned out a lot of that stuff when wp34s went from v2 to v3. I’ll have to take a look sometime. Re: Belated 9-Step Solution (BLTN:-) - Gerson W. Barbosa - 10-11-2012 From the fine wp34s manual: ```|| Returns (1/x + 1/y)^(-1), being very useful in electrical engineering especially. ``` Shouldn't this return zero when x = y = 0? I never used this function to compute the equivalent resistance of two 0-ohm resistors connected in parallel. However I think I wouldn't find it very useful in EE if the answer was different from zero :-) Re: Belated 9-Step Solution (BLTN:-) - Walter B - 10-11-2012 Mathematically, you're definitively right. For x and y approximating zero, || approximates zero as well. On the WP 34S, it would require an exception handling for one or both x and y equalling zero. Re: Belated 9-Step Solution (BLTN:-) - Gerson W. Barbosa - 10-11-2012 The limit is zero when either x, y, or both, tend to zero. Something similar occurs with the SINC function: it returns 1 when x = 0 and sin(x)/x otherwise. The manual doesn't mention the exception however. Edited to correct a mistake as per Valentin's observation below Edited: 12 Oct 2012, 10:52 a.m. after one or more responses were posted Re: HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution - Marcus von Cube, Germany - 10-11-2012 I 'invented' local registers because I wanted to implement recursive algorithms. This was the main driver that led to version 3 of the WP 34S firmware. Local registers use the subroutine return stack which shares memory with the area used for program steps. The longer the program the smaller the remaining area for local data or subroutine levels. Since global registers become less important for intermediate storage, I added an option to reduce the number of global registers in favor of the remaining memory for local data. If you move your program to the flash library almost all memory can be used for local (dynamic) data. I think we maxed out the available resources. :-) Re: Belated 9-Step Solution (BLTN:-) - Marcus von Cube, Germany - 10-11-2012 I vote for returning a zero when either x or y are zero. Re: Belated 9-Step Solution (BLTN:-) - Paul Dale - 10-11-2012 Change committed, wait for the next build. - Pauli Re: Belated 9-Step Solution (BLTN:-) - Paul Dale - 10-11-2012 I thought a complex multiply would be usable here, but hadn't worked out how. I didn't think of the parallel operation though. - Pauli Edited: 11 Oct 2012, 6:24 p.m. Re: Belated 9-Step Solution (BLTN:-) - Marcus von Cube, Germany - 10-11-2012 I've just committed a new build (3303) Re: Belated 9-Step Solution (BLTN:-) - Gerson W. Barbosa - 10-11-2012 Yes, complex multiply, together with your idea of using complex addition, helps a lot: ```(a2 + a) - (b2 + b) = a2 - b2 - b + a = Re((a + i*b)2) - b + a x2 RCL+ L x<> Y x2 RCL+ L - ``` Compared to the implementation above, it saves one step here: ``` C+ Cx2 CRCL L - - ``` Jeff has managed to save yet another step here: ``` C+ Cx2 RCL+ L RCL- I ``` Quote: I didn't think of the parallel operation though. Because you didn't need it, I guess. I cannot locate your 11-step solution right now, but I think the divide-by-two operation was not an issue, stack-wise.A HALF(x) function, were it available, would always save one step. Also, it would be useful in many situations. This has been suggested, I think, by I don't remember what the response was. Gerson Re: Belated 9-Step Solution (BLTN:-) - Gerson W. Barbosa - 10-11-2012 Thanks Walter, Pauli & Marcus. Now I will be able to compute equivalent impedances using this function, when one of the components is zero :-) Re: Belated 9-Step Solution (BLTN:-) - Gerson W. Barbosa - 10-11-2012 Quote: Surely no 8 step is possible... I've accidentally removed the reference to the possible 8-step in my original message, sorry! I said I would not be surprised if you or anyone else came up with an 8-solution. Well, if a HALF(x) or 2/ function were availabe, then that would surely be possible. Integer halving and doubling used to be important operations, but perhaps not anymore. 2* of course is not necessary, as we know. It's just STO+ X or RCL+ X. 3* is RCL+ X RCL+ L (two steps, but no stack-lift). Gerson. Re: Belated 9-Step Solution (BLTN:-) - Paul Dale - 10-12-2012 I wanted to include basic arithmetic operations with small integers. Essentially an arithmetic equivalent of the # nnn operation. This would give divide by two. I've also been tempted to added a function to produce triangular numbers which would have shortened solutions. Assuming I've not screwed it up: ``` 01 [<->] YTXZ x2 x1 y2 y1 02 [cmplx]+ s2 s1 y2 y1 si = xi + yi 03 TRIANG t2 s1 y2 y1 ti = si'th triangular number 04 [<->] YXTZ s1 t2 y1 y2 05 TRIANG t1 t2 y1 y2 06 [cmplx]+ p1 p2 y1 y2 pi = ti + yi = distance from origin 07 - p2-p1 ``` All most, as is the parallel solution since firmware updates aren't allowed. - Pauli Re: Belated 9-Step Solution (BLTN:-) - Jeff O. - 10-12-2012 That was more of a challenge than anything else. With current firmware, 8 would be two steps better than the current minimum. Seems unlikely, but I would not rule it out. First let's get to 9 steps :-) Re: Belated 9-Step Solution (BLTN:-) - Valentin Albillo - 10-12-2012 Hi, Gerson_ Quote: The limit is zero when either x, y, or both, tend to zero. Something similar occurs with the SINC function: it returns 1 when x = 1 and sin(x)/x otherwise. You mean "it returns 1 when x = 0", right ? ... :D Best regards from V. Re: Belated 9-Step Solution (BLTN:-) - Gerson W. Barbosa - 10-12-2012 Hello Valentin, Quote: You mean "it returns 1 when x = 0", right ? ... :D Yes! Thanks for the correction. It's just been fixed. I'd like to call it a typo, but I cannot as '0' and '1' are in opposite positions on the keyboard. Sorry for my lack of attention. Best regards, Gerson. Re: Belated 9-Step Solution (BLTN:-) - Gerson W. Barbosa - 10-12-2012 Hello Jeff, Quote: With current firmware, 8 would be two steps better than the current minimum. The 9-step solution works perfectly on Marcus's new build (3303). I've just tried it on the emulator. Needless to say, this 9-step solution would not have been possible without your discovery of the effect of complex operations on the register I. Unlike your outstanding independent 10-step solution, mine relies on third party's ideas. Here is it again, with due credits, for the record: ```001 y<> YTXZ ; Paul Dale 002 C+ ; Paul Dale 003 Cx2 004 RCL+ L 005 RCL- I ; Jeff O. 006 STO Y 007 || 008 + 009 RCL- Y ``` I appreciate your efforts in doing this one on your own and ultimately finding a technique the rest of us had missed. Gerson. Re: Belated 9-Step Solution (BLTN:-) - Jeff O. - 10-12-2012 Thank you for your kind words Gerson. Your 9-step program using the revised parallel instruction is a pretty, tight piece of code. Regarding my efforts, I was doing so for fun, so I got what I was after. I'm quite pleased that our efforts resulted in a new firmware revision with the improved parallel command. A fine legacy of the HHC 2012 RPN Programming Contest. Re: Belated 9-Step Solution (BLTN:-) - Gerson W. Barbosa - 10-12-2012 Quote: Your 9-step program using the revised parallel instruction is a pretty, tight piece of code. Thanks, but this is just the result of teamwork as I recognize :-) Quote: I'm quite pleased that our efforts resulted in a new firmware revision with the improved parallel command. A fine legacy of the HHC 2012 RPN Programming Contest. Exactly my feelings! That's really an unexpected and welcome by-product of the HHC 2012 RPN Programming Contest. I had already used | | in a program before for another purpose, but I didn't notice the problem then. Re: Belated 9-Step Solution (BLTN:-) - David Hayden - 10-13-2012 Quote: Well, if a HALF(x) or 2/ function were available, then that would surely be possible. If X is an integer, you can multiply and divide by any power of 2 with the SL and ASR (shift left and arithmetic shift right) commands). Does that help create an 8 step solution? Dave Edited: 13 Oct 2012, 10:21 a.m. Re: Belated 9-Step Solution (BLTN:-) - Gerson W. Barbosa - 10-13-2012 No, because these instructions are not available in the default decimal mode. According to rule #4, IIRC, the calculator should start from the default settings and return to it in case of mode changes. That would allow for another 10-step solution that would have been accepted at Nashville however, unlike the 9-step one (because | | had an issue at the time). ```001 y<> YTXZ 002 C+ 003 Cx2 004 RCL+ L 005 RCL- I 006 BASE 10 007 ASR 1 008 RCL+ Z 009 RCL- T 010 DECM ``` We've been trying to optimize it beyond your winning 12-step solution just for fun, has Jeff has pointed out. These of course don't compare to the optimized solution you came up with within the few available hours before the contest was over. Gerson. Edited: 13 Oct 2012, 1:23 p.m.