(12C) Prime Factorization
11-23-2019, 03:04 AM (This post was last modified: 11-24-2019 02:20 AM by Don Shepherd.)
Post: #1
 Don Shepherd Senior Member Posts: 713 Joined: Dec 2013
(12C) Prime Factorization
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

Code:
 01 sto 0    number to factor 02 clr sigma    clears R1 for trial factor use 03 1        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 2 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 5        reset indirect pointer to 5 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 goto 57    see if current trial factor is again a factor
11-23-2019, 03:23 AM
Post: #2
 Paul Dale Senior Member Posts: 1,601 Joined: Dec 2013
RE: (12C) Prime Factorization
Couldn't the final two steps be replaced by goto 57?

Pauli
11-23-2019, 03:45 AM (This post was last modified: 11-24-2019 01:56 AM by Don Shepherd.)
Post: #3
 Don Shepherd Senior Member Posts: 713 Joined: Dec 2013
RE: (12C) Prime Factorization
(11-23-2019 03:23 AM)Paul Dale Wrote:  Couldn't the final two steps be replaced by goto 57?

Pauli

Hi Pauli, thanks.

It looks like that change would work, but the 2010 post is archived and cannot be changed so I'd have to do some cutting and pasting into a new post, which I'd rather not do. There are three additional changes I wanted to make back in 2010 (to reduce the number of indirect registers by 1) but I couldn't make the changes because of the archive status. Those changes didn't really affect the speed or functionality of the program anyhow.

UPDATE: I'm going to remove the link to the archived article (that can't be updated) and post the revised code in its place--to include Pauli's suggestion and also use one fewer register for indirect addressing.

Don
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)