(35S) - prime factors - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Software Libraries (/forum-10.html) +--- Forum: General Software Library (/forum-13.html) +--- Thread: (35S) - prime factors (/thread-2454.html) (35S) - prime factors - Dirk E. - 11-20-2014 02:28 PM 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 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 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>< 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>< 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>< 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 ...?