HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution



#34

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.


..


#35

Is this with the WP34?


#36

Yes, wp34s.

#37

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.


#38

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.


#39

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!


#40

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


#41

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.


#42

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. :-)

#43

Quote:
but that would give me far too much credit!

It surely is the other way around, but thanks anyway :-)

#44

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


#45

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...


#46

There is an issue, however. See my edited post above. Nice try, anyway :-)


#47

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.


#48

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 :-)


#49

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.


#50

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


#51

I vote for returning a zero when either x or y are zero.


#52

Change committed, wait for the next build.


- Pauli


#53

I've just committed a new build (3303)


#54

Thanks Walter, Pauli & Marcus. Now I will be able to compute equivalent impedances using this function, when one of the components is zero :-)

#55

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.


#56

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.

#57

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.


#58

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 :-)


#59

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.


#60

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.


#61

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.

#62

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.


#63

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.

#64

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.


#65

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


#66

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


Possibly Related Threads…
Thread Author Replies Views Last Post
  [HP-PIRME] BUG Pretty Print, Solution: abs => |...|, ABS => ||...|| CompSystems 2 2,244 12-13-2013, 09:36 AM
Last Post: CompSystems
  Shutdown with the Apps key and more than 10 variables in a program. Davi Ribeiro de Oliveira 10 3,974 11-05-2013, 01:26 PM
Last Post: Han
  [PRIME] RPN: another attempt at returning more than one value to the RPN stack Marcus von Cube, Germany 5 2,536 11-05-2013, 02:44 AM
Last Post: Marcus von Cube, Germany
  HHC 2013 RPN Programming Challenge - Final Thought Jeff O. 7 2,463 10-17-2013, 11:02 AM
Last Post: Jeff O.
  Updated PPC DVD Version 2.10: HP-41 Searchable Program Files and Scannable Barcode Jake Schwartz 3 1,938 09-27-2013, 09:51 PM
Last Post: Olivier (Wa)
  HHC 2013 programming contest winners Brian Walsh 52 13,069 09-26-2013, 11:39 PM
Last Post: David Hayden
  Box left at HHC Tim Wessman 1 1,644 09-26-2013, 11:05 PM
Last Post: Wlodek Mier-Jedrzejowicz
  HHC 2013 speakers' files Joe Horn 2 1,668 09-26-2013, 02:51 AM
Last Post: Geoff Quickfall
  HHC 2013 Day 2 Highlights Eddie W. Shore 6 2,655 09-23-2013, 04:03 PM
Last Post: Kimberly Thompson
  HHC 2013: Day 1 Highlights Eddie W. Shore 28 8,136 09-23-2013, 03:22 PM
Last Post: Brad Barton

Forum Jump: