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.
The advantages of this program over the original program are:
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