CODEWITHSUNDEEP
cpolynomials
Jedore
Jedore

Reputation: 363

multiplication of polynomial in C using list

I'm using lists to implement the multiplication of polynomials. My code is:

typedef struct node *node_ptr;
typedef struct node
{
    unsigned int power;
    int coeff;
    node_ptr next;
}POLY;
typedef node_ptr polynomial; 

void mult_polynomial(polynomial poly1, polynomial poly2, polynomial poly_mult)
{
    assert(!is_null(poly1) && !is_null(poly2) && is_null(poly_mult));
    node_ptr p1 = poly1->next;
    node_ptr p2;
    node_ptr p3;
    node_ptr tmp, cell;

    while (p1) {
        p2 = poly2->next;
        while (p2) {
            p3 = poly_mult;
            cell = p3->next;
            tmp = (node_ptr)malloc(sizeof(struct node));
            tmp->power = p1->power + p2->power;
            tmp->coeff = p1->coeff * p2->coeff;
            tmp->next = NULL;
            if (!cell)
                p3->next = tmp;
            else { 
                if (cell->power == tmp->power) {
                    cell->coeff += tmp->coeff;
                    free(tmp);   
                } else if (cell->power < tmp->power) {
                    p3->next = tmp;
                    tmp->next = cell;
                } else if (cell->power > tmp->power) {
                    while (cell->power > tmp->power) {
                        if(!cell->next || cell->next->power < tmp->power) {
                            cell->next = tmp;
                            break; 
                        } else if (cell->next->power == tmp->power) {
                            cell->next->coeff += tmp->coeff;
                            break;
                        }
                        p3 = cell;
                        cell = p3->next;
                    }
                }
            }
            p2 = p2->next;
        }
        p1 = p1->next;
    }
}

But it seems too redundant; how to simplify it?

Upvotes: 0

Views: 711

Answers (1)

Jonathan Leffler
Jonathan Leffler

Reputation: 753525

Here's my take on a solution. It is basically a complete rewrite — though the structure used is only renamed but structurally equivalent to what you had.

The function add_term() turns out to be crucial — it is a variant of part of what you had in mult_polynomial(), but it also lends itself to use in add_polynomial() and sub_polynomial() — one factor which indicates that it is a useful abstraction. Note that mult_polynomial() itself is very simple and compact as a result — and neither add_polynomial() nor sub_polynomial() is any more complex.

I'm not completely happy with the code in add_term() (there are too many special cases), but I believe it does its job reasonably well. You can end up with a polynomial with many terms that have 0 as the coefficient; the code does not remove such terms, though it could (should) be upgraded to do so. The printing code accordingly has to skip such terms — and has a special case to deal with all terms zero (it prints 0, of course).

Also, the design of mult_polynomial() in the question is inadequate. If you have void mult_polynomial(polynomial *p1, polynomial *p2, polynomial *p3), you can't get the new data in p3 out of the function. The options are to use polynomial **p3 or to return the new polynomial — this code returns the new value.

And, as already mentioned in the comments, it is generally best not to used typedef for data pointers (function pointers are a different matter). You can find out more at Is it a good idea to typedef pointers. I ended up with one structure for polynomials, which is the same as the structure for a term in a polynomial. (The test code uses a pair of structures, a term and a termlist, to describe polynomials for testing purposes. They make life easier. There's a modest amount of test code. The add_polynomial() and sub_polynomial() functions were completed inside 10 minutes, including fixing up the printing for 0 polynomials, which is a testament to the usefulness of the add_term() function.

The print_polynomial() function is important and useful. It also has to deal with some fiddly special cases (negative coefficients, first coefficient negative, zero coefficients, power of one, and power of zero). It should arguably be generalized to allow the variable name to be specified; it is hard-coded as x. There might be some simpler functions trying to escape — one possibility is a print_term() function that could be used elsewhere as well as being called in print_polynomial(). There'd be tricky communication to handle the fiddly special cases, of course.

An FYI: I define all functions (other than main()) as static unless there's a second source file that references them and a header file that declares them. Clearly, some of these functions would become publicly accessible if the code was to be reused and would then be made extern (non-static) and declared in a header. The details of the type would not be in the header; the typedef struct polynomial polynomial; would be there, but that's all that would be needed. The definition would be hidden in the implementation file. This would be an opaque type. Some functions such as add_term() and make_term() would remain as static functions.

The code uses C99 designated initializers and compound literals. It could be written using C89/C90 code, but it would be harder and/or messier. Not necessarily very much harder, but…

Without further ado, here's the code (it's quite long):

/* SO 4313-7847 */
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include "emalloc.h"

typedef struct polynomial polynomial;

struct polynomial
{
    unsigned int power;
    int          coeff;
    polynomial  *next;
};

static void print_polynomial(const char *tag, const polynomial *poly);

static polynomial *make_term(unsigned int power, int coeff, polynomial *next)
{
    polynomial *new_term = MALLOC(sizeof(*new_term));
    new_term->power = power;
    new_term->coeff = coeff;
    new_term->next  = next;
    return new_term;
}

static polynomial *add_term(polynomial *poly, unsigned int power, int coeff)
{
    if (coeff == 0)
        return poly;
    if (poly == NULL)
        return make_term(power, coeff, NULL);

    /* Find where this term goes */
    polynomial *term = poly;
    polynomial *prev = NULL;
    while (term != NULL && term->power > power)
    {
        prev = term;
        term = term->next;
    }

    if (term != NULL && term->power == power)
    {
        term->coeff += coeff;
        /* Eliminate zero terms here */
    }
    else
    {
        assert(term == NULL || term->power < power);
        polynomial *new_term = make_term(power, coeff, term);
        if (prev == NULL)
            poly = new_term;
        else
            prev->next = new_term;
    }
    return poly;
}

static polynomial *mult_polynomial(polynomial *poly1, polynomial *poly2)
{
    assert(poly1 != NULL && poly2 != NULL);
    polynomial *result = NULL;

    for (polynomial *p1 = poly1; p1 != NULL; p1 = p1->next)
    {
        for (polynomial *p2 = poly2; p2 != NULL; p2 = p2->next)
            result = add_term(result, p1->power + p2->power, p1->coeff * p2->coeff);
    }
    return result;
}

static polynomial *add_polynomial(polynomial *poly1, polynomial *poly2)
{
    assert(poly1 != NULL && poly2 != NULL);
    polynomial *result = NULL;

    for (polynomial *p1 = poly1; p1 != NULL; p1 = p1->next)
        result = add_term(result, p1->power, p1->coeff);
    for (polynomial *p2 = poly2; p2 != NULL; p2 = p2->next)
        result = add_term(result, p2->power, p2->coeff);
    return result;
}

static polynomial *sub_polynomial(polynomial *poly1, polynomial *poly2)
{
    assert(poly1 != NULL && poly2 != NULL);
    polynomial *result = NULL;

    for (polynomial *p1 = poly1; p1 != NULL; p1 = p1->next)
        result = add_term(result, p1->power, p1->coeff);
    for (polynomial *p2 = poly2; p2 != NULL; p2 = p2->next)
        result = add_term(result, p2->power, -p2->coeff);
    return result;
}

static void print_polynomial(const char *tag, const polynomial *poly)
{
    int printed = 0;
    printf("%s:", tag);
    char sign = ' ';
    while (poly != NULL)
    {
        int coeff = poly->coeff;
        if (coeff != 0)
        {
            if (sign != ' ' && coeff < 0)
            {
                sign = '-';
                coeff = -coeff;
            }
            if (poly->power == 0)
                printf(" %c %d", sign, coeff);
            else if (poly->power == 1)
                printf(" %c %dx", sign, coeff);
            else
                printf(" %c %dx^%u", sign, coeff, poly->power);
            printed++;
        }
        poly = poly->next;
        sign = '+';
    }
    if (printed == 0)
        printf("   0");
    putchar('\n');
    fflush(stdout);
}

static void free_polynomial(polynomial *poly)
{
    while (poly != NULL)
    {
        polynomial *next = poly->next;
        free(poly);
        poly = next;
    }
}

typedef struct term
{
    unsigned int power;
    int coeff;
} term;

typedef struct termlist
{
    int n_terms;
    term *terms;
} termlist;

static polynomial *make_polynomial(termlist *terms)
{
    polynomial *poly = 0;
    for (int i = 0; i < terms->n_terms; i++)
    {
        printf("Term: %dx^%u\n", terms->terms[i].coeff, terms->terms[i].power);
        fflush(stdout);
        poly = add_term(poly, terms->terms[i].power, terms->terms[i].coeff);
    }
    return poly;
}

int main(void)
{
    termlist p1[] =
    {
        { .n_terms = 4, .terms = (term[]){ { 3, 2 }, { 2,  1 }, { 1,  4 }, { 0, -9 } } },
        { .n_terms = 3, .terms = (term[]){ { 2, 3 }, { 1, -4 }, { 0,  8 } } },
        { .n_terms = 3, .terms = (term[]){ { 1, 5 }, { 0,  3 }, { 2, -4 } } },
        { .n_terms = 2, .terms = (term[]){ { 4, 5 }, { 0, -5 } } },
        { .n_terms = 4, .terms = (term[]){ { 3, 2 }, { 2,  1 }, { 1,  4 }, { 2, -9 } } },
    };
    enum { NUM_POLYS = sizeof(p1) / sizeof(p1[0]) };
    polynomial *poly[NUM_POLYS] = { 0 };

    for (int i = 0; i < NUM_POLYS; i++)
    {
        poly[i] = make_polynomial(&p1[i]);
        print_polynomial("Building", poly[i]);
    }

    printf("Checking:\n");
    for (int i = 0; i < NUM_POLYS; i++)
        print_polynomial("Next", poly[i]);
    putchar('\n');

    printf("Multiplying polynomials:\n");
    for (int i = 0; i < NUM_POLYS; i++)
    {
        for (int j = 0; j < NUM_POLYS; j++)
        {
            print_polynomial("Term 1", poly[i]);
            print_polynomial("Term 2", poly[j]);
            polynomial *prod = mult_polynomial(poly[i], poly[j]);
            print_polynomial("Product", prod);
            free_polynomial(prod);
        }
        putchar('\n');
    }

    printf("Adding polynomials:\n");
    for (int i = 0; i < NUM_POLYS; i++)
    {
        for (int j = 0; j < NUM_POLYS; j++)
        {
            print_polynomial("Term 1", poly[i]);
            print_polynomial("Term 2", poly[j]);
            polynomial *sum = add_polynomial(poly[i], poly[j]);
            print_polynomial("Sum", sum);
            free_polynomial(sum);
        }
        putchar('\n');
    }

    printf("Subtracting polynomials:\n");
    for (int i = 0; i < NUM_POLYS; i++)
    {
        for (int j = 0; j < NUM_POLYS; j++)
        {
            print_polynomial("Term 1", poly[i]);
            print_polynomial("Term 2", poly[j]);
            polynomial *diff = sub_polynomial(poly[i], poly[j]);
            print_polynomial("Difference", diff);
            free_polynomial(diff);
        }
        putchar('\n');
    }

    for (int i = 0; i < NUM_POLYS; i++)
        free_polynomial(poly[i]);

    return 0;
}

And the output, broken into three sections so you can see the start of the multiplication, addition and subtraction sections of the tests:

Term: 2x^3
Term: 1x^2
Term: 4x^1
Term: -9x^0
Building:   2x^3 + 1x^2 + 4x - 9
Term: 3x^2
Term: -4x^1
Term: 8x^0
Building:   3x^2 - 4x + 8
Term: 5x^1
Term: 3x^0
Term: -4x^2
Building:   -4x^2 + 5x + 3
Term: 5x^4
Term: -5x^0
Building:   5x^4 - 5
Term: 2x^3
Term: 1x^2
Term: 4x^1
Term: -9x^2
Building:   2x^3 - 8x^2 + 4x
Checking:
Next:   2x^3 + 1x^2 + 4x - 9
Next:   3x^2 - 4x + 8
Next:   -4x^2 + 5x + 3
Next:   5x^4 - 5
Next:   2x^3 - 8x^2 + 4x

Multiplication:

Multiplying polynomials:
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   2x^3 + 1x^2 + 4x - 9
Product:   4x^6 + 4x^5 + 17x^4 - 28x^3 - 2x^2 - 72x + 81
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   3x^2 - 4x + 8
Product:   6x^5 - 5x^4 + 24x^3 - 35x^2 + 68x - 72
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   -4x^2 + 5x + 3
Product:   -8x^5 + 6x^4 - 5x^3 + 59x^2 - 33x - 27
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   5x^4 - 5
Product:   10x^7 + 5x^6 + 20x^5 - 45x^4 - 10x^3 - 5x^2 - 20x + 45
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   2x^3 - 8x^2 + 4x
Product:   4x^6 - 14x^5 + 8x^4 - 46x^3 + 88x^2 - 36x

Term 1:   3x^2 - 4x + 8
Term 2:   2x^3 + 1x^2 + 4x - 9
Product:   6x^5 - 5x^4 + 24x^3 - 35x^2 + 68x - 72
Term 1:   3x^2 - 4x + 8
Term 2:   3x^2 - 4x + 8
Product:   9x^4 - 24x^3 + 64x^2 - 64x + 64
Term 1:   3x^2 - 4x + 8
Term 2:   -4x^2 + 5x + 3
Product:   -12x^4 + 31x^3 - 43x^2 + 28x + 24
Term 1:   3x^2 - 4x + 8
Term 2:   5x^4 - 5
Product:   15x^6 - 20x^5 + 40x^4 - 15x^2 + 20x - 40
Term 1:   3x^2 - 4x + 8
Term 2:   2x^3 - 8x^2 + 4x
Product:   6x^5 - 32x^4 + 60x^3 - 80x^2 + 32x

Term 1:   -4x^2 + 5x + 3
Term 2:   2x^3 + 1x^2 + 4x - 9
Product:   -8x^5 + 6x^4 - 5x^3 + 59x^2 - 33x - 27
Term 1:   -4x^2 + 5x + 3
Term 2:   3x^2 - 4x + 8
Product:   -12x^4 + 31x^3 - 43x^2 + 28x + 24
Term 1:   -4x^2 + 5x + 3
Term 2:   -4x^2 + 5x + 3
Product:   16x^4 - 40x^3 + 1x^2 + 30x + 9
Term 1:   -4x^2 + 5x + 3
Term 2:   5x^4 - 5
Product:   -20x^6 + 25x^5 + 15x^4 + 20x^2 - 25x - 15
Term 1:   -4x^2 + 5x + 3
Term 2:   2x^3 - 8x^2 + 4x
Product:   -8x^5 + 42x^4 - 50x^3 - 4x^2 + 12x

Term 1:   5x^4 - 5
Term 2:   2x^3 + 1x^2 + 4x - 9
Product:   10x^7 + 5x^6 + 20x^5 - 45x^4 - 10x^3 - 5x^2 - 20x + 45
Term 1:   5x^4 - 5
Term 2:   3x^2 - 4x + 8
Product:   15x^6 - 20x^5 + 40x^4 - 15x^2 + 20x - 40
Term 1:   5x^4 - 5
Term 2:   -4x^2 + 5x + 3
Product:   -20x^6 + 25x^5 + 15x^4 + 20x^2 - 25x - 15
Term 1:   5x^4 - 5
Term 2:   5x^4 - 5
Product:   25x^8 - 50x^4 + 25
Term 1:   5x^4 - 5
Term 2:   2x^3 - 8x^2 + 4x
Product:   10x^7 - 40x^6 + 20x^5 - 10x^3 + 40x^2 - 20x

Term 1:   2x^3 - 8x^2 + 4x
Term 2:   2x^3 + 1x^2 + 4x - 9
Product:   4x^6 - 14x^5 + 8x^4 - 46x^3 + 88x^2 - 36x
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   3x^2 - 4x + 8
Product:   6x^5 - 32x^4 + 60x^3 - 80x^2 + 32x
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   -4x^2 + 5x + 3
Product:   -8x^5 + 42x^4 - 50x^3 - 4x^2 + 12x
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   5x^4 - 5
Product:   10x^7 - 40x^6 + 20x^5 - 10x^3 + 40x^2 - 20x
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   2x^3 - 8x^2 + 4x
Product:   4x^6 - 32x^5 + 80x^4 - 64x^3 + 16x^2

Addition:

Adding polynomials:
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   2x^3 + 1x^2 + 4x - 9
Sum:   4x^3 + 2x^2 + 8x - 18
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   3x^2 - 4x + 8
Sum:   2x^3 + 4x^2 - 1
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   -4x^2 + 5x + 3
Sum:   2x^3 - 3x^2 + 9x - 6
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   5x^4 - 5
Sum:   5x^4 + 2x^3 + 1x^2 + 4x - 14
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   2x^3 - 8x^2 + 4x
Sum:   4x^3 - 7x^2 + 8x - 9

Term 1:   3x^2 - 4x + 8
Term 2:   2x^3 + 1x^2 + 4x - 9
Sum:   2x^3 + 4x^2 - 1
Term 1:   3x^2 - 4x + 8
Term 2:   3x^2 - 4x + 8
Sum:   6x^2 - 8x + 16
Term 1:   3x^2 - 4x + 8
Term 2:   -4x^2 + 5x + 3
Sum:   -1x^2 + 1x + 11
Term 1:   3x^2 - 4x + 8
Term 2:   5x^4 - 5
Sum:   5x^4 + 3x^2 - 4x + 3
Term 1:   3x^2 - 4x + 8
Term 2:   2x^3 - 8x^2 + 4x
Sum:   2x^3 - 5x^2 + 8

Term 1:   -4x^2 + 5x + 3
Term 2:   2x^3 + 1x^2 + 4x - 9
Sum:   2x^3 - 3x^2 + 9x - 6
Term 1:   -4x^2 + 5x + 3
Term 2:   3x^2 - 4x + 8
Sum:   -1x^2 + 1x + 11
Term 1:   -4x^2 + 5x + 3
Term 2:   -4x^2 + 5x + 3
Sum:   -8x^2 + 10x + 6
Term 1:   -4x^2 + 5x + 3
Term 2:   5x^4 - 5
Sum:   5x^4 - 4x^2 + 5x - 2
Term 1:   -4x^2 + 5x + 3
Term 2:   2x^3 - 8x^2 + 4x
Sum:   2x^3 - 12x^2 + 9x + 3

Term 1:   5x^4 - 5
Term 2:   2x^3 + 1x^2 + 4x - 9
Sum:   5x^4 + 2x^3 + 1x^2 + 4x - 14
Term 1:   5x^4 - 5
Term 2:   3x^2 - 4x + 8
Sum:   5x^4 + 3x^2 - 4x + 3
Term 1:   5x^4 - 5
Term 2:   -4x^2 + 5x + 3
Sum:   5x^4 - 4x^2 + 5x - 2
Term 1:   5x^4 - 5
Term 2:   5x^4 - 5
Sum:   10x^4 - 10
Term 1:   5x^4 - 5
Term 2:   2x^3 - 8x^2 + 4x
Sum:   5x^4 + 2x^3 - 8x^2 + 4x - 5

Term 1:   2x^3 - 8x^2 + 4x
Term 2:   2x^3 + 1x^2 + 4x - 9
Sum:   4x^3 - 7x^2 + 8x - 9
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   3x^2 - 4x + 8
Sum:   2x^3 - 5x^2 + 8
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   -4x^2 + 5x + 3
Sum:   2x^3 - 12x^2 + 9x + 3
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   5x^4 - 5
Sum:   5x^4 + 2x^3 - 8x^2 + 4x - 5
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   2x^3 - 8x^2 + 4x
Sum:   4x^3 - 16x^2 + 8x

Subtraction:

Subtracting polynomials:
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   2x^3 + 1x^2 + 4x - 9
Difference:   0
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   3x^2 - 4x + 8
Difference:   2x^3 - 2x^2 + 8x - 17
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   -4x^2 + 5x + 3
Difference:   2x^3 + 5x^2 - 1x - 12
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   5x^4 - 5
Difference:   -5x^4 + 2x^3 + 1x^2 + 4x - 4
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   2x^3 - 8x^2 + 4x
Difference: + 9x^2 - 9

Term 1:   3x^2 - 4x + 8
Term 2:   2x^3 + 1x^2 + 4x - 9
Difference:   -2x^3 + 2x^2 - 8x + 17
Term 1:   3x^2 - 4x + 8
Term 2:   3x^2 - 4x + 8
Difference:   0
Term 1:   3x^2 - 4x + 8
Term 2:   -4x^2 + 5x + 3
Difference:   7x^2 - 9x + 5
Term 1:   3x^2 - 4x + 8
Term 2:   5x^4 - 5
Difference:   -5x^4 + 3x^2 - 4x + 13
Term 1:   3x^2 - 4x + 8
Term 2:   2x^3 - 8x^2 + 4x
Difference:   -2x^3 + 11x^2 - 8x + 8

Term 1:   -4x^2 + 5x + 3
Term 2:   2x^3 + 1x^2 + 4x - 9
Difference:   -2x^3 - 5x^2 + 1x + 12
Term 1:   -4x^2 + 5x + 3
Term 2:   3x^2 - 4x + 8
Difference:   -7x^2 + 9x - 5
Term 1:   -4x^2 + 5x + 3
Term 2:   -4x^2 + 5x + 3
Difference:   0
Term 1:   -4x^2 + 5x + 3
Term 2:   5x^4 - 5
Difference:   -5x^4 - 4x^2 + 5x + 8
Term 1:   -4x^2 + 5x + 3
Term 2:   2x^3 - 8x^2 + 4x
Difference:   -2x^3 + 4x^2 + 1x + 3

Term 1:   5x^4 - 5
Term 2:   2x^3 + 1x^2 + 4x - 9
Difference:   5x^4 - 2x^3 - 1x^2 - 4x + 4
Term 1:   5x^4 - 5
Term 2:   3x^2 - 4x + 8
Difference:   5x^4 - 3x^2 + 4x - 13
Term 1:   5x^4 - 5
Term 2:   -4x^2 + 5x + 3
Difference:   5x^4 + 4x^2 - 5x - 8
Term 1:   5x^4 - 5
Term 2:   5x^4 - 5
Difference:   0
Term 1:   5x^4 - 5
Term 2:   2x^3 - 8x^2 + 4x
Difference:   5x^4 - 2x^3 + 8x^2 - 4x - 5

Term 1:   2x^3 - 8x^2 + 4x
Term 2:   2x^3 + 1x^2 + 4x - 9
Difference: - 9x^2 + 9
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   3x^2 - 4x + 8
Difference:   2x^3 - 11x^2 + 8x - 8
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   -4x^2 + 5x + 3
Difference:   2x^3 - 4x^2 - 1x - 3
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   5x^4 - 5
Difference:   -5x^4 + 2x^3 - 8x^2 + 4x + 5
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   2x^3 - 8x^2 + 4x
Difference:   0

Upvotes: 1

Related Questions