(35S) - prime factors

[Dirk E.]

Since I learned from the 35s bug list how easy it is to loose all programs, I think shorter is better.

This program doesn't preserve the RPN stack, but therefore it's faster to enter and needs less other registers. There are some really nice procedures around here in the forum to save and restore the stack, and one can build a factors list by replacing the result display stops.

The last factor may be displayed (rather redundantly) as "1", this happens because I left only one test for the exit condition to make the main loop shorter. My HP 35s found the second factor of 7 x 3851 x 6221 after 1:37 min.

There are three loops - the first checking factors 2 and 3, then the second for factor 5, the third 7, the second again 11, the third 13 and so on...
Of course the user should know himself that the whole works only for natural numbers which fit into the HP 35s' 12 digits.

HP 35s - Prime factorization - test 7x3851x6221 second factor after 1'37"

- usage: nnn XEQ P002 - 0 pf1 - R/S - ... 1 pfN
- global registers, MOD 6 loop (7.Feb.2015 - RPN ln=143 ck=6626)
X: 'unknown', T: factor to test, RPN stack

================================================================================​
P001 LBL P
P002 STO X
P003 2
;loop P004..P017 - Test 2 and 3 as factors
P004 STO T
P005 RCL X
P006 RCL T
P007 RMDR
P008 x!=0?
P009 GTO P014
P010 RCL T
P011 STO/ X
P012 STOP ;y=0, x='T'
P013 GTO P005 ;try factor again

P014 RCL T
P015 3
P016 x!=y?
P017 GTO P004
P018 STO/ T ;'T':=1

;loop P019..P035 - 15(17) lines per 2(6) i.e. 75(85) per 10(30) test divides
P019 4
P020 STO+ T ;'T':=6n-1
P021 RCL X
P022 RCL T
P023 RMDR
P024 X=0?
P025 GTO P040

P026 2
P027 STO+ T ;'T':=6n+1
P028 RCL T
P029 RCL X
P030 RCL/ T
P031 x<y? ;'X/T'<'T' or 'X'<'T'^2
P032 GTO P044 ;-> End
P033 FP
P034 x!=0?
P035 GTO P019 ;-> next factor
P036 RCL T
P037 STO/ X
P038 STOP ;y=0, x='T'
P039 GTO P028 ;try factor again

P040 RCL T
P041 STO/ X
P042 STOP ;y=0, x='T'
P043 GTO P021 ;try factor again

P044 1
P045 RCL X
P046 RTN ;y=1, x='X'

Since I was always convinced that the control overhead would cost more than what you gain leaving out also test divisions by multiples of 5, I didn't really try before - when I got my first WP34S two weeks ago, I felt challenged to do it though. The main loop of the above will run 15 lines and skip two for each two factor candidate divisions.
In the primer below I tried everything to gain speed - compare to the previously saved integer part of "X" ' square root should be faster than a complete float compare; also the three lines RCL X - RCL T - RMDR should run faster than RCL X - RCL/ T - FP. Anyway It seems that the use of ISG and the indirect register call in place of a constant eat up almost all of the advantage. (And I don't know whether the position in the memory makes a difference - maybe, I'd have to reset the calculator and enter just the one program for time comparisons?)
The following program's main loop tests only 8 factors from a sequence of 30 natural numbers while the above tests 10, for those 8 it runs 69 and skips 9 lines while the above runs 75 and skips 10 lines for the whole 10 tests. This should give an advantage of 7%, but I took 1:34 min to find the second factor of 7 x 3851 x 6221, which is only 2% less and seems a rather marginal win for entering 18 more lines and using 13 more registers:

Code:

HP 35s - Prime factorization - test 7x3851x6221 second factor after 1'34"

- usage: nnn XEQ R002 - 0 pf1 - R/S - ... 1 pfN
- global and indirect registers, MOD 30 loop (7.Feb.2015 - RPN ln=210 ck=EC83)
- Registers: X: 'unknown', T: Test factor, S: [sqrt(X)], RPN stack
 I: pointer/loop counter, ind.00-10: steps between factors

========================================
R001 LBL R
R002 STO X
R003 0.01       ;prepare for MOD30 chain
R004 STO I      ;of test divisions
R005 1
R006 STO(I)
R007 ISG I
R008 2
R009 STO T      ;first test factor btw.
R010 STO(I)
R011 ISG I
R012 STO(I)
R013 ISG I
R014 4
R015 STO(I)
R016 ISG I
R017 2
R018 STO(I)
R019 ISG I
R020 4
R021 STO(I)
R022 ISG I
R023 2
R024 STO(I)
R025 ISG I
R026 4
R027 STO(I)
R028 ISG I
R029 6
R030 STO(I)
R031 ISG I
R032 2
R033 STO(I)
R034 ISG I
R035 6
R036 STO(I)
R037 10
R038 STO- I
R039 GTO R043   ;skip 3 lines

R040 RCL T
R041 STO/ X     ;leave remaining nnn
R042 STOP       ;show factor
R043 RCL X
R044 SQRT()
R045 IP
R046 STO S      ;SQRT(X) for fast end test

R047 RCL X     ;main loop 7x8(9)+13(15) lines
R048 RCL T      ;for 8(10) test candidates
R049 RMDR       ;i.e. 69 lines for 8("10"/30)
R050 x=0?
R051 GTO R040
R052 RCL(I)
R053 STO+ T     ;next T
R054 ISG I
R055 GTO R047
R056 8
R057 STO- I
R058 RCL S
R059 RCL T
R060 x<=y?      ;T<=sqrt(X) -> continue
R061 GTO R047

R062 1          ;indicator 'End'
R063 RCL X
R064 RTN

On the WP 34S I ran further tests, and found it preserves the subroutine stack almost as stable as the programs. Since my tests ended with the first or second factor, I found some trash left on the subroutine stack and consider it better to avoid subroutines if possible.
A few tests with the HP 35s and the HP 42s showed that a manual GTO, XEQ or OFF clears the subroutine stack, thus on these models the MOD 30 routine that Dave presented will less mess up this stack.
Tus to be able to compare the speed of XEQ/RTN against the RCL(I)/ISG used above, I tried the MOD 30 with subroutine way, too. It ran significantly faster, although the main loops run nearly the same number of lines.

Code:

HP 35s - Prime factorization - test 7x3851x6221 second factor after 1'18.7"

- usage: nnn XEQ R002 - 0 pf1 - R/S - ... 1 pfN
- subroutine, integer compare, global registers, MOD 30 loop (8.Feb.2015)
X: 'unknown', T: factor to test, S: [sqrt(X)], RPN stack    (RPN ln=169 ck=F157)

================================================================================​
R001  LBL R
R002  GTO R017

R003  STO+ T    ;loop subroutine, also display
R004  RCL X
R005  RCL T
R006  RMDR
R007  x!=0?
R008  RTN
R009  RCL T
R010  STO/ X
R011  STOP      ;y=0, x=T
R012  RCL X
R013  sqrt(X)
R014  IP        ;value for end condition
R015  STO S
R016  GTO R004  ;try factor again

R017  STO X
R018  sqrt(X)
R019  IP        ;value for end condition
R020  STO S
R021  1
R022  STO T     ;for first test w. T=2
R023  XEQ R003
R024  1         ;test 3
R025  XEQ R003
R026  2         ;test 5
R027  XEQ R003
R028  2         ;test 7
R029  XEQ R003
   ;loop R030..R049 - 8x8+4=68 lines per 8(30) test divides
R030  4
R031  XEQ R003
R032  2
R033  XEQ R003
R034  4
R035  XEQ R003
R036  2
R037  XEQ R003
R038  4
R039  XEQ R003
R040  6
R041  XEQ R003
R042  2
R043  XEQ R003
R044  6
R045  XEQ R003
R046  RCL S
R047  RCL T
R048  x<y?
R049  GTO R030

