optimized prime factor finder for HP-32s



#8

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


#9

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?


#10

Pablo, that takes exactly 15 seconds.


#11

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.


#12

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.

#13

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).


#14

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.


Possibly Related Threads...
Thread Author Replies Views Last Post
  HP Prime Collect/Factor difference bluesun08 3 224 10-29-2013, 09:36 AM
Last Post: Eddie W. Shore
  Joys of eBay: HP-32S, HP-32SII, HP-42S, HP-16C, ... Sasu Mattila 7 334 09-23-2013, 04:39 PM
Last Post: Julián Miranda (Spain)
  33s, 35s & 42s--The Timex(R) Factor Matt Agajanian 7 323 09-13-2013, 12:28 AM
Last Post: Matt Agajanian
  HP 32s LCD part Trisnadi Sutrisno 2 202 08-27-2013, 02:12 PM
Last Post: Han
  HP-32S II Expansion Matt Agajanian 14 614 07-21-2013, 10:19 PM
Last Post: Matt Agajanian
  HP 32S-II Vertical Curve Program Ron Cardwell 2 219 05-20-2013, 07:54 AM
Last Post: Thomas Klemm
  HP-32S/33S/35S emulator with Stack Overflow sensing/Stack display x34 3 230 10-26-2012, 04:56 PM
Last Post: x34
  Finding the largest prime factor on the 15c Evan Gates 2 149 10-03-2012, 11:17 AM
Last Post: Thomas Klemm
  HP-41's ARCL on the 32S-II Matt Agajanian 2 167 05-04-2012, 04:45 PM
Last Post: Matt Agajanian
  Tips & Programs for the 32S Matt Agajanian 0 103 03-16-2012, 02:24 AM
Last Post: Matt Agajanian

Forum Jump: