The Museum of HP Calculators

HP Forum Archive 20

 ULAM Bizarre #2 - The power of HP 42S STO/RCL arithmeticMessage #1 Posted by Allen on 5 Feb 2011, 10:48 p.m. I was doodling yesterday in meeting, and found a closed-form solution to the 2008 Ulam Spiral mini-challenge that has been haunting me for three years from: this thread. Usage: Enter a Number (N) and execute the program. It will return the non-trivial solutions for adjacent numbers in Ulam's spiral. For example: ``` 17 yields 36, 38 16 yields 05, 35 14 yields 03, 33 13 yields 30, 32 example spiral: 37 36 35 34 33 32 31 38 17 16 15 14 13 30 . 18 05 04 03 12 29 . 19 06 01 02 11 28 . 20 07 08 09 10 27 . 21 22 23 24 25 26 . . . . . etc.. ``` If you're interested, I've made a Stack Diagram describing how the STAT registers and careful stack discipline can be combined to accumulate terms without local variables, and only using two numbers in the program. (integers 3 and 5) This program has a very concise check to see if . It returns and for corner numbers such as 31,37,43. Otherwise it returns and This closed form approach allows a 30% reduction in program space, AND an order of magnitude reduction in runtime. The new program is O(1) constant runtime, 37 bytes (28 steps max for all values with no looping)- The previous version from 2008 was O(N) and 54 bytes and 43 program lines with some considerable sized loops. ```' 37-byte HP 42S ULAM spiral solution Allen T. 2/5/2011 00 { 37-Byte Prgm } 01 LBL 00 02 CL\Sigma @ Clear Stat registers 03 ENTER 04 ENTER @ Fill the stack up with input 05 3 06 5 07 \Sigma+ @ add 3 and 5 to Stat regs 08 + @ add the 3 and 1 to get four 09 STOŚ ST T @ Put 4*N on level T 10 Rv @ ROLLDN 11 \Sigma+ @ Add N to each of the Stat regs 12 STO- ST Z @ Put 4N-2 on Stack level Z 13 R^ @ ROLLUP 14 +/- @ NEG 15 RCL+ ST T @ Put 4N-6 on Stack Level T 16 SQRT 17 IP 18 STO+ ST X @ find 2*floor(sqrt(4N-2)) < doubles the number in X without loosing STACK(T) 3 bytes same cost as "2 *" 19 R^ 20 SQRT 21 IP 22 STO+ ST X @ find 2*floor(sqrt(4N-6)) 23 X=Y? @ if the numbers are the same, then it's a SIDE 24 +/- @ Need to subtract 2* the Side number 25 ENTER 26 ABS 27 \Sigma+ @ Otherwise add 2*Side number to both stat regs 28 RCL 13 @ Recall SUM(Y) register 29 RCL 11 @ Recall SUM(X) Register 30 .END. ``` Thanks to Thomas for his tutorial on using formulas. I did not follow the teacher exactly, but managed to get the formulas here anyway. * NOTE - I do not believe this program is compatible with the HP41C due to the specific use of the linear stat register and the STO/RCL arithmetic (line 15). Caveat Emptor. Five Reasons I think this is a nice demonstration program for the 42S and RPN flexibility: ```1) Lines 04 and 09 allow use of STACK(T) copies as the lower stack items are consumed in operations 2) It's one of the very few RPN programs I've seen use both ROLLUP and ROLLDN 3) Byte-saving tricks like "STO+ ST X" to double a number without disturbing the stack. (Is there a better RPN way?) 4) Uses 3 stat registers rather than local variables 5) Wherever possible uses output from the STAT accumulator instead of entering numbers (byte conservation) ``` Edited: 5 Feb 2011, 11:11 p.m.

 Re: ULAM Bizarre #2 - The power of HP 42S STO/RCL arithmeticMessage #2 Posted by Don Shepherd on 6 Feb 2011, 3:06 a.m.,in response to message #1 by Allen Amazing work, Allen, congratulations. I was thinking about entering this code on my 32sii but I notice several references to things like STO * STO T and STO - STO Z. I assume these are 42s commands to put values directly on the stack, correct? And I don't believe these commands exist on the 32sii, is that correct? Many thanks for this great work in algorithm development.

 Re: ULAM Bizarre #2 - The power of HP 42S STO/RCL arithmeticMessage #3 Posted by Dieter on 6 Feb 2011, 7:21 a.m.,in response to message #2 by Don Shepherd Quote: I was thinking about entering this code on my 32sii but I notice several references to things like STO * STO T and STO - STO Z. The HP41-series offers direct access to the stack registers - they can be used in the same way as the usual numbered registers. So STO Z directly stores X in stack register Z, or ST+ T adds X to register T. This allows very effective programming and elegant solutions like ST+ X for doubling a number (even without affecting LastX). The 42s adds two more features: Since it can also use named storage registers a simple "STO T" might be confusing because it may refer to stack register T as well as a variable named T. That's why there's an additional "ST" for "stack" in commands referring to stack registers: STO T stores a value in variable T, while STO ST T stores it in the top stack tegister T. On the other hand, the 42s can also do all this with recall-arithmetics as well: RC+ ST Z adds the content of stack register Z to the value in X without affecting the stack otherwise. No, all this can't be done on the 32s and similar calculators. Dieter

 Re: ULAM Bizarre #2 - The power of HP 42S STO/RCL arithmeticMessage #4 Posted by Thomas Klemm on 6 Feb 2011, 5:00 a.m.,in response to message #1 by Allen Hi Allen You could reverse clearing the statistic registers and filling the stack thus saving one precious byte: ```02 ENTER @ Fill the stack up with input 03 CL\Sigma @ Clear Stat registers ``` Clearing the statistic registers enables the stack lift. Since 3 and 5 follow only one ENTER is needed. Furthermore you could replace the two last statements with SUM. This instruction uses two bytes as well, so no gain with that change, but this makes the program independent of the setting of \GSREG. However this instruction is missing in the HP-41C. Quote: Thanks to Thomas for his tutorial on using formulas. I did not follow the teacher exactly, but managed to get the formulas here anyway. Did you just save the images or did you find another ingenious way? In the latter case I could add it to the article. Which reminds me to add Egan's method he once posted as well. It's a clever idea to use the statistic functions for some kind of parallel processing. Kind regards Thomas Edited: 6 Feb 2011, 5:13 a.m.

 Re: ULAM Bizarre #2 - The power of HP 42S STO/RCL arithmeticMessage #5 Posted by Allen on 6 Feb 2011, 8:25 a.m.,in response to message #4 by Thomas Klemm Thomas, This is fantastic, Thanks! I made the change- yes even to save 1 byte. I also did not realize about the SUM function- I've always been concerned until now about making it independent of the REG settings- now I know how!! Don noted ULAM shows a correlation between meeting doodles and math.. perhaps I should go to more meetings!

 Re: ULAM Bizarre #2 - The power of HP 42S STO/RCL arithmeticMessage #6 Posted by Mark Storkamp on 6 Feb 2011, 1:22 p.m.,in response to message #1 by Allen I made it work with the 41C by changing line 15 from ```15 RCL+ ST T ``` to ```15 R^ 16 STO+ ST Y 17 Rv ```

 Re: ULAM Bizarre #2 - down to 32 bytesMessage #7 Posted by Allen on 7 Feb 2011, 12:26 a.m.,in response to message #6 by Mark Storkamp Mark, Thanks for your 41C Fix!! I made the output from FREE42 and used HP41UC to create a 41C barcode, then scanned it in using my wand- sure it may have been faster just to type the thing in, but I'm not sure how to type R^ in the 41c. Thomas, I incorporated your Stack lift saving 1 byte and SUM features, I also found a way to save 4 more bytes by getting rid of some of the 2-Byte STO+ instructions from above. Now it's down to 32 Bytes- Not sure I can do much better than that.

 Re: ULAM Bizarre #2 - down to 32 bytesMessage #8 Posted by Thomas Klemm on 7 Feb 2011, 8:03 a.m.,in response to message #7 by Allen Quote: but I'm not sure how to type R^ in the 41c Special characters are listed on the back of the calculator: So the keystrokes would be: XEQ ALPHA 7 Shift ENTER^ ALPHA HTH Thomas

Go back to the main exhibit hall