▼
Posts: 875
Threads: 37
Joined: Jul 2005
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.
..
▼
Posts: 764
Threads: 118
Joined: Aug 2007
▼
Posts: 875
Threads: 37
Joined: Jul 2005
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
▼
Posts: 875
Threads: 37
Joined: Jul 2005
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!
▼
Posts: 528
Threads: 40
Joined: Dec 2008
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
▼
Posts: 875
Threads: 37
Joined: Jul 2005
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.
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
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. :-)
Posts: 2,761
Threads: 100
Joined: Jul 2005
Quote:
but that would give me far too much credit!
It surely is the other way around, but thanks anyway :-)
Posts: 2,761
Threads: 100
Joined: Jul 2005
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
▼
Posts: 875
Threads: 37
Joined: Jul 2005
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...
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
There is an issue, however. See my edited post above. Nice try, anyway :-)
▼
Posts: 875
Threads: 37
Joined: Jul 2005
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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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 :-)
▼
Posts: 4,587
Threads: 105
Joined: Jul 2005
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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
I vote for returning a zero when either x or y are zero.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
Change committed, wait for the next build.
- Pauli
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
I've just committed a new build (3303)
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Thanks Walter, Pauli & Marcus. Now I will be able to compute equivalent impedances using this function, when one of the components is zero :-)
Posts: 1,755
Threads: 112
Joined: Jan 2005
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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
▼
Posts: 875
Threads: 37
Joined: Jul 2005
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 :-)
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
▼
Posts: 875
Threads: 37
Joined: Jul 2005
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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
Posts: 528
Threads: 40
Joined: Dec 2008
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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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.
Posts: 3,229
Threads: 42
Joined: Jul 2006
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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
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
|