Multiplication of Polynomials

Polynomials like 5x4+2x3+7x2+10x-8 can be maintained using a linked list. To achieve this each node should consists of three elements, namely coefficient, exponent and a link to the next term. While maintaining the polynomial it is assumed that the exponent of each successive term is less than that of the previous term. Once we build a linked list to represent a polynomial we can use such lists to perform common polynomial operations like addition and multiplication. The following program carry out multiplication of the two polynomials:

/* Program to multiply two polynomials maintained as linked lists */
#include "alloc.h"

/* structure representing a node of a linked list. The node can store a term of a polynomial */
struct polynode
{

float coeff ;
int exp ;
struct polynode *link ;

} ;

void poly_append ( struct polynode **, float, int ) ;
void poly_multiply ( struct polynode *, struct polynode *,
struct polynode ** ) ;
padd ( float, int, struct polynode ** ) ;

main( )
{

struct polynode *first, *second, *mult ;
int i = 1 ;

first = second = mult = NULL ; /* empty linked lists */

poly_append ( &first, 3, 5 ) ;
poly_append ( &first, 2, 4 ) ;
poly_append ( &first, 1, 2 ) ;

clrscr( ) ;
display_poly ( first ) ;

poly_append ( &second, 1, 6 ) ;
poly_append ( &second, 2, 5 ) ;
poly_append ( &second, 3, 4 ) ;

printf ( "\n\n" ) ;
display_poly ( second ) ;

printf ( "\n" );
while ( i++ < 79 )
printf ( "-" ) ;

poly_multiply ( first, second, &mult ) ;

printf ( "\n\n" ) ;
display_poly ( mult ) ;

}

/* adds a term to a polynomial */
void poly_append ( struct polynode **q, float x, int y )
{

struct polynode *temp ;
temp = *q ;

/* create a new node if the list is empty */
if ( *q == NULL )
{

*q = malloc ( sizeof ( struct polynode ) ) ;
temp = *q ;

}

else

{

/* traverse the entire linked list */
while ( temp -> link != NULL )

temp = temp -> link ;

/* create new nodes at intermediate stages */
temp -> link = malloc ( sizeof ( struct polynode ) ) ;
temp = temp -> link ;

}

/* assign coefficient and exponent */

temp -> coeff = x ;
temp -> exp = y ;
temp -> link = NULL ;

}

/* displays the contents of linked list representing a polynomial */
display_poly ( struct polynode *q )
{

/* traverse till the end of the linked list */
while ( q != NULL )
{

printf ( "%.1f x^%d : ", q -> coeff, q -> exp ) ;

q = q -> link ;

}

printf ( "\b\b\b " ) ; /* erases the last colon(:) */

}

/* multiplies the two polynomials */
void poly_multiply ( struct polynode *x, struct polynode *y, struct polynode **m )
{

struct polynode *y1 ;
float coeff1, exp1 ;

y1 = y ; /* point to the starting of the second linked list */

if ( x == NULL && y == NULL )

return ;

/* if one of the list is empty */
if ( x == NULL )

*m = y ;

else
{

if ( y == NULL )

*m = x ;

else /* if both linked lists exist */
{

/* for each term of the first list */
while ( x != NULL )

{

/* multiply each term of the second linked list with a
term of the first linked list */

while ( y != NULL )

{

coeff1 = x -> coeff * y -> coeff ;

exp1 = x -> exp + y -> exp ;

y = y -> link ;

/* add the new term to the resultant polynomial */
padd ( coeff1, exp1, m ) ;

}

y = y1 ; /* reposition the pointer to the starting of the second linked list */

x = x -> link ; /* go to the next node */

}

}

}

}

/* adds a term to the polynomial in the descending order of the exponent */
padd ( float c, int e, struct polynode **s )
{

struct polynode *r, *temp = *s ;

/* if list is empty or if the node is to be inserted before the first node */
if ( *s == NULL || e > ( *s ) -> exp )
{

*s = r = malloc ( sizeof ( struct polynode ) ) ;
( *s ) -> coeff = c ;
( *s ) -> exp = e ;
( *s ) -> link = temp ;

}
else
{

/* traverse the entire linked list to search the position to insert a new node */
while ( temp != NULL )
{

if ( temp -> exp == e )
{

temp -> coeff += c ;
return ;

}

if ( temp -> exp > e && ( temp -> link -> exp < e || temp -> link == NULL ) )
{

r = malloc ( sizeof ( struct polynode ) ) ;
r -> coeff = c;
r -> exp = e ;
r -> link = temp -> link ;
temp -> link = r ;
return ;

}

temp = temp -> link ; /* go to next node */

}

r -> link = NULL ;
temp -> link = r ;

}

}

In this program once again the poly_append( ) function is called to build the two polynomials. Followed by this, the poly_multiply( ) function is called to carry out the multiplication of the two polynomials. In this function if it is found that both the linked lists (representing the two polynomials being multiplied) are non-empty then the control goes in a pair of while loops. Here each term of the second polynomial is multiplied with every term of the first polynomial. As this proceeds and a new term is built, the function p_add( ) is called to add this term to the resulting polynomial. In p_add( ) each term of the existing resulting polynomial is scanned to find whether there exists a term in this polynomial whose exponent is same as that of the term to be added. If it is so, then the corresponding coefficient of the existing polynomial is updated, otherwise the new term is simply appended to the end of the existing polynomial. Yet again the resulting polynomial is displayed using the function display_poly( ).