1 #include "polynomial_adt.h"
3 PolyAdt *create_adt(int hp)
5 PolyAdt *pAdt = malloc(sizeof(PolyAdt));
15 void insert_term(PolyAdt *pAdt, float c, int e)
17 assert(pAdt != NULL); //assume client code didnt call create_adt()
18 Node *n = malloc(sizeof(Node));
20 if(pAdt->head == NULL)
21 pAdt->head = create_node(c, e, pAdt->head);
23 for(n = pAdt->head; n->next != NULL; n = n->next); //go to the end of list
24 n->next = create_node(c, e, NULL);
29 PolyAdt *polyImage(const PolyAdt *orig)
31 PolyAdt *img = create_adt(orig->hp);
32 Node *origHead = orig->head;
34 for(; origHead; origHead = origHead->next)
35 insert_term(img, origHead->coeff, origHead->exp);
39 PolyAdt *add(const PolyAdt *a, const PolyAdt *b)
45 assert(a != NULL && b != NULL);
47 int hpow = max(a->hp, b->hp);
48 sum = create_adt(hpow); //create space for it
50 /* using state machine to compare the poly with the most terms to
51 ** the poly with fewer, round robin type of effect comparison of
52 ** exponents => 3 Cases: Equal, Less, Greater
54 n = a->head; np = b->head;
56 /* compare the exponents */
57 if(n->exp == np->exp){
58 insert_term(sum, n->coeff + np->coeff, n->exp);
63 else if(n->exp < np->exp){
64 insert_term(sum, np->coeff, np->exp);
65 np = np->next; //move to next term of b
69 insert_term(sum, n->coeff, n->exp);
72 /* check whether at the end of one list or the other */
73 if(np == NULL && state){ //copy rest of a to sum
74 for(; n != NULL; n = n->next)
75 insert_term(sum, n->coeff, n->exp);
79 if(n == NULL && state){
80 for(; np != NULL; np = np->next)
81 insert_term(sum, np->coeff, np->exp);
88 PolyAdt *subtract(const PolyAdt *a, const PolyAdt *b)
90 assert(a != NULL && b != NULL);
92 PolyAdt *tmp = create_adt(b->hp);
95 for(bptr = b->head; bptr != NULL; bptr = bptr->next)
96 insert_term(tmp,-bptr->coeff,bptr->exp); //negating b's coeffs
100 PolyAdt *multiply(const PolyAdt *a, const PolyAdt *b)
102 assert(a != NULL && b != NULL);
104 //the polys are inserted in order for now
105 PolyAdt *prod = create_adt(a->head->exp + b->head->exp);
106 Node *n = a->head, *np = b->head;
109 if(a->terms < b->terms){
114 for(; n != NULL; n = n->next){
115 np = t; //reset to the beginning
116 for(; np != NULL; np = np->next){ //always the least term in this loop
117 insert_term(prod, n->coeff * np->coeff, n->exp + np->exp);
124 PolyAdt *derivative(const PolyAdt *a)
128 PolyAdt *deriv = create_adt(a->head->exp - 1);
131 for(; n != NULL; n = n->next){
132 if(n->exp == 0) break;
133 insert_term(deriv, n->coeff * n->exp, n->exp-1);
138 PolyAdt *integrate(const PolyAdt *a)
142 PolyAdt *integrand = create_adt(a->head->exp + 1);
145 for(n = a->head; n != NULL; n = n->next) //very simple term by term
146 insert_term(integrand, (float)n->coeff/(n->exp+1.0F), n->exp + 1);
151 void quadratic_roots(const PolyAdt *a, float *real, float *cplx)
155 float dscrmnt, _a, b, c;
159 _a = n->coeff; b = n->next->coeff; c = n->next->next->coeff;
161 dscrmnt = (b*b) - 4*_a*c;
162 u = -b/(2*_a); v = sqrt((double)fabs(dscrmnt))/(2*_a);
164 if((real && !cplx) || (!real && cplx))
167 if(real == NULL && cplx == NULL){
168 if(a->hp != 2 && a->terms < 3){
169 printf("Invalid Quadratic*, A and B must be non-zero");
174 printf("X = %.2f +/- %.2f%c\n",u,v,dscrmnt < 0 ? 'I':' ');
176 printf("(X %c %.2f)(X %c %.2f)\n",sgn(u),fabs(u),sgn(u),fabs(u));
177 printf("X1,2 = %.2f\n",u);
180 //save values in pointers
182 if(dscrmnt < 0){ //x = u +/- vI Re(x) = u, Im(x) = +v
184 *cplx = v; //understand +/- is not representable
186 else if(dscrmnt == 0){
197 PolyAdt *exponentiate(const PolyAdt *a, int n)
201 PolyAdt *expn = create_adt(a->hp * n);
202 PolyAdt *aptr = polyImage(a);
205 //check default cases before calculation
207 insert_term(expn, 1, 0);
215 aptr = multiply(aptr, aptr);
217 if(n % 2) //odd exponent do a^(n-1) * a = a^n
218 expn = multiply(aptr, a);
224 PolyAdt *compose(const PolyAdt *p, const PolyAdt *q)
228 PolyAdt *comp = create_adt(p->head->exp * q->head->exp);
236 if(p->terms < q->terms){
242 /* going through, exponentiate each term with the exponent of p */
243 for(; pp != NULL; pp = pp->next){
244 exp = exponentiate(swap ? p: q, pp->exp);
245 insert_term(comp, pp->coeff * exp->head->coeff, exp->head->exp);
251 void destroy_poly(PolyAdt *poly)
253 Node *ps = poly->head;
260 poly->hp = poly->terms = 0;
264 void display_poly(const PolyAdt *a)
269 for(n = a->head; n != NULL; n = n->next){
271 n->coeff < 0 ? putchar('-') : putchar('+');
273 printf(" %.2f ",fabs(n->coeff));
274 else if(n->coeff == 1)
275 printf(" X^%d ",n->exp);
277 printf(" %.2fX ",fabs(n->coeff));
278 else if(n->coeff == 0)
281 printf(" %.2fX^%d ",fabs(n->coeff),n->exp);