optimized prime factor finder for HP-32s

[Don Shepherd]

In this thread, Dave Britten presented excellent prime factor finders for both the HP-20s and HP-32sii. This was also implemented on the HP-30b by Tim Wessman. Katie Wasserman pointed out that faster results will be obtained (on machines like the 30b and 32sii) by moving the most frequently-called subroutines to the top of code.

I recently acquired an HP-32s, a very beautiful machine. I wanted to implement the optimized algorithm on the 32s and reduce the label count if possible, since labels are a valuable resource on these machines. I was able to eliminate the V label (which was required because the 32s does not have a x<=y instruction like the 32sii) by reversing the order of variables M and F on the stack and using x>y, and I was able to eliminate the X label by simplifying the logic involved with displaying the final factor.

Here is the code that works on the HP-32s:

optimized prime factor program for HP-32s

Usage:

num to factor

xeq f

r/s to see all factors

0 = done

lbl w

rcl + f

sto f

rcl x

x<->y

/

fp

x=/=0

rtn

rcl x

rcl / f

sto x

sqrt

ip

sto m

view f

0

goto w

lbl z

4

xeq w

2

xeq w

4

xeq w

2

xeq w

4

xeq w

6

xeq w

2

xeq w

6

xeq w

rcl x

ln

x=0

rtn

rcl f

rcl m

x>y

goto z

rcl x

sto f

view f

clx

rtn

lbl f

sto x

sqrt

ip

sto m

0

sto f

2

xeq w

1

xeq w

2

xeq w

2

xeq w

rcl x

ln

x=0

rtn

goto z

[Pablo P (Spain)]

Hi Don, a time ago I wrote a program in the HP 35s to factorize numbers. I am curious, how long it takes to factorize 999,983 in the HP 32s?

[Don Shepherd]

Pablo, that takes exactly 15 seconds.

[Pablo P (Spain)]

HP 35s takes 18.2 seconds using a modified version of Dave Britten's program.

Basically, I rewrote the original program to use one label, simplified the logic involved with displaying the final factor and replaced each appearance of 2, 4 and 6 with RCL D, RCL C, RCL S respectively.

The last is because in the HP 35s putting a number directly is 1.62 times slower than recalling a variable. In fact without doing this, the program takes 25 seconds to calculate the factors of 999,983 (by the way, does this happen in other calc?)

| Line | Instruction |

|------+-------------|

| F001 | LBL F       |

| F002 | STO X       |

| F003 | SQRT        |

| F004 | IP          |

| F005 | STO M       |

| F006 | 0           |

| F007 | STO F       |

| F008 | 2           |

| F009 | STO D       |

| F010 | XEQ F054    |

| F011 | 1           |

| F012 | XEQ F054    |

| F013 | RCL D       |

| F014 | XEQ F054    |

| F015 | RCL D       |

| F016 | XEQ F054    |

| F017 | RCL X       |

| F018 | LN          |

| F019 | x=0?        |

| F020 | RTN         |

| F021 | 4           |

| F022 | STO C       |

| F023 | 6           |

| F024 | STO S       |

| F025 | RCL C       |

| F026 | XEQ F054    |

| F027 | RCL D       |

| F028 | XEQ F054    |

| F029 | RCL C       |

| F030 | XEQ F054    |

| F031 | RCL D       |

| F032 | XEQ F054    |

| F033 | RCL C       |

| F034 | XEQ F054    |

| F035 | RCL S       |

| F036 | XEQ F054    |

| F037 | RCL D       |

| F038 | XEQ F054    |

| F039 | RCL S       |

| F040 | XEQ F054    |

| F041 | RCL X       |

| F042 | LN          |

| F043 | x=0?        |

| F044 | RTN         |

| F045 | RCL M       |

| F046 | RCL F       |

| F047 | x=<y?       |

| F048 | GTO F025    |

| F049 | RCL X       |

| F050 | STO F       |

| F051 | VIEW F      |

| F052 | CLx         |

| F053 | RTN         |

| F054 | RCL+ F      |

| F055 | STO F       |

| F056 | RCL X       |

| F057 | x<>y        |

| F058 | /           |

| F059 | FP          |

| F060 | X!=0?       |

| F061 | RTN         |

| F062 | RCL X       |

| F063 | RCL/ F      |

| F064 | STO X       |

| F065 | SQRT        |

| F066 | IP          |

| F067 | STO M       |

| F068 | VIEW F      |

| F069 | 0           |

| F070 | GTO F054    |

Edited: 7 July 2010, 11:48 a.m.

[Don Shepherd]

Quote:

---

HP 35s takes 18.2 seconds

---

I'm surprized it's that fast! I did some benchmarks on the 35s a few years ago and noticed it was markedly slower in executing programs than its predecessor, the 33s. Running the unoptimized algorithm on the 33s for 999,983 takes 10 seconds; optimizing the program by moving the W and Z subroutines to the top of memory (before Lbl F) would probably take a second or two off that, at the most.

Quote:

---

I rewrote the original program to use one label

---

Ah, you took advantage of a feature available in the 35s but unavailable in the 32s or 33s. I wish that was available in the 32s, but wishing just won't make it come true!

Quote:

---

in the HP 35s putting a number directly is 1.62 times slower than recalling a variable

---

Interesting. I'll have to modify my 32s program to do that and see if it makes a timing difference. I'll do that and let you know.

[Pablo P (Spain)]

Quote:

---

...and I was able to eliminate the X label by simplifying the logic involved with displaying the final factor.

---

Basically you fused LBL W with LBL X and replaced XEQ X with VIEW F, isn't it? At least this is what I did.

As this is so simple I am wondering why did not Dave do it? So I am asking if this modification is correct. (I have not had time to study carefully the original algorithm).

[Don Shepherd]

Quote:

---

As this is so simple I am wondering why did not Dave do it? So I am asking if this modification is correct.

---

When I looked at the code around the original label x:

x=0

goto x

rtn

lbl x

I realized that that whole goto/lbl could be avoided if I changed the x=0 to x!=0. But then I saw the reference to xeq x over at the end of the z routine, and I knew this would have to change if I eliminated label x, obviously. So then I considered that the end of the label z routine is really the end of the program, which has the net effect (although achieved in a rather roundabout way) of displaying the final factor which is still in x, if you reach that point in the code. So, yes, I basically replaced xeq x with view f, and that seemed to have the effect I wanted and it made the end-of-file logic clearer, at least to me.

Now, why didn't Dave do it that way too? I suspect because he adapted his programs for the 32sii and 20s from an existing HP-67 program that did MORE than just find prime factors, and considering the other functions that that program had, there was probably a reason that the original programmer did xeq x and handled end-of-file that way. Dave also had an extra label that was unnecessary (Lbl A for the 20s and Lbl Y for the 32sii) in this code that was undoubtedly in the original code and Dave just left it there in case it was necessary here, which is is not since there are no other references to A or Y.

The other label I got rid of, Lbl V (which a followup poster in the original thread listed as a solution to the problem that the 32s has no x<=y), could be safely deleted by changing the order of variables M and F on the stack and using x>y. The followup poster probably considered this option but was unsure if changing the stack order would harm the rest of the program, and I looked at it and determined that it wouldn't. As you know, changing the order of things on the stack sometimes goofs everything up, but sometimes it has no effect, as in this case (I hope and think!).

I'm pretty sure these changes are correct. I've tested them with a bunch of numbers that are prime and not prime and it still seems to give me the correct factorization.

Don

Edited: 7 July 2010, 6:33 p.m.