Another 30b program!



#5

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


#6

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


#7

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.


#8

I believe it always looks from the TOP of program memory, regardless of where the branch / call originates.


Possibly Related Threads...
Thread Author Replies Views Last Post
  HP Prime: run a program in another program Davi Ribeiro de Oliveira 6 1,901 11-11-2013, 08:28 PM
Last Post: Davi Ribeiro de Oliveira
  Flashing cable for HP 20 / 30B Stefan Koenig 3 1,475 09-19-2013, 05:53 AM
Last Post: Marcus von Cube, Germany
  Any 30b cables left? patryk 7 1,914 09-16-2013, 02:54 PM
Last Post: Marcus von Cube, Germany
  HP-30B (WP-34S) Technical Documentation Barry Mead 3 1,296 09-09-2013, 03:07 PM
Last Post: Harald
  HP's thinking behind the 20b/30b? John Ioannidis 3 1,256 09-07-2013, 10:21 AM
Last Post: Tim Wessman
  30b/34s interfacing? ross sponholtz 5 1,604 06-26-2013, 01:41 AM
Last Post: Walter B
  Inexpensive HP 30b Matthew Richards 23 4,823 05-22-2013, 10:10 AM
Last Post: Dave
  hp-30b with free shipping sjthomas 9 2,238 04-14-2013, 02:46 AM
Last Post: Gerson W. Barbosa
  Amazon offering 8$ for my HP-30B Siegfried (Austria) 7 1,892 04-13-2013, 04:38 PM
Last Post: Chris Smith
  That is how they should sell the HP 30B :) Harald 11 2,584 04-07-2013, 11:44 AM
Last Post: Juergen Keller

Forum Jump: