Thread: Polynomial Long Division

  1. #1
    Registered User
    Join Date
    Aug 2007
    Posts
    7

    Polynomial Long Division

    Hello, I'm trying to write a program for doing long division with polynomials, and I am having a very difficult time trying to get the program to (properly) determine the coefficients of the quotient's terms (but it is determining the degree of the quotient properly, a plus). Using this program, an example would be a polynomial to be divided of 5x^5+9x^3+-18x (would be put in as (and manipulated) as 5x^5+0x^4+9x^3+0x^1-18x+0), with a divisor polynomial of x^3+3x (NOTE: the caret (^) is to raise to the power). The quotient should be 5x^2-6 (displayed in the program as 5x^2+0x-6), but is instead displaying 0x^2+00x+0.

    Here is the problem code:
    Code:
    	{//This section is (supposed to) do the actual math.
    
    	for (; wsh_counter<=wsh_count_to; wsh_counter++, dr_counter++){
    
    		ws[wsh_counter][wsv_counter]=dd[wsh_counter];
    		if (dr[dr_counter]!=0){
    		qt[wsv_counter]=ws[wsh_counter][wsv_counter]/dr[dr_counter];
    		}
    		else if (dr[dr_counter]==0){
    			qt[wsv_counter]=0;
    		}
    		ws[wsh_counter][wsv_counter]=qt[wsv_counter]*dr[dr_counter];
    
    		if (wsh_counter==wsh_count_to&&wsh_count_to<=(dd_degree+1)){
    			dr_counter=0;
    			wsh_count_from++;
    			wsh_counter=wsh_count_from;
    			wsv_counter++;
    			wsh_count_to++;
    	}
    
    	}//This is the end of the section meant to do the math.
    However, if need be, here is the whole program's code:
    Code:
    #include <iostream>
    
    int dd_degree, dr_degree, qt_degree; //Degree of divided, divider, and quotient.
    int counter, counter_a, counter_b, dd_counter, dr_counter, qt_counter; //Various counters that might be needed.
    
    using namespace std;
    
    int main(){
    
    
    	cout<<"Welcome to the easy-to-use polynomial long-division program.";
    	cin.get();
    	cout<<"\nTo begin, please enter the degree of the polynomial to divide: ";
    	cin>>dd_degree;
    	float dd[dd_degree+1]; //The array for the divided polynomial's coefficients.
    	counter=0;
    
    	//This section will take the input for the polynomial to be divided's coefficients.
    	for (;counter<=dd_degree;counter++){
    		if (counter<dd_degree-1){
    			cout<<"\nPlease enter the coefficient of the x^"<<dd_degree-counter<<" term: ";
    		}
    		if (counter==dd_degree-1){
    			cout<<"\nPlease enter the coefficient of the x term: ";
    		}
    		if (counter==dd_degree){
    			cout<<"\nPlease enter the constant: ";
    		}
    		cin>>dd[counter];
    	}
    
    	cout<<"\nTo continue, please enter the degree of the polynomial to divide by: ";
    	cin>>dr_degree;
    	float dr[dr_degree+1]; //The array for the divsor's coefficients.
    	counter=0;
    
    	//Same as previous for loop, but for the divisor's coefficients.
    	for (;counter<=dr_degree;counter++){
    		if (counter<dr_degree-1){
    			cout<<"\nPlease enter the coefficient of the x^"<<dr_degree-counter<<" term: ";
    		}
    		if (counter==dr_degree-1){
    			cout<<"\nPlease enter the coefficient of the x term: ";
    		}
    		if (counter==dr_degree){
    			cout<<"\nPlease enter the constant: ";
    		}
    		cin>>dr[counter];
    	}
    
    	qt_degree=dd_degree-dr_degree; //The degree of the quotient.
    	float qt[qt_degree+1]; //Array for the coefficients of the quotient.
    	int wsh; //Work Space Horizontal.
    	int wsv; //Work Space Vertical.
    	//The vertical and horizontal size of the Work Space Array are equal to the divided's degree.
    	wsh=dd_degree+1;
    	wsv=wsh;
    	float ws[wsh][wsv]; //This is the array for the Work Space coefficients.
    	int wsh_counter, wsv_counter, wsh_count_to, wsv_count_to, wsh_count_from; //More counters and counter controllers, yay!
    	wsh_counter=0; //This is to count the horizontal position.
    	wsv_counter=0; //This is to count the vertical position.
    	wsh_count_to=dr_degree; //This is the limit on the loop for the horizontal counter.
    	wsv_count_to=dd_degree; //This is the limit on the loop for the vertical counter.
    	dr_counter=0;
    	wsh_count_from=0;
    
    	{//This section is (supposed to) do the actual math.
    
    	for (; wsh_counter<=wsh_count_to; wsh_counter++, dr_counter++){
    
    		ws[wsh_counter][wsv_counter]=dd[wsh_counter];
    		if (dr[dr_counter]!=0){
    		qt[wsv_counter]=ws[wsh_counter][wsv_counter]/dr[dr_counter];
    		}
    		else if (dr[dr_counter]==0){
    			qt[wsv_counter]=0;
    		}
    		ws[wsh_counter][wsv_counter]=qt[wsv_counter]*dr[dr_counter];
    
    		if (wsh_counter==wsh_count_to&&wsh_count_to<=(dd_degree+1)){
    			dr_counter=0;
    			wsh_count_from++;
    			wsh_counter=wsh_count_from;
    			wsv_counter++;
    			wsh_count_to++;
    	}
    
    	}//This is the end of the section meant to do the math.
    
    	//This section is to display the quotient.
    	counter_a=0;
    	cout<<"\nThe quotient is: \n";
    	for (;counter_a<=qt_degree;counter_a++){
    		if (counter_a<qt_degree-1){
    			cout<<qt[counter_a]<<"x^"<<(qt_degree-counter_a)<<"+";
    		}
    		if (counter_a==qt_degree-1){
    			cout<<qt[counter_a]<<"x+";
    		}
    		else {
    		cout<<qt[counter_a];
    		}
    	}
    	//This is the end of the section to display the quotient.
    
    	//This section is to ask the user to either restart or exit the the program.
    	cin.get();
    	cout<<"\n\nWould you like to restart the program?\n1. Yes\n2. No\n\nChoice: ";
    	int rerun;
    	cin>>rerun;
    	if (rerun==1){
    		cout<<"\nRestarting... please press enter.";
    		cin.get();
    		cin.get();
    		cout<<"\n\n\n";
    		main();
    	}
    	else{
    }
    }
    }
    The problem, as mentioned, lies in the first code section; the problem being how would I write a system that replicates the human process of long division?
    Last edited by NESevolved; 09-02-2007 at 04:19 PM. Reason: Forgot Something

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    First of all, without examining the code too closely (although I notice that you call main() recursively, which I believe is forbidden in standard C++), do you actually have to do this yourself? There are a number of symbolic algebra packages that will do this, and a lot more, for you.

    http://en.wikipedia.org/wiki/Computer_algebra_system

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dev-cpp - compiler options
    By tretton in forum C Programming
    Replies: 7
    Last Post: 01-06-2006, 06:20 PM
  2. Sorting Algorithms with Time
    By silicon in forum C++ Programming
    Replies: 3
    Last Post: 05-03-2005, 11:27 AM
  3. BigInt Linked List Long Division
    By abyssknight in forum C Programming
    Replies: 5
    Last Post: 04-01-2004, 07:02 PM
  4. Polynomial
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 04-17-2002, 05:00 PM
  5. Polynomial Problem
    By softcoder76 in forum C++ Programming
    Replies: 5
    Last Post: 03-01-2002, 02:07 PM