Improvement of sparse polynomial multiplication

  1. Problem Description:
    The improvement of the multiplication of sparse current polynomials
  2. Problem analysis and algorithm design:
    The basic idea is to create a structure node to store the coefficient (int), index (int), and a next pointer of each item.
    After entering two linked lists A and B:
    1. When the exponents are equal, the coefficients are formed; if the added coefficients are not 0, they are stored in the linked list C;
    2. If the exponent is not equal, if the exponent of A is less than that of B, all the coefficients and exponents in the node of A are stored in the linked list C;
    3. On the contrary, the coefficients and indexes in the nodes of B are all stored in the chain table C;
    4. When the last several items of a linked list are more than one, they are also saved in linked list C.
  3. Algorithm implementation
//The improvement of the multiplication of sparse current polynomials

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

typedef struct ployNode* mul_ploy;

mul_ploy get_tail_point(mul_ploy root);
mul_ploy createList(mul_ploy root);
mul_ploy sort(mul_ploy head, mul_ploy new_poly);

/****************************************
    *The structure of storing polynomials
    *exp :  index
    *para :  coefficient
    *next :  Pointer to the next structure
*****************************************/
struct ployNode
{
    int exp;
    int para;
    mul_ploy next;
};

/****************************************
    *Return to the end of a linked list
    *root :  Linked list pointer
*****************************************/
mul_ploy get_tail_point(mul_ploy root)
{
    while (root->next != NULL)
        root = root->next;
    return root;
}

/****************************************
    *Input the index and coefficient, and put them into the chain list
    *root :  Existing list to put
*****************************************/
mul_ploy createList(mul_ploy root)
{
    int exp;
    int para;
    scanf("Please enter index: %d", &exp);
    scanf("Please enter parameters: %d", &para);
    mul_ploy new_node = (mul_ploy)malloc(sizeof(struct ployNode));
    new_node->exp = exp;
    new_node->para = para;
    new_node->next = NULL;
    mul_ploy tail = get_tail_point(root);
    tail->next = new_node;
}

/****************************************
    *Sort from large to small
    *head :  First element node of linked list
    *new_ploy :  Element node to insert
*****************************************/
mul_ploy sort(mul_ploy head, mul_ploy new_poly)
{
    if (head->exp < new_poly->exp)
    {
        new_poly->next = head;
        head = new_poly;
    }
    else
    {
        mul_ploy temp = head;
        mul_ploy temp_pre = head;
        while (temp != NULL)
        {
            if (temp->exp < new_poly->exp)
            {
                temp_pre->next = new_poly;
                new_poly->next = temp;
                break;
            }
            else
            {
                if (temp->exp == new_poly->exp)
                {
                    temp->para += new_poly->para;
                    free(new_poly);
                    break;
                }
                else
                {
                    temp_pre = temp;
                    temp = temp->next;
                }

            }

        }
        if (temp == NULL)
        {
            temp_pre->next = new_poly;
        }
    }
    return head;
}

/****************************************
    *Polynomial multiplication
    *first :  First polynomial
    *second :  Another polynomial
*****************************************/
mul_ploy multiply(mul_ploy first, mul_ploy second)
{
    if (first == NULL || second == NULL)
        return NULL;

    mul_ploy head = (mul_ploy)malloc(sizeof(struct ployNode));
    int count = 0;

    mul_ploy first_head = first;
    mul_ploy second_head = second;
    while (first)
    {
        second = second_head;
        while (second)
        {
            mul_ploy new_poly = (mul_ploy)malloc(sizeof(struct ployNode));

            new_poly->exp = first->exp + second->exp;
            new_poly->para = first->para * second->para;
            if (new_poly->para == 0)
                free(new_poly);
            else
            {
                if (count)
                {
                    head = sort(head, new_poly);
                }
                else
                {
                    head->exp = new_poly->exp;
                    head->para = new_poly->para;
                    free(new_poly);
                    count++;
                }
            }
        }
    }
    return head;
}

reference resources: Unary sparse polynomials (addition and subtraction method)

Tags: less

Posted on Tue, 05 May 2020 02:09:13 -0700 by raymedia