kskalb@faui1f.informatik.uni-erlangen.de (Klaus Kalb) (12/07/90)
Hello everybody,
This program for the HP48 tests numbers for being prime.
It is written as a user defined function, so you can include
it into algebraics.
Start it with a number (binary or real) in level 1 and it will answer:
0 if the number is composite
1 if the number is prime
2 if it can't do the job
The last case occurs only if the number is greater then 25*10^9.
Even if this occurs, you can be quite sure that the given number
is a prime, since the numbers that give a 2 on this test and are
composite are very rare --- but they do exist.
(they are indeed so rare that I don't know an example ;-)
This test is fast --- testing a prime near 10^9 will take about 7000 ticks.
This is less then one second --- not so bad for a small machine.
Of course this is accomplished using mcode. You need ASC\-> to get it
into your machine.
------------------------------------------------------------------------------
MORE ABOUT THE IMPLEMENTATION:
This program implements the test proposed by Pomerance, Selfridge and
Wagstaff in _The_Pseudoprimes_to_25*10^9_ in math.comp.35 (1980)
Some special effort is made to recognize small primes and numbers with
small factors on an early stage.
It will recognize all primes below 25*10^9.
It runs the strong pseudoprime test with the bases 2,3,5,7, so that
a number passing this test with result 2 is at least a strong pseudoprime
to these bases.
There are two subroutines written in mcode:
BGCD calculates the greatest common divisor of two binary integers.
It uses the binary algorithm that can be found in Knuth's
_The_Art_of_Computer_Programming.
MILRAB performs a strong pseudoprime test on the number N in level 2
to the base B in level 1. It will accept any combination of
binary integers and reals. The output is 1 if N is a
strong base-B pseudoprime and 0 if not.
Both routines perform argument checking and give decent error messages.
------------------------------------------------------------------------------
INSTALLATION:
Download the following object to your HP48 using the name 'PRIME'.
Be sure that ASC\-> can be found in the path.
Evaluate 'PRIME'. Answer 'YES' be pressing the 'A' key.
After this, you may purge 'PRIME'.
Three Programs will be installed on the current directory:
BGCD, MILRAB and PRIME?
------------------------------------------------------------------------------
DISCLAIMER: (that's one I've found on the net ;-)
This program makes use of undocumented low-level features of
the HP48SX calculator, and may or may not cause loss of data,
excessive battery drainage, and/or damage to the calculator
hardware. The Author takes no responsibility whatsoever for
any damage caused by the use of this program.
This software is provided "as is" and WITHOUT ANY EXPRESS OR
IMPLIED WARRANTIES, including, but not limited to, THE IMPLIED
WARRANTIES OF MERCHANTABILITY and FITNESS FOR A PARTICULAR PURPOSE.
------------------------------------------------------------------------------
Klaus Kalb | mail : IMMD1 / Martenstr. 3 / W-8520 Erlangen / Germany
| email: kskalb@immd1.informatik.uni-erlangen.de
------------------------------------------------------------------------------
%%HP: T(3)A(D)F(,);
@
@ PRIME (generated by hp48pack at 07.12.90)
@
@$NAME PRIME
@$DATE 06.12.90
@$VERSION 2.00
@
@
@ PRIME? 2.00 06.12.90
@ BGCD 1.00
@ MILRAB 1.00
@
@
\<< CLLCD
"----------------------" DUP 1 DISP
"PRIME 2.00 06.12.90" 2 DISP
DUP 3 DISP
" PRIMALITY TEST" 4 DISP
" by Klaus Kalb" 5 DISP
6 DISP
" unpack ?" 7 DISP
0
@
@ $NAME PRIME?
@ $DATE 06.12.90
@ $VERSION 2.00
@
\<<
\-> n
\<<
RCLF 64 STWS @ save the flag status
@ check the argument
n DTAG
IF DUP TYPE NOT
THEN
ABS DUP R\->B DUP B\->R ROT
IF SAME THEN
0
ELSE
515 @ bad argument value
END
ELSE
IF DUP TYPE 10 SAME THEN
0
ELSE
514 @ bad argument type
END
END
@ make an error
IF DUP THEN
ROT STOF
SWAP DROP
IF -55 FC? THEN n SWAP END
DOERR
END
DROP
'n' STO
CASE
n #2d < THEN 0 END
{ #2d #3d #5d #7d } n POS THEN 1 END
#210d n BGCD #1d \=/ THEN 0 END
#121d n > THEN 1 END
#9156001667401012567d n BGCD #1d \=/ THEN 0 END
#12474161705592459703d n BGCD #1d \=/ THEN 0 END
#11449d n > THEN 1 END
n 2 MILRAB NOT THEN 0 END
#42799d n > THEN 1 END
n 3 MILRAB NOT THEN 0 END
#1373653d n > THEN 1 END
n 5 MILRAB NOT THEN 0 END
#25326001d n > THEN 1 END
n 7 MILRAB NOT THEN 0 END
#3215031751d n == THEN 0 END
#25000000000d n > THEN 1 END
2
END
SWAP STOF
\>>
\>>
@ $END PRIME?
'PRIME?'
@ $NAME BGCD
@ $VERSION 1.00
@
"D9D20E1632FDE81ECD46CCD20F70008F77F35AF397845AFE978C48087091AFE8
0870F081E81CB7765EF808B09081E65FF9F650AFEB7A9780181C808608F65EFA
FA97BC0A74A7F64FF8F59E3593632B21302438"
ASC\->
@ $END BGCD
'BGCD'
@ $NAME MILRAB
@ $VERSION 1.00
@
"D9D20E1632FDE8199040D9D209F345322309F34532230CCD20900006380B2130
4CD46D9D209F345CCD20900006160B2130DF040D9D20322309F34532230CCD20
900006530B2130ECD46D9D202C230CA13050F353DE350BE35CCD20431008F77F
3510A1008087093978D0A7CA7C9789120808244B2A28F07F35808C20808249C2
A268EFA7C9783DAF381CB77808605F101AF0B74103111978E380870F181C1011
1211A7950102111808605E11311A7240103111A7C97CDC113AF2B7697202118A
7E97251A7F97B11AF67C0065EF6B5F604FAF19780080870D181CA761209F650B
72120808607EA71A7C1209F050B7812097CECAF401B213093632B213010A4"
ASC\->
@ $END MILRAB
'MILRAB'
@ user dialog
{ { "YES" \<< WHILE DUP 0 SAME NOT
REPEAT STO END DROP
" PRIME installed." 7 DISP 3 FREEZE
0 MENU \>> }
"" "" "" ""
{ "NO" \<< WHILE DUP 0 SAME NOT
REPEAT DROP DROP END DROP
0 MENU \>> }
} 3 FREEZE TMENU \>>
@$END PRIME