Next: Remarks
Up: Commands Previous:
Modular arithmetic on
unlimited
Algebraic computations, like the simplification, factorization, partial fraction expansion or integration of rational functions, are complex operations and are generally time-consuming for non-trivial problems. Therefore, even though ALG48 is written in sysRPL and machine language, any operation that involves such operations is not instantaneous on the HP48.
ALG48 version 4.2 can nevertheless perform most simplifications quite quickly. Section 2 gives some examples with their timings. [The times given throughout this document were obtained on a HP48GX with approximately 60Kb of free memory.] Even complex simplifications can be handled in a reasonable amount of time. For instance, ALG48 version 4.2 takes only 8s to simplify the relatively large three-variable rational below.
ALG48 is also 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:
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.
The factorization of polynomials is comparatively slow, especially for multivariate problems. Simple factorizations, however, are performed quite fast. For instance, FCTR takes only slightly more than 2s on the following example:
Even some seemingly complex factorizations can be performed quickly, like the following one, taken from Mathematica's book, that ALG48 solves in 15s,
ALG48 version 4.2 uses Berlekamp p-adic factorization algorithm and, given enough time, can compute the complete factorization of virtually any polynomials (up to degree 256), even if they are square-free and contain high-degree factors. E.g.,
Even large multivariate polynomials can be handled in a reasonable amount of time. For instance, ALG48 can factor the numerator and the denominator of the large three-variable rational above in about a minute.
As a first approximation, the running time of the
simplification and factorization algorithms used in ALG48
increases exponentially with the number of variables and
polynomially (but fast --like ) with the
maximum total degree n of the polynomials involved. In
theory the factorization algorithm can also take exponential time
in the degree of the polynomial, but this is usually not the case
in practice. However, as illustrated by the examples above, the
actual time taken by the simplification and factorization
commands varies greatly depending on the properties of the
polynomial involved (e.g., whether the polynomial is square-free
or not, whether the factors are all linears, etc.).
Next: Remarks
Up: Commands Previous:
Modular arithmetic on
unlimited