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
RCL3 ; uv;
ENT
GF 02
MATH
DOWN
DOWN
DOWN
= ; ABS
STO 5
RCL 0
STO 4
CALL 06 ; gcd(uv,n)
1
<=?
GT 01 ; main loop
RD
RCL 0
>=?
GT 01 ; main loop
RD
LBL 02
STOP
LBL 06
; GCD(R4, R5)
; registers 45
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
 ; t4ip(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, 49
; 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)
RCL1 ; FMA
1
+
RTN
LBL 09
; calculates r9*r8 + r7 with extended precision
; registers 49. destroys all but 7
rcl 9
rcl*8
STO 5
rcl+7
ENT
ENT
rcl5
STO 4

rcl5

rcl 7
rcl4
+
1
EEX 6
=
1
+
STO 4
RCL*9
ENT
RCL9

STO 6
STO9
RD
rcl 4
RCL*8
ENT
RCL8

sto 4
sto8
RD
RCL 4
RCL*6
+
RCL5
RCL 6
RCL*8
+
RCL 9
RCL*4
+
RCL 9
RCL*8
+
RTN
