ULAM Bizarre #2 - The power of HP 42S STO/RCL arithmetic
Message #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.
| 
Go back to the main exhibit hall