A very recent thread requesting an IRR calculation prompted me to think about polynomials in Oracle SQL and PL/SQL. This morning I decided to take the bull by the horns. I started working on a small project to implement a user-defined data type POLYNOMIAL, giving it all the methods normally associated with the concept in mathematics. In this post (and perhaps a few replies later in the thread) I will share my work with you. My main interest here is to learn more about PL/SQL and object-relational stuff, rather than "implementing polynomials" as the final goal. However, there may be some independent interest in polynomials too.
I will create a space for this on github - it's time for me to start learning and using that as well. (Also for practice/learning purposes more than anything else!) I can post a link to that when it's ready if anyone is interested.
Let it be clear from the outset - I am LEARNING most of the concepts and features I am using; so much of what I do may be wrong, or silly, or both. If anyone is tempted to take any code from here and use it for anything serious, they do so at their own peril.
Please let me know what you think about the overall approach, design, and the details of the code.
Theory
I assume most people are familiar with polynomials. To be precise, I mean polynomials in one variable (one "indeterminate") with real coefficients (that is, coefficients that are real numbers). It is sometimes also helpful to think of the more advanced concept of power series (also in one variable and over the real numbers) - those are formal INFINITE sums of the form a_0 + a_1 * T + a_2 * T^2...... Then we can think of polynomials as power series where only a finite number of coefficients are non-zero.
A polynomial is completely determined by (and therefore it can be modeled as its) sequence of coefficients. It is often convenient to think of them as a_0, a_1, ... , a_n : the constant term, the coefficient of T, the coefficient of T^2, etc. (representing them in our minds rather as a finite power series, starting from the constant term as we read them in order, rather than from the highest power of T).
A polynomial has more than one such representation: we may add more coefficients, all equal to zero, for HIGHER powers of T (higher than the highest non-zero coefficient). So, for example, 3 + 5 * T is the same as 3 + 5 * T + 0 * T^2 + 0 * T^3. We can always "trim" a polynomial by deleting the zero terms at the RIGHT END of the sequence of coefficients (when we think "left to right" as "constant term to higher powers of T"). Note however that the zero polynomial (with all coefficients equal to zero) can be "trimmed" TOO MUCH. For the zero polynomial, by convention, we "trim" it by still retaining the constant term.
The degree of a polynomial is the highest n for which a_n is non-zero. We need a special convention for the zero polynomial. In mathematics that is defined as minus-infinity, but it is more practical for our purposes to define it as -1. Note that "degree zero" is the same as "polynomial consisting of just a NON-ZERO constant term".
The ORDER of a power series (and therefore of a polynomial) is the LEAST n for which a_n is non-zero. The order of the zero power series (and the zero polynomial) in mathematics is defined as plus-infinity; however, for my purposes it's OK to define it as -1.
Type definition
A polynomial has a single attribute, a VARRAY of number (the array of coefficients). I need to keep in mind that in PL/SQL arrays are indexed from 1, not from 0 - quite a pain in the posterior. It ("a polynomial") has many methods; the names should be self-explanatory.
create or replace type coeff_array is array(1000000) of number;
/
create or replace type polynomial is object
( coeff coeff_array
, member function boolean_isvalid return boolean
, member function isvalid return integer
, member function deg return integer
, member function ord return integer
, member function trim return polynomial
, member function neg return polynomial
, member function plus(q polynomial) return polynomial
, member function eval(x number) return number
, member function deriv return polynomial
, member function tostring(ch varchar2 default 'X', ord varchar2 default 'desc') return varchar2
);
/
There will be more methods - multiply, long division, composite of two polynomials... I haven't implemented PLUS yet, I just have a placeholder in the type body. And, of course, a method to approximate the real roots, using Newton's method (and a few other, preliminary tools) - the original motivation for the whole thing.
I will show the body in a Reply, but here is one illustration of what I can do so far. The illustration uses .TOSTRING, a pretty useless method to pretty-print a polynomial in the usual manner; I wrote it so it can be either in ascending or descending order of powers of the variable, and the name of the variable is an input (default 'X', and default order is descending). I only wrote .TOSTRING for practice; the data type doesn't really need it. (But now that I wrote it, I can use it to see more easily the results of other methods.)
First I populate a table with polynomials, and then I show a SELECT statement and its output.
Note about NULL - I will discuss the different meanings in the first Reply below.
drop table t_poly purge;
create table t_poly (p polynomial);
insert into t_poly
select polynomial(coeff_array(1,-2,-1)) from dual
union all select polynomial(coeff_array(1,0,-1,.3)) from dual
union all select polynomial(coeff_array(1,0,0)) from dual
union all select polynomial(coeff_array(0,1,0)) from dual
union all select polynomial(coeff_array(0,0,0)) from dual
union all select polynomial(coeff_array(-0.2,0,-3.8,0,5)) from dual
union all select polynomial(coeff_array(1,3,null)) from dual
union all select polynomial(coeff_array()) from dual
union all select polynomial(null) from dual
union all select null from dual
;
commit;
select 'The derivative of p(x) = ' || t.p.tostring('x')
|| ' is p''(x) = ' || t.p.deriv().tostring('x') as str
from t_poly t
where t.p.isvalid() = 1;
STR
--------------------------------------------------------------------------------
The derivative of p(x) = - x^2 - 2 * x + 1 is p'(x) = -2 * x - 2
The derivative of p(x) = .3 * x^3 - x^2 + 1 is p'(x) = .9 * x^2 - 2 * x
The derivative of p(x) = 1 is p'(x) = 0
The derivative of p(x) = x is p'(x) = 1
The derivative of p(x) = 0 is p'(x) = 0
The derivative of p(x) = 5 * x^4 - 3.8 * x^2 - .2 is p'(x) = 20 * x^3 - 7.6 * x