optimized prime factor finder for HP-32s Don Shepherd Unregistered Posts: 1,392 Threads: 142 Joined: Jun 2007 07-06-2010, 01:38 PM 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) Unregistered Posts: 41 Threads: 9 Joined: Mar 2010 07-07-2010, 08:34 AM 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 Unregistered Posts: 1,392 Threads: 142 Joined: Jun 2007 07-07-2010, 10:20 AM Pablo, that takes exactly 15 seconds. Pablo P (Spain) Unregistered Posts: 41 Threads: 9 Joined: Mar 2010 07-07-2010, 11:41 AM 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 | | 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 Unregistered Posts: 1,392 Threads: 142 Joined: Jun 2007 07-07-2010, 03:32 PM 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) Unregistered Posts: 41 Threads: 9 Joined: Mar 2010 07-07-2010, 05:23 PM 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 Unregistered Posts: 1,392 Threads: 142 Joined: Jun 2007 07-07-2010, 06:23 PM 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. « Next Oldest | Next Newest »

 Possibly Related Threads… Thread Author Replies Views Last Post HP Prime Collect/Factor difference bluesun08 3 1,505 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 2,525 09-23-2013, 04:39 PM Last Post: Julián Miranda (Spain) 33s, 35s & 42s--The Timex(R) Factor Matt Agajanian 7 2,266 09-13-2013, 12:28 AM Last Post: Matt Agajanian HP 32s LCD part Trisnadi Sutrisno 2 1,427 08-27-2013, 02:12 PM Last Post: Han HP-32S II Expansion Matt Agajanian 14 3,783 07-21-2013, 10:19 PM Last Post: Matt Agajanian HP 32S-II Vertical Curve Program Ron Cardwell 2 1,400 05-20-2013, 07:54 AM Last Post: Thomas Klemm HP-32S/33S/35S emulator with Stack Overflow sensing/Stack display x34 3 1,601 10-26-2012, 04:56 PM Last Post: x34 Finding the largest prime factor on the 15c Evan Gates 2 1,256 10-03-2012, 11:17 AM Last Post: Thomas Klemm HP-41's ARCL on the 32S-II Matt Agajanian 2 1,191 05-04-2012, 04:45 PM Last Post: Matt Agajanian Tips & Programs for the 32S Matt Agajanian 0 854 03-16-2012, 02:24 AM Last Post: Matt Agajanian

Forum Jump: