How to multiply polynomials in C?

Question

I hope this code makes sense.....I create two polynomials and try to multiply them. The problem is that I don't know what I should do to multiply them properly. This programs multiplies the polynomials, stores the result to another polynomial but it doesn't add the coefficients with the same power.

What should I do in order to do that?? Also how should I use free() in this program?

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

typedef struct poly {
  int coef;
  int exp;
  struct poly *next;
} poly;

int main(void) {
  poly * po1, *head, *po2, *head2, *po3, *head3 = NULL;
  int sel, c = 1;

  head = NULL;
  printf(
      "\nInsert elements for the first polynomial from the biggest to the smallest power of x. (Enter a power of zero (0) to stop)\n");
  while (1) {
    po1 = (poly *) malloc(sizeof(poly));
    printf("Give number: ");
    scanf("%d", &po1->coef);
    printf("Give power of x: ");
    scanf("%d", &po1->exp);
    po1->next = head;
    head = po1;
    if (po1->exp == 0) break;
  }

  head2 = NULL;
  printf(
      "\nInsert elements for the second polynomial from the biggest to the smallest power of x. (Enter a power of zero (0) to stop)\n");
  while (1) {
    po2 = (poly *) malloc(sizeof(poly));
    printf("Give number: ");
    scanf("%d", &po2->coef);
    printf("Give power of x: ");
    scanf("%d", &po2->exp);
    po2->next = head2;
    head2 = po2;
    if (po2->exp == 0) break;
  }

  po1 = head;
  po2 = head2;

  printf("Multiplying********\n");
  po1 = head;
  po2 = head2;
  while (po1 || po2) {
    po2 = head2;
    while (po1 && po2) {
      po3 = (poly *) malloc(sizeof(poly));
      po3->coef = (po1->coef) * (po2->coef);
      po3->exp = (po1->exp) + (po2->exp);
      po3->next = head3;
      head3 = po3;
      po2 = po2->next;
    }
    po1 = po1->next;
  }
  while (po3) {
    printf("%+d(x^%d)", po3->coef, po3->exp);
    po3 = po3->next;
  }
  printf("\n");

}

 }

Answer 1

First you need a more organized way to add terms to the polynomials. It isn't sufficient to just add new coefficients to the end of the list. You need to search for the correct position in the list and add the polynomial there.

// Adds coef * x ^ exp to poly.
void poly_add (poly ** add2me, int coef, int exp)
{
    poly ** p;

    // printf ("poly_add %d %d\n", coef, exp);

    // Advance p to the first node such that 
    //   *p is either the correct term or the subsequent term.
    for (p = add2me; *p != NULL && (*p)->exp > exp; p = &(*p)->next);

    // If *p is too small a coefficient / NULL,
    //   then it's pointing to the next term and you need to make a new node
    if (*p == NULL || (*p)->exp < exp)
    {
        poly * new_poly = malloc(sizeof(poly));
        new_poly->coef = coef;
        new_poly->exp = exp;
        new_poly->next = *p;
        *p = new_poly;
    }
    // Else *p is the correct exponent, in which case we add...
    else
    {
        (*p)->coef += coef;
    }
}

Then it's just a small modification to your multiplication loop to get things working.

printf("Multiplying********\n");
po1 = head;
po2 = head2;
po3 = NULL;

while(po1||po2){
    po2 = head2;
    while(po1&&po2) {
        int new_coef = (po1->coef)*(po2->coef);
        int new_exp = (po1->exp)+(po2->exp);
        poly_add(&po3, new_coef, new_exp);

        po2 = po2->next;
    }
    po1 = po1->next;
}

---

Addendum: free()

Each polynomial is a linked list, so you want to manually clean up the polynomials afterwards with a generic list-destruction function...

void poly_free (poly * free_me)
{
  poly * next;
  for (; free_me != NULL; free_me = next)
  {
    next = free_me->next; // Safe because free_me != NULL
    free(free_me);
  }
}

Just call that for each polynomial you make before the program terminates. Tools like valgrind will help you know if you're leaking memory.

Answer 2

Expanding on my comment...

You will have a far easier time managing your coefficients if you store them in arrays such that the array position corresponds to exponent. For example, you'd represent 3.0x2 - 2.0x + 1.0 as

double c[3] = { 1.0, -2.0, 3.0 };

Thus, a 2nd-degree polynomial requires a 3-element array, a 3rd-degree polynomial requires a 4-element array, etc.

Multiplying two polynomials then becomes a simple nested loop:

void polymul( double *x, size_t xsize, double *y, size_t ysize, double *r, size_t rsize )
{
  memset( r, 0, sizeof *r * rsize );

  for ( size_t i = 0; i < xsize; i++ )
  {
    for ( size_t j = 0; j < ysize; j++ )
    {
      r[i + j] += x[i] * y[j];
    }
  }
}

Life will also be simpler if you separate out I/O and memory management from computation. If you know how big your input polynomials are, you know how big the output polynomial needs to be:

double *x, *y;
size_t xsize, ysize;

getcoeffs( &x, &xsize );
getcoeffs( &y, &ysize );

size_t rsize = xsize + ysize - 1;
double *r = malloc( sizeof *r * rsize );

polymul( x, xsize, y, ysize, r, rsize );
...
free( r );
free( x );
free( y );

If you're committed to using the list of structs approach, then QuestionC's answer is a good one. I just think this approach is much simpler.

Answer 3

You have two options:

• Do a second pass (e.g. sort by coefficients), and merge the coefficients with the same power.
• Do multiplication like you do it on paper, calculate the sums for the columns (it can be a rolling sum). The simplest way to do this is to implement addition first.