2 ** A polynomial module with
3 ** ability to add,sub,mul derivate/integrate, compose ... polynomials
4 ** ..expansion in progress ...
5 * Copyright (c) 2009 I. Soule
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 ** iasoule32@gmail.com
32 #ifndef __POLYNOMIAL_ADT
33 #define __POLYNOMIAL_ADT
40 #define max(a, b) (a) > (b) ? (a) : (b)
41 #define sgn(a) (a) < 0 ? '+' : '-' //for quadratic factored form
49 typedef struct polynomial_adt {
51 int terms, hp; //hp highest power
55 * create_adt - create a polynomial on the heap
56 * @hp: the highest power in the polynomial
58 PolyAdt *create_adt(int hp);
61 * create_node - creates a Node (exponent, constant and next pointer) on the heap
62 * @constant: the contant in the term
63 * @exp: the exponent on the term
64 * @next: the next pointer to another term in the polynomial
66 * This should not be called by client code (hence marked static)
67 * used to assist insert_term()
69 static inline Node *create_node(float constant, int exp, Node *next) {
70 Node *nNode = malloc(sizeof(Node));
71 assert(nNode != NULL);
74 nNode->coeff = constant;
80 * insert_term - inserts a term into the polynomial
81 * @pAdt: the polynomial
82 * @c: constant value on the term
83 * @e: the exponent on the term
85 void insert_term(PolyAdt *pAdt, float c, int e);
88 * polyImage - returns an image (direct) copy of the polynomial
89 * @orig: the polynomial to be duplicated
91 PolyAdt *polyImage(const PolyAdt *orig);
95 * add - adds two polynomials together, and returns their sum (as a polynomial)
96 * @a: the 1st polynomial
97 * @b: the 2nd polynomial
99 PolyAdt *add(const PolyAdt *a, const PolyAdt *b);
102 * sub - subtracts two polynomials, and returns their difference (as a polynomial)
103 * @a: the 1st polynomial
104 * @b: the 2nd polynomial
105 * Aids in code reuse by negating the terms (b) and then calls the add() function
107 PolyAdt *subtract(const PolyAdt *a, const PolyAdt *b);
110 * multiply - multiply two polynomials, and returns their product (as a polynomial)
111 * @a: the 1st polynomial
112 * @b: the 2nd polynomial
114 PolyAdt *multiply(const PolyAdt *a, const PolyAdt *b);
117 * derivative - computes the derivative of a polynomial and returns the result
118 * @a: the polynomial to take the derivative upon
120 PolyAdt *derivative(const PolyAdt *a);
123 * integrate - computes the integral of a polynomial and returns the result
124 * @a: the polynomial to take the integral of
126 * Will compute an indefinite integral over a
128 PolyAdt *integrate(const PolyAdt *a);
131 * quadratic_roots - finds the roots of the polynomial ax^2+bx+c, a != 0 && b != 0
133 * @real: a pointer to float of the real(R) part of a
134 * @cplx: a pointer to float of the imaginary(I) part of a
137 * Two options can be done by the client
138 * 1. Either pass NULL to real and cplx
139 * this will display the roots by printf
140 * quadratic_roots(myPolynomial, NULL, NULL);
142 * 2. Pass in pointers** to type float of the real and complex
143 * if the discriminant is >0 cplx = -ve root of X
144 * quadratic_roots(myPolynomial, &realPart, &complexPart);
146 void quadratic_roots(const PolyAdt *a, float *real, float *cplx);
149 * exponentiate - computes polynomial exponentiation (P(x))^n, n E Z*
152 * Works fast for small n (n < 8) currently runs ~ O(n^2 lg n)
154 PolyAdt *exponentiate(const PolyAdt *a, int n);
157 * compose - computes the composition of two polynomials P(Q(x)) and returns the composition
158 * @p: polynomial P(x) which will x will be equal to Q(x)
159 * @q: polynomial Q(x) which is the argument to P(x)
161 PolyAdt *compose(const PolyAdt *p, const PolyAdt *q);
164 * destroy_poly - completely frees the polynomial from the heap and resets all values
165 * @poly: the polynomial to release memory back to the heap
167 * destroy_poly(myPoly); //puts polynomial on free list
169 void destroy_poly(PolyAdt *poly);
172 * display_poly - displays the polynomial to the console in nice format
173 * @a: the polynomial to display
175 void display_poly(const PolyAdt *a);