From: jhmeyers@miu.edu (John H Meyers)
Subject: Small factoring programs for HP48
Date: 05 Jun 1997 00:00:00 GMT
Message-ID: <5n5smd$pkp$1@jefferson.lisco.com>
Organization: M.U.M. (Author's personal opinion only)
Newsgroups: comp.sys.hp48


Small HP48 programs for factoring small numbers
===============================================

ALG48 and FACTOR include large sophisticated programs which
can test for primes and factor large integers quickly (FACTOR
is a 2400-byte directory from Goodies Disk #2, accepts arguments
up to 2^64, and requires a cable to download, since it is
a combination of both User-RPL and ML code).

A small unsophisticated User-RPL program which can factor small integers is
offered below.  It can factor any 6-digit number in less than 4 seconds,
or any 8-digit number in less than 40 seconds, although most arguments
can be factored much faster than these worst-case times
(all timings quoted here are for the HP48G/GX).

%%HP: T(3); @ \-> is right-arrow, \<- is left-arrow, etc.
@ The symbol at the left end of this line always begins a comment.
DIR @ Directory begins
  FACTR @ real_integer(>1) --> { factors }
    \<< DEPTH { WHILE DUP2 MOD NOT REPEAT SWAP OVER / OVER END }
      \-> d \<-p  \<< PRXX
      DUP 1 == { DROP } IFT DEPTH d - 1 + \->LIST \>> \>>
  PRIM @ real_integer(>1) --> 1 (is prime) or 0 (not prime)
    \<< { DUP2 MOD NOT { DUP2 > { DROP2 -1 2 } IFT } IFT }
      \-> \<-p \<< PRXX 0 > \>> \>>
  PRIN @ real_integer(>1) --> next larger odd prime (not 2)
    \<< DUP 2 MOD NOT - DO 2 + UNTIL DUP PRIM END \>>
  PRIP @ real_integer(>1) --> next smaller odd prime (not 2)
    \<< DUP 2 MOD NOT + DO 2 - UNTIL DUP PRIM END \>>
  PRXX @ inner loop for FACTR and PRIM programs
    \<< 1 MAX 2 \<-p EVAL 1 + \<-p EVAL 2 + \<-p EVAL 2 +
      WHILE DUP2 SQ \>= REPEAT
          \<-p EVAL 4 + \<-p EVAL 2 + \<-p EVAL 4 + \<-p EVAL
      2 + \<-p EVAL 4 + \<-p EVAL 6 + \<-p EVAL 2 + \<-p EVAL 6 +
      END DROP \>>
  \pilist @ { factors } --> product
    \<< { 1 1 } + \PILIST \>> @ G/GX only
END @ Directory ends

The length of time required for factoring is roughly proportional
to either the second-largest factor or the square root of the
largest factor, whichever is greater; divide this quantity
by 280 to estimate how many seconds it will take.

Primality testing and next/previous prime functions are also offered;
primality testing is faster than factoring, being proportional to
either the smallest factor or the square root of the original number,
whichever is less; divide by 340 for a time estimate.

Although the method used is along the lines of "try every possible
divisor," it has been speeded up considerably by trying 2, 3, and 5
at the outset, then the set 7, 11, 13, 17, 19, 23, 29, and 31, then
indefinitely incrementing the trial divisors in the latter set by 30.
The test for exceeding the square root of the current quotient is made
only once per "block of 30" trial divisors, saving even more time.

1 MAX is used to forestall some infinite looping; otherwise there are no
checks for sensible arguments (i.e. positive integers between 2 and 1E12);
the PRIN/PRIP functions skip over the prime number 2; zero, one,
and all negative arguments or non-integers are considered prime.

The programs as listed take advantage of the "compiled local variables"
feature of the HP48G/GX, described near the end of Chapter 29 in the
HP48G/GX User's Guide, inasmuch as local variable \<-p is defined in
programs FACTR and PRIM but is referenced in separate subroutine PRXX.

If you are typing these programs by hand, the required
left-arrow character is produced in alpha mode by pressing
right-shift before the left-arrow (cursor left) key.

If you have an HP48S/SX, the "inner loop" function PRXX must
be re-compiled after downloading to your calculator, in order to
make its variable local; if you are manually typing it in, you can
save a lot of time by omitting every left-arrow character from the
local variable name, since those characters are necessary only on a G/GX.

  To re-compile PRXX: (for S/SX only!)
  o Perform 0 \-> \<-p \<< HALT \>> (this creates the local variable).
  o Edit the PRXX program; don't make any changes, just press ENTER; this
    changes all instances of the variable name from global to local.
  o Store the PRXX program back into its variable.
  o Perform either CONT or KILL to exit the halted program.

That's all from the factor factory for today, folks.

-----------------------------------------------------------
With best wishes from:   John H Meyers   <jhmeyers@mum.edu>

