# Univariate polynomial multiplication using Doubly Linked List

A univariate polynomial is a polynomial over a single variable, and in the following discussion when we say polynomial, we mean a polynomial in a single variable. You are given two polynomials – the first one, M1(x), is called the multiplicand, and the second one, M2(x), is called the multiplier. Your program has to output the product of M1(x) and M2(x). You could use the functions implemented in the lectures to maintain your lists corresponding to the polynomials. Below, you find a formal description of the inputs and outputs.

INPUT & OUTPUT:

The input will be four lines in the format specified below:

Line 1: Number of terms in multiplicand
e.g: 2

Line 2: Coefficients and exponents in the multiplicand in the format coeff 1 exp1 coeff2 exp2
e.g: 2 2 1 0 which represents 2x^2+1

Line 3: Number of terms in multiplier.
e.g: 3

Line 4: Coefficients and exponents in the multiplier in the format coeff 1 exp1 coeff2 exp2 ....
e.g: -23 12 11 10 -6 41 which represents -6x^41-23x^12+11x^10

Each line will have multiple sets of coeff exp pairs, each corresponding to a non zero coefficient in the corresponding polynomial. The output has to be a single polynomial in ‘x’ that is the product polynomial. Note that, in the input, for each exponent, there may be multiple terms with the same exponent. However you should print a single term for each exponent while you print the output. Also, if the resulting product is zero, you have to explicitly print a zero.

The output has to be displayed as in the sample output shown with decreasing value of exponent.

Sample Input:

2
2 1 1 0
2
3 2 2 0


Sample Output:

6x^3+3x^2+4x+2


#include<stdio.h>
#include<stdlib.h>
#include<stddef.h>
#include<string.h>

typedef struct Dcontainer
{
int coeff;
int exp;
struct Dcontainer *prev;
struct Dcontainer *next;
}DL_node;

void DswapElement(DL_node* position1,DL_node* position2)
{
int etemp,ctemp;
if((position1 == NULL) || (position2 == NULL)) return;
etemp = position1->exp;
ctemp = position1->coeff;
position1->exp   = position2->exp;
position1->coeff = position2->coeff;
position2->exp   = etemp;
position2->coeff = ctemp;
}

DL_node *Dlast(DL_node* list)
{
if(list == NULL) return list;
while(list->next != NULL)
{
list = list->next;
}
return list;
}

DL_node * partition(DL_node *l, DL_node *h)
{
// set pivot as h element
int x  = h->exp;
int etemp;
int ctemp;
// similar to i = l-1 for array implementation
DL_node *i = l->prev;
DL_node *j;
// Similar to "for (int j = l; j <= h- 1; j++)"
for (j = l; j != h; j = j->next)
{
if (j->exp >= x)
{
// Similar to i++ for array
i = (i == NULL)? l : i->next;
ctemp    = i->coeff;
i->coeff = j->coeff;
j->coeff = ctemp;

etemp    = i->exp;
i->exp   = j->exp;
j->exp   = etemp;
}
}
i = (i == NULL)? l : i->next; // Similar to i++
DswapElement(i, h);
return i;
}

/* A recursive implementation of quicksort for linked list */
void _quickSort(DL_node* l, DL_node *h)
{
if (h != NULL && l != h && l != h->next)
{
DL_node *p = partition(l, h);
_quickSort(l, p->prev);
_quickSort(p->next, h);
}
}

// The main function to sort a linked list. It mainly calls _quickSort()
{
// Find last node

// Call the recursive QuickSort
}

DL_node* DinsertFirst(DL_node** poly_head, int coeff, int exp)
{
DL_node* new_node = (DL_node*)malloc(sizeof(DL_node));
new_node->coeff = coeff;
new_node->exp   = exp;
new_node->prev  = NULL;
}

void DinsertLast(DL_node** poly_head, int coeff, int exp)
{
DL_node* new_node = (DL_node*)malloc(sizeof(DL_node));

new_node->coeff = coeff;
new_node->exp   = exp;

new_node->next  = NULL;

{
new_node->prev = NULL;
return;
}

while(last->next != NULL)
{
last = last->next;
}

last->next     = new_node;

new_node->prev = last;
return;
}

DL_node* Mul(DL_node* poly1,DL_node* poly2)
{
//DL_node* new_DL_node;
DL_node* temp   = NULL;
//DL_node* last   = NULL;
DL_node* p1temp = poly1;
DL_node* p2temp = poly2;
int coeff,exp;
temp = (DL_node*)malloc(sizeof(DL_node));
temp->next = NULL;

while(p1temp != NULL )
{
p2temp = poly2;
while(p2temp != NULL)
{
coeff = p1temp->coeff * p2temp->coeff;
exp   = p1temp->exp    +  p2temp->exp;
//printf("%d %d \n ",coeff , exp);
p2temp = p2temp->next;
{
}
else
{
}
}
p1temp = p1temp->next;
//printf("%d %d \n ",p1temp->coeff,p1temp->exp);
}
}

void Dprint_list(DL_node* poly)
{
while(poly != NULL)
{
printf("%d %d\t ",poly->coeff,poly->exp);
poly = poly->next;
}
printf("\n");
return;
}

void Purge(DL_node** poly)
{
DL_node *cr,*pr,*run,*temp,*del;
cr   = *poly;
cr   = cr->next;
pr   = *poly;
while(cr != NULL)
{
if((*poly)->exp == cr->exp)
{

(*poly)->coeff += cr->coeff;
temp        = cr->prev;
temp->next  = cr->next;
(temp->next)->prev = temp;
del         = cr;
cr          = cr->next;
free(del);
}
else
{
cr  = cr->next;
pr  = pr->next;
}
}
cr = *poly;
cr = cr->next;
pr = *poly;
while(cr != NULL)
{
run = *poly;
while(run != cr)
{
if(run->exp  == cr->exp)
{
{
run->coeff += cr->coeff;
}
temp        = cr->prev;
temp->next  = cr->next;
(temp->next)->prev = temp;
del         = cr;
cr          = cr->next;
free(del);
//                pr->next    = cr;
//                cr->prev    = pr;
}
run  = run->next;
}
if(run == cr)
{
cr   = cr->next;
pr   = pr->next;
}
}
cr   = *poly;
cr   = cr->next;
//printf("%d %d \n", pr->coeff,pr->exp);
while(cr != NULL)
{
if(pr->exp == cr->exp && pr != cr)
{

(pr)->coeff += cr->coeff;
temp        = cr->prev;
temp->next  = cr->next;
(temp->next)->prev = temp;
del         = cr;
cr          = cr->next;
free(del);
}
else
{
cr  = cr->next;
}
}
}
void Dprint_list_poly(DL_node* poly)
{
int flag = 1;  //1 to print +
int first=0;
while(poly != NULL)
{
if(poly->coeff !=0)
{
if(poly->exp == 0)
{first =1;flag =1;  printf("%d",poly->coeff);}
else if(poly->exp  == 1 && poly->coeff >1)
{first =1 ;flag = 1; printf("%dx",poly->coeff);}
else if(poly->exp  == 1 && poly->coeff ==1)
{first =1 ;flag = 1; printf("x");}
else if(poly->coeff == 1)
{first =1 ;flag =1;  printf("x^%d",poly->exp);}
else if(poly->coeff < 0 && poly->exp != 1)
{first =1 ;flag = 1; printf("%dx^%d",poly->coeff,poly->exp);}
else if(poly->coeff < 0 && poly->exp == 1)
{first =1 ;flag = 1; printf("%dx",poly->coeff);}
else
{first =1 ;flag = 1; printf("%dx^%d",poly->coeff,poly->exp);}
poly = poly->next;
if((poly)!=NULL && flag == 1 && first == 1 && ((poly->coeff)>0)) printf("+");
}
else
{
poly = poly->next;
if(poly != NULL && (poly->coeff)>0 && first == 1) printf("+");
flag = 0;
}
}
if(flag == 0) printf("0");
return;

}

int main()
{
DL_node* poly1 =  NULL;
DL_node* poly2 =  NULL;
DL_node* x;
int terms_1,terms_2;
char s_1[100];
char s_2[100];
int n1,n2;
int i =0;
int temp;
int coeff;
int exp;
//char l;
char delimiters[] = " ";
char *token;
int tuple = 1;
fscanf(stdin,"%d\n", &terms_1);
n1 = 100;
fgets(s_1,n1,stdin);
fscanf(stdin,"%d\n", &terms_2);
n2 = 100;
fgets(s_2,n2,stdin);

token = strtok (s_1, delimiters);

while( token != NULL )
{
//printf( " %s\n", token );
temp  = atoi(token);
if(tuple == 1)
{
coeff = temp;
tuple++;
}
else
{
exp = temp;
tuple--;
DinsertLast(&poly1, coeff, exp);
}
token = strtok(NULL, delimiters);
}
i = 0;

token = strtok (s_2, delimiters);      /* token => "words" */
while( token != NULL )
{
// printf( " %s\n", token );
temp  = atoi(token);
if(tuple == 1)
{
coeff = temp;
tuple++;
}
else
{
exp = temp;
tuple--;
DinsertLast(&poly2, coeff, exp);
}
token = strtok(NULL, delimiters);
}
//Dprint_list(poly1);
x =  Mul(poly1,poly2);
//Dprint_list(x);
Purge(&x);
//Dprint_list(x);
quickSort(&x);
//Dprint_list(x);
Dprint_list_poly(x);
return 0;
}

• @200_success, I have cited. – envy_intelligence Mar 21 '15 at 6:56

On a quick glance,

• You need a function to parse a polynomial. Copy-pasted while loop in main doesn't look good.

• quickSort is under-utilized. Sorting the polynomial by exponents at teh end of Mul would simplify Purge immensely.

• As coded Purge doesn't stand a criticism. A function composed of multiple loops, nested, and apparently (almost) copy-pasted is ill-concieved. Can you state the purpose of each loop?

• DinsertFirst communicates the result via return value and via the side effect. Do you have a justification for such redundancy? (BTW, DinsertLast only has side effect; I honestly recommend to stick to return value).

• Each monomial multiplication result is appended to the end of list. In other words, the list is traversed N*M times, bringing the complexity to $O((N*M)^2)$. Prepending results instead is a mere $O(N*M)$.

## Printing

To print each term, there are a multitude of considerations:

• If the coefficient is positive, is this the leading term?
• Is this the coefficient ±1, and if so, is it the constant term?
• Is the exponent 0 or 1 or something else?
• If the coefficient is 0, is the polynomial just a monomial?

You have a bit of a combinatorial explosion of cases to handle these considerations. I'm surprised that the code works as well as it does. It's not quite right, though. For example, for

1
-1 1
1
1 0


the result is conventionally rendered as -x, but you print -1x. Since you have two branches dealing with cases where poly->coeff == 1, you would need to add two branches to handle poly->coeff == -1 as well. I wonder why your poly->coeff == 1 tests are placed at the innermost level — this seems like awkward and redundant:

if(poly->coeff !=0)
{
…
else if(poly->coeff == 1)
{…}
…
}


All the places where you set first =1 ;flag =1; should be factored out. first feels perversely named to me, as it is set to 1 when this is not the first term. flag is also a poor variable name, as it provides little insight to its purpose.

## Purging

I'm not sure what you're doing, but having three loops that all do some variant of … += cr->coeff;, followed by list splicing, makes me suspicious.

When given dubious input, such as a zero-term polynomial…

1
1 3
0
0


Purge() segfaults attempting to do cr = cr->next; on an an empty list. Admittedly, the input is bad, but it's good practice to avoid crashing nonetheless.

My main criticism, though, is that you used linked lists at all in this solution. Linked lists come with many disadvantages:

• No random access; you have to traverse them one element at a time. It's hard to sort a linked list efficiently, for example.
• Memory overhead and fragmentation. Storing forward and backward pointers already doubles your storage size. Add to that the space needed by malloc() to do its bookkeeping for each tiny allocation. Making lots of small allocations and deallocations is also leaves your heap in a sorry state.
• There is no built-in support in the C library for linked lists, perhaps due to those issues. As a result, you end up reinventing the wheel. Who wants to write, verify, and maintain yet another linked list implementation? After you've done that exercise once as a beginner, nobody wants to do it again.

There are occasional situations where linked lists may be justified. This is definitely not one of them, especially since the input format is designed to let you know in advance the size of the inputs, which gives you an upper bound on the size of the result. You would be much better off using a dynamically sized array — even if it means copy-moving some entries. (You're already copy-moving entries within your "quicksort" implementation instead of adjusting pointers. The difference is that list traversal is more cumbersome with linked lists than arrays.)

One strength of linked lists is that you can splice out one element relatively easily. However, when you coalesce all of the terms of the polynomial with same exponents, you are deleting many elements, and can do so in one pass through the list. Whether you use an array or linked list, the purge operation is going to be O(n), where n is the number of terms in the unsimplified representation. So that justification for linked lists disappears as well.

To illustrate the complication brought about by using linked lists, consider the following solution using dynamic arrays. Partly because I don't have to write all that linked list support, and can take advantage of the C library's built-in qsort(), it's only 1/3 as many lines of code as yours. It should also perform better, and, in my opinion, it's easier to read.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
int coeff;
int exp;
} Term;

typedef struct {
size_t len;
Term *terms;
} Polynomial;

static int term_desc_exp_comparator(const void *term_a, const void *term_b) {
return ((Term *)term_b)->exp - ((Term *)term_a)->exp;
}

static void canonicalize_polynomial(Polynomial *p) {
qsort(p->terms, p->len, sizeof(Term), term_desc_exp_comparator);
size_t out = 0;
for (size_t in = 1; in < p->len; in++) {
if (p->terms[out].exp == p->terms[in].exp) {
p->terms[out].coeff += p->terms[in].coeff;
} else if (p->terms[out].coeff == 0) {
p->terms[out] = p->terms[in];
} else {
p->terms[++out] = p->terms[in];
}
}

// Zero out the unused terms
for (size_t i = out + 1; i < p->len; i++) {
p->terms[i].exp = p->terms[i].coeff = 0;
}
p->len = out + 1;
}

Polynomial multiply_polynomials(Polynomial a, Polynomial b) {
Polynomial prod = {
.len   = a.len * b.len,
.terms = malloc(a.len * b.len * sizeof(Term))
};
size_t term_ct = 0;

// Crudely multiply all terms with each other
for (size_t i = 0; i < a.len; i++) {
for (size_t j = 0; j < b.len; j++) {
prod.terms[term_ct].coeff = a.terms[i].coeff * b.terms[j].coeff;
prod.terms[term_ct++].exp = a.terms[i].exp   + b.terms[j].exp;
}
}

assert(term_ct == prod.len);
canonicalize_polynomial(&prod);
return prod;
}

void print_polynomial(Polynomial p, const char *varname) {
if (p.len == 0 || (p.len == 1 && p.terms[0].coeff == 0)) {
puts("0");
return;
}
for (size_t i = 0; i < p.len; i++) {
switch (p.terms[i].coeff) {
case 0:
continue;
case -1:
putchar('-');
if (p.terms[i].exp == 0) putchar('1');
break;
case 1:
if (i) putchar('+');
if (p.terms[i].exp == 0) putchar('1');
break;
default:
printf(i ? "%+d" : "%d", p.terms[i].coeff);
}
switch (p.terms[i].exp) {
case 0:
break;
case 1:
printf("%s", varname);
break;
default:
printf("%s^%d", varname, p.terms[i].exp);
}
}
putchar('\n');
}

Polynomial input_polynomial() {
Polynomial p = { .len = 0, .terms = NULL };
if (scanf("%zd", &p.len) && (p.terms = calloc(p.len, sizeof(Term)))) {
for (size_t i = 0; i < p.len; i++) {
scanf("%d %d", &p.terms[i].coeff, &p.terms[i].exp);
}
}
return p;
}

void free_polynomial(Polynomial *p) {
free(p->terms);
p->terms = NULL;
p->len = 0;
}

int main() {
Polynomial a = input_polynomial();
Polynomial b = input_polynomial();

Polynomial prod = multiply_polynomials(a, b);
print_polynomial(prod, "x");

free_polynomial(&a);
free_polynomial(&b);
free_polynomial(&prod);
}