### # #### # ### # # # # ## # # # # # # # # # # ####### # # #### # # ### # # # # # ##### # # # # # # # # # # # # #### #### # ### AN ALGEBRA LIBRARY FOR THE HP48 Version 3.06 (c) 1994-96 by Claude-Nicolas Fiechter & Mika Heiskanen [Note: This document is for an older version of ALG48, but it's the only plain-text version available. For a complete postscript or TEX version of the current document, contact the authors (see below). -jkh-] 1. ACKNOWLEDGEMENTS, COPYRIGHT & DISCLAIMER OF WARRANTY ======================================================= All the files of the ALG48 library are copyrighted (c) by Claude-Nicolas Fiechter and Mika Heiskanen. ALG48 is distributed in the hope that it will be useful, but the COPYRIGHT HOLDERS PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT WILL THE COPYRIGHT HOLDERS BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM. This version of ALG48 is a GiftWare release. You may use it as long as you like, but only for non-commercial purposes and only as a private person. Permission to copy the whole, unmodified, ALG48 library is granted provided that the copies are not made or distributed for resale (excepting nominal copying fees) and provided that you conspicuously and appropriately include on each copy this copyright notice and disclaimer of warranty. Special thanks to Dominique Rodriguez for his Latex version of the documentation for ALG48 v2.1, on which the nice-looking version of this document is based. 2. OVERVIEW =========== ALG48 provides a number of commands to do advanced algebraic (symbolic) calculations on the HP48, including simplification, factorization, and symbolic matrices manipulation. ALG48 differs from other mathematical packages for the HP48 in two important aspects: 1. ALG48 can manipulate, simplify and factorize MULTIVARIATE polynomials and functions, i.e., algebraic expressions with several variables. 2. ALG48 only does EXACT calculation, using unlimited precision integers and advanced computer algebra algorithms (as opposed to doing approximate calculation using floating point numbers and numerical algorithms). This not only means you will not get wrong or approximate results (2.00001, 4.9999 and the like), but also that all and only exact simplifications are performed. Here are some examples of ALG48 operations. The time taken for the commands on a HP48GX (with ~60K free) are given in brackets. * Simplification of multivariate polynomials and rational functions: Y 1 - --- X+Y 1 - ------- X 1 - --- X+Y 2 2 ------------------------- = RSIM => INV(X + X*Y + Y ) 2 X [X*Y ] [3.1s] Y - -------- * [--- - X] X [Y-X ] 1 + --- Y-X * including polynomials and rational functions with non-rational subexpressions: COS(A)*SIN(A)-COS(A)-SIN(A)+1 SIN(A)-1 ----------------------------- = RSIM => -------- COS(A)*SIN(A)+COS(A)-SIN(A)-1 [1.2s] SIN(A)+1 * Complete factorization of polynomials and rational functions: 7 6 5 4 3 2 3*X -36*X +132*X -126*X -12*X -180*X + 75*X 2 = FCTR [2.2s] => 3 * X * (X^2+X+1) * (X^2-3*X+1) * (X-5) * including polynomials and rational functions in several variables: 2 2 3 2 4 3 2 3*X *Y +9*X -X*Y -5*X*Y -2*X*Y -18*X +Y -Y +6*Y -Y+5 = FCTR [5.2s] => (X*Y+3*X-Y^2-1) * (3*X-Y^2+Y-5) * Simplification of non-rational expressions: SQRT(X^3+X^2-X-1) SQRT(X-1) ------------------------- = ASIM => ----------- SQRT(12*SQRT(5)+49)*(X+1) [4.3s] 3*SQRT(5)+2 * including exponential functions: X*EXP(3*LN(X)+LN(X^2)) - 1 4 2 -------------------------- = ASIM => 2*X +2*X +2 LN(SQRT(EXP(X^2-1))) [1.8s] * and trigonometric functions: COS(ASIN(SIN(X)-COS(X)))^2 SIN(X)*COS(X) -------------------------- = ASIM => ------------- LN(SIN(X)*COS(X)*TAN(X)) [8.6s] LN(SIN(X)) * Symbolic vector and matrix operations: Inverse {{ 3 2*H^2 1 } {{ 2*H^4+1 (-4*H^4-1)/(2*H) H^2 } { 4*H 2*H^3 2*H } = AINV => { -2*H^2 2*H -1 } { 2*H^2 -1 2*H^2 }} [9.3s] { -2*H^4-2 (4*H^4+3)/(2*H) -H^2 }} Determinant {{ 1 T T T } { 1 K T T } 3 2 2 3 3 { 1 T K T } = MDET => K - 3*K *T + 3*K*T - T = FCTR => (K-T) { 1 T T K }} [3.9s] [2.7s] Addition, Subtraction, Negation, Multiplication, Division, Exponentiation, Transpose ... * Resolution of systems of linear equations (Ax = b) with symbolic coefficients b: { 1 2 3 } A: {{ 1-T 2 -4 } { 3/2-T 3 -5 } { 5/2+T 5 -7 }} = ADIV [5.3s] => x: { INV(-2*T) (7*T+1)/(4*T) 3/4 } Additional features include: * Provides arithmetic operations on unlimited-size integer numbers, including modular arithmetic, integer factorization, and primality testing. * Can be used to easily calculate with fractions. * Can handle polynomials and rational functions of arbitrary degrees and with arbitrary many variables (limited only by your HP48's memory and by your patience). * Entirely written in system-RPL and ML. 3. INSTALLATION =============== 3.1 Library versions -------------------- ALG48 v3.0 comes in two versions: a) Full-feature version (file: 'alg48ful.lib') This is the complete version of the library, which contains all the commands described in this manual. It takes approx. 30K of memory. b) "Light" version (file: 'alg48lgt.lib') This is a leaner version of the library, which contains all the commands except ASIM (see Section 4.3). It takes approx. 23K of memory. The two versions are fully compatible. That is, a program that uses commands of ALG48 will work the same with the two versions (as long as it does not use ASIM). In the light version, the command location of ASIM is redirected to RSIM (see Section 4.2). 3.2 Platforms and Ports ----------------------- ALG48 should work in ANY port of a HP48G(X) or SX. The library was developed on a HP48GX version P and tested in ports 0, 1 and 2. Previous versions were reported to also work properly on the SX. ALG48 can safely be run from a covered port (2-33) of a HP48GX and uses a special technique to avoid the usual slowdown associated with running a library from a covered port. However, if running the library from a covered port, only use the provided user commands and do not try to access internal routines of the library directly, since this might crash your calculator. NOTE: If you have ALG48 in a covered port and want to use the Special Functions Library (SpecFun), SpecFunc must be put in the same port as ALG48 or in port 0 (see the SpecFun documentation). 3.3 Installation procedure -------------------------- ALG48 is a regular auto-attaching library (library number 909). To install it on your HP48 download the file corresponding to the version you want (alg48ful.lib or alg48lgt.lib) onto your calculator (in BINARY mode), put the content of the created variable on the stack, store it the port of your choice (e.g., 'ALG48FUL.LIB' DUP RCL SWAP PURGE 0 STO) and power-cycle the calculator. The basic operation commands defined in ALG48 (AADD, ASUB, ANEG, AMUL, ADIV, AINV, APOW, see Section 4) are intended to be assigned to the corresponding keys (+ - +/- * / 1/x ^) of the calculator. To do this you can type { S APOW 45.1 AINV 46.1 ANEG 52.1 ADIV 65.1 AMUL 75.1 ASUB 85.1 AADD 95.1 } STOK Thereafter, whenever the calculator is in user mode, pressing one of these keys will call the corresponding ALG48 command, and, if the arguments provided do not match those handled by the library (see the Command Reference in appendix) the standard command will be called. Therefore you can stay in user mode and still perform "regular" operations. In addition, these commands have algebraic aliases, which means that you can stay in user mode when typing a symbolic expression (in what HP calls algebraic-entry mode) and still get the usual symbols (+,-,*,...) when pressing the corresponding keys. 4. USE ====== 4.1 Generalities ---------------- To ensure exact results ALG48 ONLY WORKS WITH INTEGER AND RATIONAL NUMBERS and produces a "Bad Argumnent Type" error if it finds a fractional number in the input. If the expressions you have contain fractional numbers, you must convert them first into rational numbers by using the command ->Q or ->Qpi of the HP48, or by using the program ->QpiRac (c) by A. Coulom. [An advantage of ->QpiRac is that it will also convert real arrays into symbolic matrices and complex numbers in (a,b) form into the a+b*i form, appropriate for ALG48.] The commands in ALG48 can be divided into six groups, according to the kind of operations they perform: (1) Simplification commands - RSIM FCTR RAT-> ASIM which are used to simplify symbolic expressions (or all the elements of a symbolic matrix or vector). (2) Basic operations commands - AADD ASUB ANEG AMUL ADIV AINV APOW which are used to do basic calculation (+ - +/- * / 1/x ^) on several kind of objects: - Symbolic matrices and vectors; - Symbolic expressions; - Fractions; - Unlimited precision integers. (3) Symbolic matrix commands - MDET MADJ MTRN MIDN which perform specific operations on symbolic matrices. (4) Algebraic funtions - GCD LCM which perform specific operations on polynomials or unlimited precision integers. (5) Modular arithmetic - MOD+ MOD- MOD* MOD/ MOD^ MODINV which perform modular arithmetic operations on unlimited precision integers. (6) Prime number operations - PRIM? PRIM+ PRIM- which perform operations related to prime numbers on unlimited precision integers. We describe below how to use these groups of commands to manipulate different kinds of objects. The Command Reference in appendix gives a brief definition and the stack diagram of each command. 4.2 Polynomials and Rational Functions Simplification ----------------------------------------------------- ALG48 provides two powerful commands for simplifying multivariate polynomials and rational functions. These commands will work on any algebraic expression by treating it as the quotient of two polynomials in several "variables", which can actually be non-rational subexpressions (see the second example in Section 2). RSIM - Simplifies a symbolic expression as a rational function and returns it in (expanded) canonical form. FCTR - Simplifies a symbolic expression as a rational function and returns it as the product of its factors. The simplification consists of two main steps - Multiplying out all products of polynomials and collecting the terms of same degree for the numerator and denominator polynomials; - Simplification of the rational function by the multivariate polynomial greatest common divisor (GCD) of the the numerator and denominator. Depending on the type of the simplified rational function, RSIM returns it in one of the following forms: - If the denominator of the rational function is a constant, then the result is returned as a polynomial with possibly rational coefficients; - If the numerator of the rational function is a constant, then the result is returned as the inverse of a polynomial with possibly rational coefficients; - If both the numerator and the denominator of the rational function contain variables, then the result is returned as the ratio of two polynomial with integer coefficients. Similarly, FCTR returns the simplified rational function as either - The product of its factors (which are all polynomials with integer coefficients) multiplied by a possibly rational coefficient; - The inverse of such a product; - The ratio of two such products. It is important to understand that FCTR computes the true factorization of a polynomial over the integers (or, equivalently, over the field of rational numbers), and not approximate roots over the real or complex field as computed by a root finding program (like the command ROOT or PROOT of the HP48). Polynomials of arbitrary degree can be irreducible over the integer, and a factorization might therefore entail high degree polynomials. For instance: X^8-4*X^7-2*X^6+20*X^5+3*X^4-44*X^3+22*X^2+4*X+34 = FCTR [12.8s] => (X^4+4*X^3+6*X^2+4*X+2)*(X^4-8*X^3+24*X^2-32*X+17) For more on RSIM and FCTR see the section 4.10. ALG48 also provides the command RAT->, which operates like RSIM, but returns the numerator and denominator of the simplified rational function as two separated polynomials. In addition, the commands GCD and LCM respectively compute the greatest common divisor and the least common multiple of two polynomials. These two functions do NOT accept rational functions as input, since the GCD and LCM are ill-defined notions in this case. For all the simplification commands, in the polynomials the terms are arranged into descending order of their degrees, and the "variables" in the terms are arranged in lexicographic order, with the true variables (global and local names) first, followed by the non-rational subexpressions. E.g., 'A*X^2*Y^3*EXP(X)*EXP(Y)+X*Y^2-2*EXP(X)+3'. All the symplification commands produce a "Infinite Result" error if the denominator of the simplified expression is zero. 4.3 General Algebraic Expressions Simplification ------------------------------------------------ RSIM and FCTR leave any non-rational (sub)expressions unchanged and treat 'i' (the complex unit) like any other variable. To simplify non-rational algebraic expressions (like square- and yth-root, exponentials, logarithmics, trigonometric and hyperbolic functions) and expressions that involve complex arguments ALG48 version 3.0 provides the command ASIM. Unlike the simplification of rational expressions, the simplification of general algebraic expressions is somewhat subjective and heuristic in nature. No algorithm will do it perfectly in all cases. ASIM does the following: - Recursively applies RSIM to every "rational" subexpression - Simultaneously apply rules to simplify non-rational expressions - Expand the exponentials, logarithms, etc. - Simplify the resulting expression using RSIM - Merge back the remaining exponentials, logarithms, etc. ASIM takes the natural "principal solution" approach to simplification, that is, it performs simplification that hold in the "principal" case, but that are not necessarily true in all cases. For instance, ASIM simplifies SQRT(X^2) into X, even though, strictly speaking, this is valid only when X is positive (the "principal" case). A table of the rules that ASIM uses to simplify non-rational expressions is given in appendix. 4.4 Automatic Simplification ---------------------------- ALG48 uses the user flag number 5 as an automatic simplification flag. When the flag is set the result of any basic operation commands is automatically simplified, as by an application of RSIM. For instance, the result of 'X-1/2' '2*X' AMUL is '2*X^2-X' when the automatic simplification flag is set and '(X-1/2)*(2*X)' when the flag is clear. Since the simplification of rational functions can be time consuming (see 4.10), it is sometimes preferable to do a series of operations without simplifying the intermediate results (i.e., with the automatic simplification flag clear) and then to simplify explicitly the final result by using RSIM. 4.5 Symbolic Matrix Manipulation -------------------------------- ALG48 represent (n x m) symbolic matrices by lists of the form {{A11 .. A1m}{A21 .. A2m} .. {An1 .. Anm}} where each element Aij is either a real number, a variable or a symbolic expression. Similarly, symbolic vectors [(n x 1) matrices] are represented by lists of the form {A1 .. An}. All the symbolic matrix commands of ALG48 check that their arguments are valid symbolic matrices and will produce a "Bad Argument Type" error otherwise. In addition, the commands that accept non-square matrices as arguments will also accept symbolic vectors and will return symbolic vectors when appropriate. ALG48 provides the following symbolic matrix commands [below, "scalar" denotes a real number, a variable or a symbolic expression]: AADD - Adds two symbolic matrices or vectors, or, given a square matrix A and a scalar X, computes A+I*X. ASUB - Subtracts two symbolic matrices or vectors, or, given a square matrix A and a scalar X, computes A-I*X (or I*X-A). ANEG - Negates all the elements of a symbolic matrix or vector. AMUL - Multiplies two symbolic matrices or vectors, or a scalar with a symbolic matrix or vector. ADIV - Multiplies a symbolic matrix, vector or scalar by the inverse of a square symbolic matrix or scalar; can be used to solve systems of linear equations with symbolic coefficients as shown in Section 2. AINV - Computes the inverse of a square symbolic matrix. APOW - Raises a square symbolic matrix to an integer power. MDET - Computes the determinant of a square symbolic matrix. MADJ - Computes the adjoint matrix (or co-matrix) of a square symbolic matrix. MTRN - Transposes a symbolic matrix or vector. MIDN - Given an integer number n returns the (n x n) identity symbolic matrix. The result of the basic operation commands is simplified or not depending on whether the automatic simplification flag is set (see Section 4.4), whereas the result of MDET and MADJ is always simplified. In addition RSIM, FCTR and ASIm can be used to simplify each element of a symbolic matrix or vector. Both AINV and ADIV produce a "Infinite Result" error if applied to a singular (non-invertible) matrix. 4.6 Calculating with fractions ------------------------------ ALG48 can be used to easily calculate with fractions, especially if the basic operation commands are assigned to the correspondings keys of the calculator (see Section 3.3). To facilitate the keying of fractions, ADIV and AINV applied to integer arguments return a symbolic fraction instead of evaluating the result as a real number. Thus, to calculate an expression using fractions just type the expression in regular RPN, as you would to evaluate it using real numbers. For instance, to compute 3/4+1/6 you just type 3 4 ADIV -> '3/4' 6 AINV -> '1/6' AADD -> '11/12' Note: Make sure the automatic simplification flag is set when calculating with fractions, otherwise the expressions will not be evaluated (see Section 4.4). 4.7 Unlimited Precision Integer Arithmetic ------------------------------------------ Internally ALG48 does all its calculations using unlimited precision integers. These unlimited precision integers are represented by hexstrings (binary integers) of variable length (NOT limited to 64 bits), with a sign-magnitude format (one sign nibble and a variable length unsigned magnitude). For instance, the number 1 is represented by the two-nibble hexstring #01h, whereas the number 2^64 is represented by the eighteen-nibble hexstring #0100..0h. Negative numbers are identical except for the sign nibble which is set to F. For instance, the number -1 is represented by the two-nibble hexstring #F1h and -2^64 is represented by the eighteen-nibble hexstring #F100..0h. Finally, zero is represented by the one-nibble hexstring #0h. Note that the TWO-nibble hexstring #F1h does NOT represent the same number as the THREE-nibble hexstring #0F1h (which represents the number 241). You can use ALG48 to do unlimited precision integer arithmetic directly by using the basic operation commands (except AINV) with binary integer arguments (or one binary integer and a real number). For example #2 65 APOW computes the exact value of 2^65. Note, however, that the HP48 will only display the value of the 64 (or whatever your binary word size currently is) lowest-significant bits of long hexstrings. Therefore, in the example above, the result will be displayed as #0h since the lowest 64 bits are all zeros. To overcome this problem, ALG48 provides the command Z<->S that converts a variable length hexstring into a (character) string giving its value in decimal, or vice versa. Thus typing #2 65 APOW Z<->S returns "3689348814711903232" which is the exact value of 2^65. As an additional example, the following little user-RPL program computes the exact factorial of its single real argument, and returns it as a string: << #1h 1 ROT FOR i i AMUL NEXT Z<->S >> Running it with 100 as argument gives "933262154439441526816992388562667004907159682643816214685 929638952175999932299156089414639761565182862536979208272 23758251185210916864000000000000000000000000" As a typing short-cut, ZS is an alias name for the Z<->S command. 4.8 Advanced Algebraic Operations on Unlimited Precision Integers ----------------------------------------------------------------- In addition to the basic operation commands, several commands of ALG48 perform advanced algebraic computations on unlimited precision integers. GCD - Greatest common divisor of two integers LCM - Least common multiple of two integers PRIM? - Check whether a number is prime PRIM+ - Returns the next (larger) prime number PRIM- - Returns the previous (next smaller) prime number FCTR - Factorization into prime numbers The integer argument(s) for all these commands, except FCTR, can be given (in any combination) as (integer) real numbers, unlimited precision binary integers, or strings representing the number in decimal. Here are some examples of the primality testing commands. "170141183460469231731687303715884105727" = PRIM? [58s] => 1 (= prime) "130529377836972488251268578591" = PRIM? [8s] => 0 (= not prime) #1234567890123456d = PRIM+ [6s] => #1234567890123481d #1234567890123456d = PRIM- [4s] => #1234567890123439d [The first number above is 2^127-1, which is the 12th Mersenne number, and is known to be indeed prime.] Because of its use as a simplification command, FCTR leaves real numbers unchanged and will only factor integers given as binary integers or as strings. If the number is given as a binary integer FCTR returns a list with the prime factors. If the number is given as a string, the factors are given in a symbolic form. For instance #130529377836972488251268578591d = FCTR [34s] => { #2647d #3691d #5113d #11779d #398609d #556517681d } and "130529377836972488251268578591" = FCTR [34s] => '2647*3691*5113*11779*398609*556517681' FCTR uses advanced integer factorization algorithms and can factor relatively large numbers. However no "efficient" (poly-time) algorithm is known for factoring arbitrarily large integers and it is widely believed that no such algorithm can exist. Thus FCTR will factor completely only reasonably small numbers (up to 20-30 digits) or larger numbers that consist only of small factors. To avoid running forever, if FCTR does not make any progress after one minute it returns the number unfactored (or only partially factored). You can also abort the computation by pressing the ATTN (ON) key. In the contrary, the primality testing algorithm (used by PRIM?, PRIM+ and PRIM-) CAN handle very large numbers. However the algorithm is randomized and might, with very low probability, say that a number is prime when it is not (but will never say that a number is not prime when in fact it is). 4.9 Modular Arithmetic on Unlimited Precision Integers ------------------------------------------------------ ALG48 provides six commands specifically to perform modular arithmetic on unlimited precision integers. These commands take three arguments (two operands A and B, and a modulus N), except MODINV which takes only two arguments (A and N). Here again the arguments can be given as (integer) real numbers, binary integers, or strings. MOD+ - (A+B) MOD N MOD- - (A-B) MOD N MOD* - (A*B) MOD N MOD/ - (A*C) MOD N where C is the inverse modulo N of B MOD^ - (A^B) MOD N MODINV - C where C is the inverse modulo N of A If A and N are relatively prime numbers (with A '(6*X^3+X*Y+X*Z+1)/(9*X^2+2*X*Y*Z+3)' Also, ALG48 is very fast at simplifying polynomials (multiplying out the products and collecting the terms of same degree). For instance, RSIM takes only 1s to simplify the following expression: 12 12 11 9 7 5 3 (X+1) -(X-1) = RSIM => 24*X +440*X +1584*X +1584*X +440*X +24*X As a comparison, the program EXCO (Expand & Collect completely), described in HP's Advanced User's Reference Manual (p.2-20), was not able to obtain the solution in 10 hours. Using extrapolation from the time taken by EXCO to perform simpler binomial expansions, John Stebbins estimated that it would take EXCO more than 18 days (!!!) to find the solution of this example. On the other hand, the factorization of polynomials is comparatively slow, specially for multivariate problems. Simple factorizations, however, are performed quite fast. For instance, FCTR takes less than 3s on the following example: 3 2 2 3 X - 3*X *Y + 3*X*Y - X - Y + Y = FCTR => (X-Y+1)*(X-Y)*(X-Y-1) Also, some seemingly complex factorizations can be handled in a reasonable amount of time, like the following one, taken from the Mathematica (TM) book, that ALG48 solves in less than 20s. '4096*X^8-14336*X^7*Y+43008*X^7+16768*X^6*Y^2-155904*X^6*Y +169344*X^6-5600*X^5*Y^3+195552*X^5*Y^2-635040*X^5*Y+296352*X^5 -1919*X^4*Y^4-83244*X^4*Y^3+849366*X^4*Y^2-1148364*X^4*Y+194481*X^4 +700*X^3*Y^5-9744*X^3*Y^4-433944*X^3*Y^3+1629936*X^3*Y^2-777924*X^3*Y +262*X^2*Y^6+8568*X^2*Y^5+15876*X^2*Y^4-963144*X^2*Y^3+1166886*X^2*Y^2 +28*X*Y^7+1680*X*Y^6+31752*X*Y^5+148176*X*Y^4-777924*X*Y^3+Y^8+84*Y^7 +2646*Y^6+37044*Y^5+194481*Y^4' = FCTR => '(X-Y)^4*(8*X+Y+21)^4' Due to the limited power and speed of the HP48, the polynomial factorization algorithm of ALG48 is somewhat limited. In general FCTR will not be able to factor arbitrary big square-free multivariate polynomials, unless they consists only of small-degree factors. However, given enough time, ALG48 version 3.0 can still factor quite complex polynomials: '6*X^6-126*X^4*Y^3*Z+78*X^4*Y*Z^2+X^4*Y+X^4*Z+13*X^3-21*X^2*Y^4*Z -21*X^2*Y^3*Z^2+13*X^2*Y^2*Z^2+13*X^2*Y*Z^3-21*X*Y^3*Z+13*X*Y*Z^2 +2*X*Y+2*X*Z+2' = FCTR [192s] => '(X^3-21XY^3Z+13XYZ^2+2)(6X^3+XY+XZ+1)' Note that before trying to factor a polynomial or rational function, FCTR blindly simplifies it into canonical form (expands it completely and collects the terms of same degree). Therefore, and specially in light of the previous remark, if you have a polynomial already partially factored, split it first using the command OBJ-> of the calculator, and then apply FCTR to each term separately. 4.11 Remarks ------------ Here are a few things to note about ALG48 * ASIM is the only command of ALG48 that handles complex arguments directly in their (x,y) form. All other commands will produce a "Bad Argument Type" error if they finds such complex argument in the input. However, complex arguments in the form 'x+y*i' are handled properly, with 'i' treated as any other variable. * If they are given equations as input RSIM and ASIM will simplify both side of the equation independenlty. On the other hand, FCTR does not accept equations as input, and produce a "Bad Argument Type" error in this case. * Even though ALG48 internally uses unlimited precision integers for all its computations, the HP48 can only handle real numbers inside symbolics. Thus ALG48 cannot input (output) unlimited precision integers from (into) algebraic expressions, and will produce a "Bad Argument Value" if a number in the input is too big to be represented exactly by a real. For instance: '1/2' 65 = APOW => '1/3.6894..E19' = 1 AAAD => Bad Argument Value Therefore, if for example you want to do unlimited precision arithmetic with fractions, you have to handle the numerator and denominator separately as two unlimited precision binary integers. 5. HISTORY OF CHANGES ===================== Changes from version 2.1 to 3.0 ------------------------------- - The commands ASIM, MOD+, MOD-, MOD*, MOD/, MOD^, MODINV, PRIM?, PRIM+, and PRIM- were added. - Both the integer and polynomial factorization algorithms used by FCTR have been greatly improved. - The conversion from/to real numbers to/from binary integers is now done by ALG48's own routine. They do not depend any longer on the binary word size, and handle large numbers correctly. - Many speed optimizations and minor bug fixes. Changes from version 2.0 to 2.1 ------------------------------- - Fixed bug so that SQ in symbolics would be handled properly. Changes from version 1.2 to 2.0 ------------------------------- - The command SQFF was replaced by the command FCTR that computes the complete (and not only square-free) factorization of a polynomials (or of an integer). - The commands RAT->, GCD, and LCM were added. - Further code optimizations and new ML routines have increased the speed on most operations by a factor 2 to 6. - Algebraic aliases where added for the basic operation commands (see Section 3). - The library can now be run from a covered port of a HP48GX safely and whithout affecting the performances. Changes from version 1.0 to 1.2 ------------------------------- - Large part of the library was rewritten to use better internal representations, faster algorithms and new ML routines. The net result is that version 1.2 is 5 to 10 times faster than version 1.0 for the simplifications and approximately twice as fast on the other operations. - Errors (Bad arguments, etc...) are now also handled correctly in the symbolic matrix operations (in some cases they would leave garbage on the stack in version 1.0); - The command Z2S to convert a long integer into a string was replaced by the command Z<->S that can perform the conversion in both directions. 6. CONTACT ========== Gifts :), bug reports, and constructive comments and suggestions can be addressed to Claude-Nicolas Fiechter Department of Computer Science University of Pittsburgh Pittsburgh, PA 15260, U.S.A. e-mail: fiechter@cs.pitt.edu or to Mika Heiskanen Jamerantaival 7 C 355 02150 Espoo Finland e-mail: mheiskan@delta.hut.fi APPENDIX ======== A. SIMPLIFICATION RULES FOR ASIM ================================ The table below lists the rules that ASIM uses to simplify and expand non-rational expressions. Converse rules are used to merge back the exponential and trigonometric functions remaining after the simplification. Here 'x' and 'y' stand for any subexpression, 'n' is any integer number and 'i' is the complex unit. Expression Simplified/Expanded Condition ------------------------------------------------------------- sq(sqrt(x)) x sq(i) -1 sq(cos(x)) 1-sq(sin(x)) sq(tan(x)) sq(sin(x)/cos(x)) sq(cosh(x)) 1+sq(sinh(x)) sq(tanh(x)) sq(sinh(x)/cosh(x)) sq(x^y) x^(2*y) e^x exp(x) if x nonreal (-x)^n x^n if n even sqrt(x)^n x^n/2 if n even i^n 1, i, -1, -i depending on n exp(x)^y exp(y*x) if y nonreal alog(x)^y alog(y*x) if y nonreal sqrt(x^2) x sqrt(x^n) x^(n/2) n even sqrt(x^n) sqrt(x)*x^(n-1)/2 n odd sqrt(xy) sqrt(x)*sqrt(y) sqrt(x/y) sqrt(x)/sqrt(y) sqrt(-x) sqrt(x)*i sqrt(a*sqrt(x)+b) c+d*sqrt(x) for integer solutions exp(0) 1 exp(1) e exp(-1) inv(e) exp(pi*i) -1 exp(x) e^x if x is real exp(ln(x)) x exp(-x) inv(exp(x)) exp(x+y) exp(x)*exp(y) exp(x-y) exp(x)/exp(y) exp(xy) exp(y)^x if x is real alog(n) integer alog(log(x)) x alog(-x) inv(alog(x)) alog(x+y) alog(x)*alog(y) alog(x-y) alog(x)/alog(y) alog(xy) alog(y)^x if x is real ln(1) 0 ln(e) 1 ln(-1) pi*i ln(i) pi*i/2 ln(exp(x)) x ln(xy) ln(x)+ln(y) ln(x/y) ln(x)-ln(y) ln(x^y) y*ln(x) ln(inv(x)) -ln(x) ln(sqrt(x)) ln(x)/2 log(1) 0 log(alog(x)) x log(xy) log(x)+log(y) log(x/y) log(x)-log(y) log(x^y) y*log(x) log(inv(x)) -log(x) log(sqrt(x)) log(x)/2 sin(asin(x)) x sin(acos(x)) sqrt(1-x^2) sin(atan(x)) x/sqrt(1+x^2) sin(-x) -sin(x) cos(acos(x)) x cos(asin(x)) sqrt(1-x^2) cos(atan(x)) 1/sqrt(1+x^2) cos(-x) cos(x) tan(atan(x)) x tan(asin(x)) x/sqrt(1-x^2) tan(acos(x)) sqrt(1-x^2)/x tan(-x) -tan(x) asin(0) 0 atan(0) 0 sinh(0) 0 sinh(asinh(x)) x sinh(atanh(x)) x/sqrt(1-x^2) cosh(0) 1 cosh(acosh(x)) x cosh(asinh(x)) sqrt(1+x^2) cosh(atanh(x)) 1/sqrt(1-x^2) tanh(0) 0 tanh(atanh(x)) x tanh(asinh(x)) -i*x/sqrt(1+x^2) asinh(0) 0 atanh(0) 0 inv(i) -i inv(inv(x)) x x/sqrt(x) sqrt(x) sin(x)/cos(x) tan(x) sin(x)/tan(x) cos(x) cos(x)*tan(x) sin(x) tan(x)/sin(x) 1/cos(x) abs(abs(x)) abs(x) abs(re(x)) re(x) abs(im(x)) im(x) abs(pi) pi abs(e) e abs(i) 1 abs(-x) abs(x) re(re(x)) re(x) re(im(x)) im(x) re(conj(x)) re(x) re(abs(x)) abs(x) re(pi) pi re(e) e re(i) 0 re(-x) -re(x) re(x+y) re(x)+re(y) re(x-y) re(x)-re(y) im(im(x)) 0 im(re(x)) 0 im(conj(x)) -im(x) im(abs(x)) 0 im(pi) 0 im(e) 0 im(i) 1 im(-x) -im(x) im(x+y) im(x)+im(y) im(x-y) im(x)-im(y) conj(conj(x)) x conj(re(x)) re(x) conj(im(x)) im(x) conj(abs(x)) abs(x) conj(pi) pi conj(e) e conj(i) -i conj(-x) -conj(x) conj(x+y) conj(x)+conj(y) conj(x-y) conj(x)-conj(y) In addition, ASIM substitutes the exact value of the trigonometric functions for arguments that are integer multiples of Pi, Pi/2 and Pi/4. B. COMMAND REFERENCE ==================== We give below a listing of all the commands provided by ALG48 with stack diagrams showing the argument(s) they require. We use the following abbreviations x or y - Real numbers. z - Integer real number. n - Positive integer real number. #z - Unlimited precision binary integer (hexstring). #n - Positive binary integer (hexstring). "z" - Character string representing an integer number in decimal. 'symb' - Symbolic expression or variable. s - Scalar (real number, variable or symbolic expression). { vector } - Symbolic vector, represented by a list of the form {A1 .. An} where each Ai is a scalar. {{ matrix }} - Symbolic matrix, represented by a list of the form {{A11..A1m} .. {An1..Anm}} where each Aij is a scalar. {{ sq-matrix }} - Square symbolic matrix. { s-list } - List whose elements are either scalars or s-list themselves (includes {vector} and {{matrix}}). The entries marked with an asterisk (*) in the stack diagrams are the operations affected by the status of the automatic simplification flag (see Section 4.4). RSIM - Rational simplification command ---------------------------------------- 'symb_1' -> 'symb_2' { s-list_1 } -> { s-list_2 } z -> z FCTR - Factorization command ------------------------------ 'symb_1' -> 'symb_2' { s-list_1 } -> { s-list_2 } z -> z #z -> { #z1 #z2 ... #zk } "z" -> 'z1*z2* ... * zk' AADD - Algebraic addition command ----------------------------------- {{ matrix_1 }} {{ matrix_2 }} -> {{ matrix_2 + matrix_1 }} (*) { vector_1 } { vector_2 } -> { vector_2 + vector_1 } (*) {{ sq-matrix }} s -> {{ I*s + sq_matrix }} (*) s {{ sq-matrix }} -> {{ sq_matrix + I*s }} (*) 'symb_1' 'symb_2' -> 'symb_2+symb_1' (*) 'symb' x -> 'x+symb' (*) x 'symb' -> 'symb+x' (*) #z1 #z2 -> #z3 #z1 z2 -> #z3 z1 #z2 -> #z3 ASUB - Algebraic subtraction command -------------------------------------- {{ matrix_1 }} {{ matrix_2 }} -> {{ matrix_2 - matrix_1 }} (*) { vector_1 } { vector_2 } -> { vector_2 - vector_1 } (*) {{ sq-matrix }} s -> {{ I*s - sq_matrix }} (*) s {{ sq-matrix }} -> {{ sq_matrix - I*s }} (*) 'symb_1' 'symb_2' -> 'symb_2-symb_1' (*) 'symb' x -> 'x-symb' (*) x 'symb' -> 'symb-x' (*) #z1 #z2 -> #z3 #z1 z2 -> #z3 z1 #z2 -> #z3 AMUL - Algebraic multiplication command ----------------------------------------- {{ matrix_1 }} {{ matrix_2 }} -> {{ matrix_2 * matrix_1 }} (*) {{ matrix }} { vector } -> { matrix * vector } (*) { vector } {{ matrix }} -> {{ matrix * vector }} (*) {{ matrix }} s -> {{ s * matrix }} (*) s {{ matrix }} -> {{ matrix * s }} (*) { vector } s -> { s * vector } (*) s { vector } -> { vector * s } (*) 'symb_1' 'symb_2' -> 'symb_2*symb_1' (*) 'symb' x -> 'x*symb' (*) x 'symb' -> 'symb*x' (*) #z1 #z2 -> #z3 #z1 z2 -> #z3 z1 #z2 -> #z3 ADIV - Algebraic division command ----------------------------------- {{ matrix }} {{ sq-matrix }} -> {{ matrix * (sq-matrix)^-1 }} (*) { vector } {{ sq-matrix }} -> { vector * (sq-matrix)^-1 } (*) s {{ sq-matrix }} -> {{ s * (sq-matrix)^-1 }} (*) {{ matrix }} s -> {{ matrix / s }} (*) { vector } s -> { vector / s } (*) 'symb_1' 'symb_2' -> 'symb_1/symb_2' (*) 'symb' x -> 'symb/x' (*) x 'symb' -> 'x/symb' (*) x y -> 'x/y' (*) #z1 #z2 -> #z3 #z1 z2 -> #z3 z1 #z2 -> #z3 APOW - Algebraic exponentiation command --------------------------------------- {{ sq-matrix }} z -> {{ (sq-matrix)^z }} (*) 'symb' z -> 'symb^z' (*) #z1 #n -> #z2 #z1 n -> #z2 z1 #n -> #z2 ANEG - Algebraic negation command ----------------------------------- { s-list_1 } -> { s-list_2 } 'symb' -> '-symb' #z1 -> #z2 AINV - Algebraic inverse command ---------------------------------- {{ sq-matrix }} -> {{ (sq-matrix)^-1 }} (*) 'symb' -> 'INV(symb)' (*) x -> '1/x' (*) MDET - Symbolic matrix determinant ------------------------------------ {{ sq-matrix }} -> 'det(sq-matrix)' MADJ - Symbolic adjoint matrix -------------------------------- {{ sq-matrix_1 }} -> {{ sq-matrix_2 }} MTRN - Symbolic matrix transpose ---------------------------------- {{ matrix_1 }} -> {{ matrix_2 }} { vector } -> {{ matrix }} MIDN - Symbolic identity matrix --------------------------------- n -> {{ (n x n) identity-matrix }} Z<->S or ZS - Conversion from unlimited precision integer to string --------------------------------------------------------------------- #z -> "z" "z" -> #z Z -> #z GCD - Greatest Common Divisor command --------------------------------------- 'poly_1' 'poly_2' -> 'poly_gcd' 'poly' x -> z x 'poly' -> z z1 z2 -> z3 z1 #z2/"z2" -> #z3 #z1/"z1" z2/#z2/"z2" -> #z3 LCM - Least Common Multiple command ------------------------------------- 'poly_1' 'poly_2' -> 'poly_lcm' 'poly' x -> 'poly_lcm' x 'poly' -> 'poly_lcm' z1 z2 -> z3 z1 #z2/"z2" -> #z3 #z1/"z1" z2/#z2/"z2" -> #z3 RAT-> - Rational to stack command --------------------------------- 'rational function' -> 2: 'numerator' 1: 'denominator' x -> 2: x 1: 1.0 ASIM - Algebraic simplification command ---------------------------------------- 'symb_1' -> 'symb_2' { s-list_1 } -> { s-list_2 } (x,y) -> 'x+y*i' z -> z MOD+ - Modular addition ------------------------- z1/#z1/"z1" z2/#z2/"z2" n/#n/"n" -> #z3 MOD- - Modular substraction ----------------------------- z1/#z1/"z1" z2/#z2/"z2" n/#n/"n" -> #z3 MOD* - Modular multiplication ------------------------------- z1/#z1/"z1" z2/#z2/"z2" n/#n/"n" -> #z3 MOD/ - Modular division ------------------------- z1/#z1/"z1" z2/#z2/"z2" n/#n/"n" -> #z3 MOD^ - Modular exponentiation ------------------------------- z1/#z1/"z1" n2/#n2/"n2" n/#n/"n" -> #z3 MODINV - Inverse modulo N --------------------------- z/#z/"z" n/#n/"n" -> #z2 PRIM? - Prime testing ----------------------- z/#z/"z" -> 0/1 PRIM+ - Next prime -------------------- z/#z/"z" -> #n PRIM- - Previous prime ------------------------ z/#z/"z" -> #n