R050  1
R051  RCL X     ;y=1, x=X
R052  RTN

When I looked through the WP 34S library 'PF' routine I felt challenged to do the factorization on the HP 35s without using any registers except the RPN stack, too. It's possible, but costs additional steps and thus time. The slight stack manipulation helped to keep it in reasonable size.

Code:

HP 35s - Prime factorization - test 7x3851x6221 second factor after 1'47"

- usage: nnn XEQ Q002 - 'nnn/pf1' pf1 - R/S - ... '1' pfN
- RPN stack only - MOD 6 loop (15.Feb.2015 - RPN ln=181 ck=AA66)
- 'REGY' key sequence: [(yellow)f] [MEM] [Rv] [ENTER]

================================================================================​
Q001  LBL Q                                   ; ( L ),  x ,  y ,  z ,  t
Q002  2                                       ; (   ),  2 , 'X'
   ;loop Q003..Q020 - Test 2 and 3 as factors
Q003  REG Y     ;duplicate 'X'                ; (   ), 'X', 'T', 'X'
Q004  REG Y     ;duplicate 'T'                ; (   ), 'T', 'X', 'T', 'X'
Q005  RMDR                                    ; ('T'),  ? , 'T', 'X'
Q006  x!=0?
Q007  GTO Q013
Q008  +                                       ; (   ), 'T', 'X0'
Q009  /                                       ; ('T'), 'X1'
Q010  LASTx                                   ; ('T'), 'T', 'X'
Q011  STOP      ;y='X1', x='T'
Q012  GTO Q003  ;try factor again

Q013  CLx                                     ; ('T'),  0 , 'T', 'X'
Q014  3                                       ; ('T'),  3 , 'T', 'X'
Q015  x=y?      ;'T'=3?
Q016  GTO Q021
Q017  x><y                                    ; ('T'), 'T',  3 , 'X'
Q018  CLx                                     ; ('T'),  0 ,  3 , 'X'
Q019  +                                       ; (   ),  3 , 'X'
Q020  GTO Q003
Q021  /                                       ; (   ),  1 , 'X'
Q022  ENTER                                   ; (   ),  1 ,  1 , 'X'
  ;loop Q023..Q041 - 17(19) lines per 2(6) i.e. 85(95) per 10(30) test divides
Q023  CLx                                     ; (   ),  0 , 'T', 'X'
Q024  4                                       ; (   ),  4 , 'T0', 'X'
Q025  +         ;'T':=6n-1                    ; (   ), 'T1', 'X'
Q026  REG Y     ;duplicate 'X'                ; (   ), 'X', 'T', 'X'
Q027  REG Y     ;duplicate 'T'                ; (   ), 'T', 'X', 'T', 'X'
Q028  RMDR                                    ; ('T'),  ? , 'T', 'X'
Q029  x=0?
Q030  GTO Q047

Q031  CLx                                     ; ('T'),  0 , 'T', 'X'
Q032  2                                       ; ('T'),  2 , 'T0', 'X'
Q033  +         ;'T':=6n+1                    ; (   ), 'T1', 'X'
Q034  REG Y     ;duplicate 'X'                ; (   ), 'X', 'T', 'X'
Q035  REG Y     ;duplicate 'T'                ; (   ), 'T', 'X', 'T', 'X'
Q036  /                                       ; ('T'),  ? , 'T', 'X'
Q037   x<y?      ;'X/T'<'T' or 'X'<'T'^2
Q038   GTO Q052  ;-> End
Q039  FP
Q040  x!=0?
Q041  GTO Q023  ;-> next factor

Q042  +                                       ; ('T'), 'T', 'X0'
Q043  /                                       ; ('T'), 'X1'
Q044  LASTx                                   ; ('T'), 'T', 'X'
Q045  STOP      ;y='X1', x='T'
Q046  GTO Q034  ;try factor again

Q047  +                                       ; ('T'), 'T', 'X0'
Q048  /                                       ; ('T'), 'X1'
Q049  LASTx                                   ; ('T'), 'T', 'X'
Q050  STOP      ;y='X1', x='T'
Q051  GTO Q026  ;try factor again

Q052  CLx                                     ; ('T'),  0 , 'T', 'X'
Q053  REG Y                                   ; ('T'), 'T', 'T', 'X'
Q054  /                                       ; ('T'),  1 , 'X'
Q055  x><y                                    ; ('T'), 'X',  1 
Q056  RTN       ;y= 1 , x='X'

- The following seems to me showing the advantages of RPN quite well, and I think that it may fit here.
Thanks to Euklid it's not too hard to add the greatest common divisor and least common multiple functions found on other recent calculators. Having a simple example in front of me made it somewhat easier. Using only x, y and LastX, it just doesn't return with the correct "LASTx". (LCM here needs one global Register, but saves the correct LASTx.)

HP 35s - GCD (RPN: ck=87EC ln=30)

User entry - output:
nnnn1 ENTER nnnn2 XEC G - gcd(n1,n2)
- uses: LASTx

G001 LBL G
G002 RMDR
G003 x=0?
G004 GTO G008
G005 LASTx
G006 x><y
G007 GTO G002
G008 CLx ;prevent automatic Stack Lift
G009 LASTx
G010 RTN

HP 35s - LCM (RPN: ck=F8E6 ln=27)

User entry - output:
nnnn1 ENTER nnnn2 XEC L - lcm(n1,n2)
- uses: GCD (above), X, G (gcd result)

L001 LBL L
L002 STO G
L003 x><y
L004 STO X
L005 XEC G002
L006 STO/ X ;X := (previousY)/gcd
L007 x>< G ;G := gcd
L008 RCLx X ;LASTx := previous X
L009 RTN

Here's added a second approach using 2 storage registers (similiar to the above lcm) but providing the LASTx for gcd, too, also combining both under one label:

Code:

HP 35s - GCD, LCM (RPN: ck=3E22 ln=72)

User entry - output:
nnnn1 ENTER nnnn2  XEC G002  - gcd(n1,n2)
- uses: G (gcd result)

nnnn1 ENTER nnnn2  XEC G003  - lcm(n1,n2)
- uses: X, G (gcd result)

G001 LBL G
G002 GTO G012
G003 STO X      ;back-up 1st number - ### LCM routine ###
G004 x><y
G005 XEC G012
G006 LASTx
G007 x><y
G008 /
G009 x>< X
G010 RCLx X     ;1st number -> LASTx
G011 RTN

G012 STO G      ;back-up 2nd number - ### GCD routine ###
G013 RMDR
G014 x=0?
G015 GTO G019
G016 LASTx
G017 x><y
G018 GTO G013
G019 LASTx      ;result
G020 x>< G
G021 +          ;2nd number -> LASTx

G022 CLx        ;prevent automatic stack lift
G023 RCL G
G024 RTN

The bug list mentioned that checksum and length are pointless - my impression is, they are consistant as long the calculator remains in default state, maybe with display settings applied. Apparently there are internal flags stored invisibly if entering expressions in ALG mode, equations or fractional, complex, vector constants. And of course the checksum changes if a different Label is used. So my 35s remained in RPN, "RDX," and FIX 4 (although ALL might look nicer for integer calculations) - and you may compare these checksums to yours, if you put in just the same code.

...now turning to my WP3xS
Dirk

EDIT (7.Feb.2015): Reverted from a display Subroutine to separate Stops (6 more lines, though), added the indirect addressing exercise. (15.Feb.2015): added the MOD 30 with subroutine and the stack-only study.
_______________
Sanyo CZ1210, TI-66, fx-4500P, HP 15C LE, fx-5800P, HP 35s, WP 34S ...?