HP Articles Forum

[Return to the Index ]
[ Previous | Next ]

Prime factors for HP-17bii solver -- a new approach

Posted by Don Shepherd on 4 Sept 2011, 7:08 p.m.

The original prime factor finder for the HP-17bii solver is documented in the Technical Applications Manual for the HP-27S and HP-19B beginning on page 52. The routine works very well, but it is very slow for large numbers (as stated on page 54). The slowness is a result of the solver's inability to exit a loop early, when a factor is found. The loop must run up to the square root of the number to be factored. This can be observed by running that program with input number 6,469,693,230. Factors 2, 3, 5, and 7 are found quickly, but factor 11 takes a long time (a bit less than 2 minutes). The remaining factors of 13, 17, 19, 23, and 29 are found more quickly than factor 11.

It turns out that there is a way to exit a loop early: simply perform an invalid instruction, like LOG(0), and the solver execution will terminate with the message SOLUTION NOT FOUND. But, if you store the value of interest in a menu variable immediately before you perform LOG(0), you can RCL that value after the error message is displayed. This implementation takes advantage of that trick.

Usage:

1. You may want to turn BEEP off.
2. Enter the number to factor, press N.
3. Press FACT.
4. When it finds the factor it will beep and display SOLUTION NOT FOUND.
5. Press RCL FACT to see the factor.
6. Repeat steps 3-5 to see the remaining factors.
7. You are done when you don't get the error message and FACT= appears with the final factor (you don't have to RCL the final factor).

The advantages of this program over the original program are:

1. It finds factors faster by exiting the main loop (by terminating execution) as soon as a factor is found.
2. It is much shorter than the original.

The only disadvantage is getting used to RCL FACT to see each factor (except the final factor).

Here is the solver equation for the 17b and 17bii. This equation will not work on the 17bii+ because it changes input N as factors are found, and the 17bii+ solver does not correctly handle changes to menu variables.

   IF(MOD(N:2)=0:L(FACT:2)+L(N:N/2)+LOG(0):
      (I:3:(N):2:
        IF(MOD(N:I)=0:L(FACT:I)+L(N:N/I)+LOG(0):0)
       )+N
     )-FACT

I just obtained an HP-19b and ran this equation on that machine and discovered a very nice surprize. When a factor is found, it still beeps and displays SOLUTION NOT FOUND, but you don't have to press RCL FACT to see the factor, it appears automatically. Not only that, the original N appears after the last factor.

Edited: 4 Oct 2011, 10:41 a.m.

[ Return to the Message Index ]

Go back to the main exhibit hall