ULAM Bizarre #2 - The power of HP 42S STO/RCL arithmetic



#9

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.


#10

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.


#11

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

#12

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.


#13

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!

#14

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

#15

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.


#16

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


Possibly Related Threads…
Thread Author Replies Views Last Post
  Layout of arithmetic keys on early calculators Walter B 10 3,591 11-20-2013, 11:13 AM
Last Post: Jake Schwartz
  HP Prime Save Power Turn Off Not Working Timothy Roche 12 4,292 10-27-2013, 01:41 PM
Last Post: Michael de Estrada
  HP Prime Program: ULAM Eddie W. Shore 0 764 10-02-2013, 03:34 PM
Last Post: Eddie W. Shore
  Low power warning for HP-15C LE and batteries Nick_S 1 1,455 09-16-2013, 09:34 AM
Last Post: Hans Brueggemann
  HP Prime - How to STO in RPN mode? Javier Goizueta 10 2,828 08-18-2013, 10:24 PM
Last Post: Xavier A. (Brazil)
  HP 9845 option 200 power supply Dave F 2 1,667 05-30-2013, 08:10 AM
Last Post: Dave F
  Arithmetic programs for HP39gII Mic 0 1,017 12-19-2012, 12:23 PM
Last Post: Mic
  HP-87 power supply repair philippe_elie 0 945 11-18-2012, 11:12 AM
Last Post: philippe_elie
  HP-48: extract coefficient of power series Thomas Klemm 3 1,615 10-21-2012, 11:42 PM
Last Post: Han
  HP-41CV power problem Don Davis 2 1,330 10-11-2012, 09:13 PM
Last Post: Don Davis

Forum Jump: