optimized prime factor finder for 12c+



#2

Well, Dave Britten started this ball rolling here with a prime factor finder for the 32sii and 20s based upon an original program for the 67. Tim Wessman used this as a model for the 30b in message number 30 of that thread. I made a few modifications here for the 32s, a very nice machine. But I always wondered if this basic algorithm could be done on the 12c, and especially the fast 12c+.

At first glance, it would appear unlikely because of the heavy reliance on subroutines, which the 12c does not have. But the more I looked at the code, the more I believed that it should be possible to somehow implement this algorithm on the 12c+. Yesterday I figured out how to do it, essentially using indirect addressing via the Rcl CFj command with the cash flow registers.

The code is listed below. The 12c+ is rather slower than the 30b for this application: the 30b determines the primality of 300,000,007 in 9 seconds versus the 12c+ 38 seconds. But this algorithm represents a significant improvement over a brute-force algorithm that eliminates only multiples of 2 from the trial factor pool; that version takes 57 seconds on the 12c+.

The fact that an algorithm that is so subroutine-intensive can be done on the 12c+ at all is a testament to the greatness of the design of the 12c. No wonder it is the most successful calculator HP has ever produced.

Edited on 9/20/2010 to implement Katie Wasserman's suggestion to use Nj in addition to CFj so that no preloading of registers is necessary, a brilliant suggestion.

Prime factors program for 12c+

Eliminates multiples of 2, 3, and 5 from trial factor pool

These are the trial factor increment values that are stored
via cfj and nj in R2 to R7:
6,2,6,4,2,4,2,4,2,2,1,2

Enter number to factor, R/S
R/S after each factor displayed
0 indicates done

maximum number to factor = 999,999,999

Register usage:
R2 - R7 (and corresponding nj) = trial factor increments, begins at R7
R0 - number to factor
R1 - current trial factor
n - used to control indirect addressing
i - flag for returning to the right location from
the routine at line 56

Mem command = p-71 r-11

01 sto 0 number to factor
02 clr sigma clears R1 for trial factor use
03 2 load trial factor increment values into cfj/nj
04 sto n registers R2 to R7
05 6
06 cfj
07 2
08 nj
09 6
10 cfj
11 4
12 nj
13 2
14 cfj
15 4
16 nj
17 2
18 cfj
19 4
20 nj
21 2
22 cfj
23 nj
24 1
25 cfj
26 2
27 nj
28 0 loop begins here to get next series of trial factor increment values
29 sto i flag so you return to the correct line number from routine at line 56
30 rcl nj get the next trial factor increment value
31 goto 56 check to see if this is a factor
32 1
33 sto i flag to return to the correct line number from line 56 routine
34 rcl cfj get the next trial factor increment value
35 goto 56 check to see if this is a factor
36 rcl n when n gets to 2, an iteration of loop is done
37 3
38 x<=y
39 goto 28 loop not done, so continue loop with next increment
40 rcl 0 if num to factor is 1, you are done factoring
41 ln will be 0 if num to factor is 1
42 x=0
43 goto 00 display 0 and exit program
44 6 reset indirect pointer to 6 for second
45 sto n and all subsequent loop iterations
46 rcl 0 number to factor
47 rcl 1 current trial factor
48 enter
49 x no x-squared key on 12c so this does it
50 x<=y continue loop until you get to
51 goto 28 the square root of the number to factor
52 rcl 0 the final factor is in R0 now so display
53 R/S it, then display 0 and stop
54 0
55 goto 00
56 sto+1 beginning of routine to see if this is a factor, increment trial divisor
57 rcl 0 current number to factor
58 rcl 1 current trial divisor
59 /
60 frac frac part will be 0 if R1 is a factor of R0
61 x=0
62 goto 67 if a factor
63 rcl i 0=return to line 32, 1=return to line 36
64 x=0
65 goto 32
66 goto 36
67 rcl 1 factor found, so update number to factor
68 sto/0 update number to factor
69 r/s display factor wait for user to press r/s
70 0 don't increment trial factor, might be same factor again
71 goto 56 see if current trial factor is again a factor


Edited: 21 Sept 2010, 1:00 p.m.


#3

Very cool. I shied away from doing it on a 12c because of the lack of subroutines. Getting it running on the algebraic 20s was enough of a challenge. :)

I might have to try this on my standard 12c and see how much more slowly it runs.


#4

Yeah, given the extensive use of subroutines in the algorithm, for a long time I thought it was just not possible to consider it on the 12c. But when I thought about the indirect addressing using Cfj, I thought there might be a way, and I found one! But it originally required loading all 12 of the trial factor increment values prior to running the program, which was definitely not cool. Then Katie said that if you use Nj in addition to Cfj you would need half as many registers and the extra program space that would free up would probably be adequate to initialize the registers you do need, and she was right. What a brilliant suggestion.

Katie also had the idea of stuffing all 12 increment values into one register using the 10-digit number and 2-digit exponent. That would free up all kinds of registers for program lines, but the mechanics of decoding that single register each time, including the exponent, would probably impact the execution speed, and I thought the Nj was a better method, so I did that.

It runs very quickly on the 12c+, not as fast as the 30b, but certainly acceptable. I've also got it running on my original 12c from 12 years ago, and it is ssssllllloooooowwwww on that machine, predictably.

But the challenge was to do that algorithm at all on the 12c, and I am happy with the result.

Yes, I did appreciate your algebraic solution on the 20s, that was very clever. And I do like the display on that machine, very clear.

So thanks Dave for resurrecting this old 67 code. I've also got it running on my 65, which handles the subroutines very well, of course.

Don


Possibly Related Threads...
Thread Author Replies Views Last Post
  HP Prime Collect/Factor difference bluesun08 3 927 10-29-2013, 09:36 AM
Last Post: Eddie W. Shore
  33s, 35s & 42s--The Timex(R) Factor Matt Agajanian 7 1,289 09-13-2013, 12:28 AM
Last Post: Matt Agajanian
  Finding the largest prime factor on the 15c Evan Gates 2 774 10-03-2012, 11:17 AM
Last Post: Thomas Klemm
  35s prompt for multi-character variables in program like "low footprint" root finder Chris C 8 1,851 02-14-2012, 06:52 PM
Last Post: Chris C
  WP34S: Valentin Albillo's Polynomial Root Finder Miguel Toro 28 4,286 11-23-2011, 07:39 PM
Last Post: Miguel Toro
  FWIW - km to miles conversion factor on a four-banger calculator Gerson W. Barbosa 37 5,305 10-19-2011, 03:49 PM
Last Post: Martin Pinckney
  HP 12C, 12C Platinum & 15C iOS App Walter Lam 2 851 06-02-2011, 01:25 PM
Last Post: Andrés C. Rodríguez (Argentina)
  optimized prime factor finder for HP-32s Don Shepherd 6 1,348 07-07-2010, 06:23 PM
Last Post: Don Shepherd
  Form factor for calculators David Hayden 58 6,416 11-13-2009, 09:15 AM
Last Post: Patrick Rendulic
  MCODE - Prime Twin Finder - RFF (Request For Feedback) PeterP 0 482 07-20-2008, 01:19 PM
Last Post: PeterP

Forum Jump: