Thread: Multiplying polynomials

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    74

    Multiplying polynomials

    Having trouble with this. Adding, derivation, integration, all work fine, but multiplication doesn't.

    My polynomial is in fact an array of pointers. Maybe redundant but that's my choice. I set the max_koef to 5 so that means that the degree of the polynomial is 5 and that the array has 6 items, p^0, p^1,..., p^5.

    This is my code.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX_KOEF 5;
    
    typedef struct node
    	{
    		int exp;
    		float koef;
    		struct node *next;
    	} monomial;
    
    
    void MENU()
    {
    	printf("\n***\tPOLYNOMIAL\t***\n");
    	printf("\n 1.) Add to p");
    	printf("\n 2.) Add to q");	
    	printf("\n 3.) Printout both");
    	printf("\n 4.) Multiply");
    	printf("\n 0.) EXIT");
    	printf("\nChoose ---------> ");	
    }
    
    void Init(monomial *p[])
    {
    	int i;
    	int n = MAX_KOEF;
    	for (i=0; i<=n; i++) p[i] = NULL;
    }
    
    
    void Printout(monomial *a[], int n)
    {
    	int i, j, test;
    	
    	for (i=0; i<=n; i++)
    	{
    		if  (a[i] != NULL) 
    		{
    			if (i == 0) printf("\t%4.2f\t",a[i]->koef);
    			else 
    			{
    				for (j=0; j<i; j++)
    				{
    					if (a[j] != NULL) 
    					{
    						test = 1;
    						break;
    					}
    					else test = 0;
    				}
    				
    				if (test == 1)  printf("\t+\t\t%4.2f x^%d\t",a[i]->koef, a[i]->exp);
    				else printf("\t%4.2f x^%d\t",a[i]->koef, a[i]->exp);
    			}	
    		}
    	}
    	printf("\n");
    }
    
    
    
    
    void Insert(monomial *a[], float koef, int exp)
    {
    	monomial *new = malloc(sizeof(monomial));
    	int e = exp;
    	
    	new->koef = koef;
    	new->exp = exp;
    	new->next = NULL;
    	
    	if (a[e] == NULL) a[e] = new;
    	else	a[e]->koef += new->koef;
    	
    }
    
    
    
    void Multiply(monomial *a[], monomial *b[], monomial *c[])
    { 
    	int i, j;
    	int n = MAX_KOEF;
    	
    	for (i=0; i<=n; i++) 
    	{
    		if (a[i] != NULL)
    		{
    			for (j=0; j<=n; j++) 
    			{
    				if (b[j] != NULL)
    				{
    					Insert(c, a[i]->koef * b[j]->koef, a[i]->exp + b[j]->exp);
    				}
    			}
    		}
    	}
    	
    	Printout(c, 2*n + 1);
    	
    } 
    
    
    int main (int argc, const char * argv[]) 
    {
    	int n = MAX_KOEF;
    	int choice, exp, test;
    	float koef;
    	monom *p[n+1],*q[n+1];
    	monom *multi[2*n+1];
    	
    	Init(p); Init(q); Init(multi);
    	
    	do
    	{
    		MENU();
    		scanf("%d",&choice);
    		switch (choice)
    		{
    			case 1:
    				printf("Enter koeficcient -> ");
    				scanf("%f",&koef);
    				do 
    				{
    					printf("Enter exponent -> ");
    					scanf("%d",&exp);
    					if (exp < 0 && exp > n) test = 0;
    					else test = 1;
    				} while (test != 1);	
    				
    				Insert(p,koef,exp);
    				
    				break;
    			case 2:		
    				printf("Enter koeficcient -> ");
    				scanf("%f",&koef);
    				do 
    				{
    					printf("Enter exponent -> ");
    					scanf("%d",&exp);
    					if (exp < 0 && exp > n) test = 0;
    					else test = 1;
    				} while (test != 1);	
    				
    				Insert(q,koef,exp);
    				
    				break;
    			case 3:		
    				printf("\n::::::: polynomial p :> ");
    				Printout(p, n);
    				printf("\n::::::: polynomial q :> ");				
    				Printout(q, n);
    				break;
    			case 4:	
    				printf("\n::::::: polynomial p * q :> ");
    				Multiply(p,q,multi);
    				break;
    
    			default:
    				printf("\n WRONG CHOICE");
    		}
    	} while (choice != 0);
    	
    	
    	return 0;
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Insert appears to be one huge memory leak. (Why malloc a new node every single time, when most of the time you don't need to?)
    Also x^5 * x^5 = x^10, which doesn't fit, and I don't see you handling that.

  3. #3
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    I am using malloc every time because i want to have separate arrays (polynomials) one for p, one for q, one for ip and iq (ip = integrate p), one for p+q and dp and dq (not mentioned here). I want this so that I can later use that polynomial for some other use.

    I am aware that x^5 * x^5 = x^10, but I think I handled that with this
    Code:
    monom *p[n+1],*q[n+1];
    monom *multi[2*n+1];
    if n == 5, then arrays p and q have 5 elements, and array multi has 10 elements.

    Isn't this legal?
    Code:
    monom *multi[2*n+1];
    of course, I am freeing everything up, but I just skipped to include it here

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by budala View Post
    I am using malloc every time because i want to have separate arrays (polynomials) one for p, one for q, one for ip and iq (ip = integrate p), one for p+q and dp and dq (not mentioned here). I want this so that I can later use that polynomial for some other use.

    I am aware that x^5 * x^5 = x^10, but I think I handled that with this
    Code:
    monom *p[n+1],*q[n+1];
    monom *multi[2*n+1];
    if n == 5, then arrays p and q have 5 elements, and array multi has 10 elements.

    Isn't this legal?
    Code:
    monom *multi[2*n+1];
    of course, I am freeing everything up, but I just skipped to include it here
    Yeah, okay, so that's enough room. There's still no need to do malloc every time, because you don't want to do malloc every time. If you multiply two degree-five polynomials together, you will do 36 mallocs, keep 11 of them in your list and leak 25 into the ether never to be seen again.

    So the next question then becomes, how do you know your multiplication doesn't work if you don't ever print it?

  5. #5
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    aaaaah I see now what you mean. I redid my Insert and now it's like this
    Code:
    int e = exp;
    	
    	if (a[e] != NULL) 	a[e]->koef += koef;
    	else	
    	{
    		monomial * new = malloc(sizeof(monom));
    		
    		new->koef = koef;
    		new->exp = exp;
    		new->next = NULL;
    		
    		a[e] = novi;
    	}
    about printing, I don't follow. after everything is multiplied I call
    Code:
    Printout(c, 2*n + 1);
    from Multiply().

    after calling Multiply() though, I get a "bus error"

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Why not Printout(c, 2*n)? You don't have the +1 on any of the other calls to Printout.

  7. #7
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    oh my God I am such an idiot!!!

    thanks!

    p.s. there is something else wrong. the n in Init() should be different for arrays of different lengths.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Polynomials and ADT's
    By Emeighty in forum C++ Programming
    Replies: 20
    Last Post: 08-19-2008, 08:32 AM
  2. Multiplying Two Polynomials
    By CaptainMorgan in forum C++ Programming
    Replies: 6
    Last Post: 10-30-2006, 02:34 PM
  3. adding two polynomials
    By sahil_m in forum C Programming
    Replies: 3
    Last Post: 11-04-2005, 06:24 AM
  4. Polynomials with linked Lists
    By shaheedpak in forum C++ Programming
    Replies: 0
    Last Post: 09-26-2001, 11:10 AM
  5. Generating Polynomials using Linked Lists
    By shaheedpak in forum C++ Programming
    Replies: 0
    Last Post: 09-25-2001, 01:22 PM

Tags for this Thread