HP Forum Archive 19

[ Return to Index | Top of Index ]

Another 30b program! Message #1 Posted by hugh steers on 21 Jan 2010, 6:19 p.m. Following Don's initiative, here's another 30b program ive only just got working. there's probably still a few rough edges, but it basically works. I've been trying to come up with something to show off the 30b's raw performance. so here is integer factorization (always a good one). It searches for a factor but, is unfortunately unable to spot if the number is prime. i could expand it to test this first, i guess. The tough bit was getting it to deal with numbers up to (10^12)/2, which it deals with in about 1 minute. ; Pollard Rho factoring ; HP30b calculator ; usage: enter a composite odd number ; run the program ; if it finds a factor (not necessarily the least), it will stop ; NOTE: the program does not terminate if the number is prime, ; except rarely with zero. ; Examples: ; 102691 (2 sec, 103) ; 1022117 (3 sec, 1013) ; 1071514531 (15 seconds, 32719) ; 1598880187 (21 seconds, 39989) ; 2620119269 (21 seconds, 39989) ; 4292870399 (65 seconds, 65519) ; 499898489929 (63 seconds, 707071) STO 0 ; n 1 STO 2 ; u = 1 STO 3; ; v = 1 LBL 01 RCL 2 ; u CALL08 ; FN(u) STO 2 ; u = fn(u) RCL 3 ; v CALL08 ; FN(v) CALL08 ; FN(FN(v)) STO 3 ; v=FN(FN(v)) RCL 2 ; u RCL-3 ; u-v; ENT GF 02 MATH DOWN DOWN DOWN = ; ABS STO 5 RCL 0 STO 4 CALL 06 ; gcd(u-v,n) 1 <=? GT 01 ; main loop RD RCL 0 >=? GT 01 ; main loop RD LBL 02 STOP LBL 06 ; GCD(R4, R5) ; registers 4-5 rcl 4 rcl 5 >= GT 07 STO 4 RD STO 5 LBL 07 rcl 4 ; t4 ENT rcl/5 ; t4/r5 MATH SUP SUP = ; IP rcl*5 ; ip(t4/t5)*t5 - ; t4-ip(t4/t5)*t5 rcl 5 ; t5 X<>Y STO 5 ; store new t5 RD sto 4 ; store new t4 rcl 5 ; t5 0 > ; t5>0 GT 07 rcl 4 RTN LBL 08 ; a^2+1 mod m (possibly == m) ; registers 1, 4-9 ; a on stack, m in r0 STO 1 X^2 RCL 0 STO 8 ; m / ; (a^2)/m MATH UP UP = ; IP = t STO 9 ; for FMA RCL*8 ; t*m +/- ; -(t*m) = w STO 7 ; for FMA CALL 09 ; FMA(r9=t, r8=m, r7=w) RCL 1 ; a STO 9 STO 8 RD ; FMA STO 1 ; result CALL 09 ; FMA(r9=a, r8=b, r7=w) RCL-1 ; -FMA 1 + RTN LBL 09 ; calculates r9*r8 + r7 with extended precision ; registers 4-9. destroys all but 7 rcl 9 rcl*8 STO 5 rcl+7 ENT ENT rcl-5 STO 4 - rcl-5 - rcl 7 rcl-4 + 1 EEX 6 = 1 + STO 4 RCL*9 ENT RCL-9 - STO 6 STO-9 RD rcl 4 RCL*8 ENT RCL-8 - sto 4 sto-8 RD RCL 4 RCL*6 + RCL-5 RCL 6 RCL*8 + RCL 9 RCL*4 + RCL 9 RCL*8 + RTN

Re: Another 30b program! Message #2 Posted by Katie Wasserman on 21 Jan 2010, 7:04 p.m., in response to message #1 by hugh steers Hugh, Very nice! I haven't digested this all yet but have a suggestion for speeding it up. If you move the most called subroutines to the top of the code (branch around them at the start) and have nothing else except this code in the calculator it will run faster. You're using the command SUP. What'sup with that! :) -Katie

Re: Another 30b program! Message #3 Posted by hugh steers on 21 Jan 2010, 7:12 p.m., in response to message #2 by Katie Wasserman thanks. i just realised a few more optimisations whilst reading your pi program. for example 1 EEX is not needed and the use of obscure labels would help. you're right, my notation is out of date. im using X<>Y instead of SWAP and ENT for Input. SUP was originally SHIFT+UP. Actually i think it's clearer to go with Don's way of having IP, ABS etc and then people know how to enter them rather than the keystrokes. so you're saying it always looks from the start of the program rather than from the current position. also, couldn't it make a label cache, it's not like they move around.

Re: Another 30b program! Message #4 Posted by Gene Wright on 21 Jan 2010, 7:57 p.m., in response to message #3 by hugh steers I believe it always looks from the TOP of program memory, regardless of where the branch / call originates.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall