|Quiz !: Evaluating polynomials [LONG]|
Message #1 Posted by Valentin Albillo on 8 July 2003, 1:19 p.m.
Though noone posted a solution to my latest HP-15C Quiz/Challenge,
"Matrix Trilogy", and though it's pretty clear to me by now that most
people participating in this forum are hardware/collector-oriented,
being the unrepentant software guy that I am, here is yet another
HP-15C Quiz/Challenge for you to try, the last one for a number
of months to come.
By the way, let me point it out once more that though the challenge's
conditions and requirements are meant for an HP-15C, the techniques
used in the solution are always equally efficient and thus applicable
to other machines, most specially the 42S, 41C/Advantage, and even
the 71B/Math, among others. You can attempt the challenge in said
machines as well, and the published solution can give you a
particularly efficient and novel implementation on your machine as well, which you might easily find useful for your own programs.
Let's suppose that we've got some experimental or otherwise dataset
and we have have fitted some suitable mathematical function to it, a rational
function to be precise:
f(x) = P(x) / Q(x)
where P(x) and Q(x) are both polynomials of arbitrary degree n, i.e:
where the degree, n, is nominally the same for both, but as any of
the ai, bi coefficients can be zero, the actual degrees could be
P(x) = a0 + a1 x + a2 x^2 + ... + an x^n
Q(x) = b0 + b1 x + b2 x^2 + ... + bn x^n
Now, for the challenge. You must write a subroutine (LBL, ..., RTN)
which must use as fixed data the coefficients ai, bi, which will
be stored in a (2 x [n+1]) matrix, in the exact way and order shown below:
This matrix isn't to be considered a parameter passed to the
subroutine, but a fixed data repository at a fixed place,
matrix A. The degree, n, isn't passed either, the subroutine must
deduce it from the number of columns in matrix A.
A = | a0 a1 a2 ... an |
| b0 b1 b2 ... bn |
The only parameter which will be passed, in the X register, is
a value x for which we want the above expression f(x) to be
evaluated. The routine will evaluate f(x) = P(x)/Q(x) for such
an x, and will return the result in the X register, i.e:
x, GSB A -> f(x)
An example will make it clear: If we have:
-2 + 3x - 5x^2 + 4x^3
f(x) = ----------------------
5 - 6x + 3x^2 - 7x^3
then our routine must use matrix A, which holds the coefficients:
A = | -2 3 -5 4 |
| 5 -6 3 -7 |
and x = 2.3, to return f(x) = -0.3472259...
As the subroutine is meant to be used a number of times
to evaluate the function, matrix A shouldn't be altered
at all between calls. That given, the primary and main requirement is to optimize for speed, i.e.,
f(x) must be evaluated as fast as possible. Once time is minimized,
the shorter the subroutine, the better.
Subject to that, there exists a general solution for the HP-15C in 18 steps
or less (including both LBL and RTN) which will evaluate f(x) in just
4 seconds for polinomials of the 4th degree, and in just 15 seconds
for 19th-degree polynomials.
If you succeed, try to generalize the routine in one or both
of these ways:
instead of a single x value, the routine would accept a vector
of x values and would return a vector with the corresponding
- instead of evaluating two polynomials, the routine would accept
the coefficients of m polynomials and would return the evaluated
values at x for all of them.
That's all. Give it a thought or two and let's see your ideas ... :-)
Edited: 9 July 2003, 9:55 a.m. after one or more responses were posted