My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Thanks Tree1Thanks
  • 1 Post By v8archie
Reply
 
LinkBack Thread Tools Display Modes
April 15th, 2016, 01:30 PM   #1
Newbie
 
tsteele31415's Avatar
 
Joined: Apr 2016
From: America

Posts: 7
Thanks: 1

[Python/JavaScript] Synthetic Division Algorithm

Hello!

I found a synthetic division algorithm for Python on Wikipedia, and I decided to translate it to my native language, JavaScript. This algorithm represents polynomials as sequences of numbers where the number at each index is the coefficient of x to the power of the total length of the sequence minus the current index. For example, $\displaystyle x^{4} - 2x^{3} + 3x + 10$ is represented as $\displaystyle [1,-2,0,3,10]$.

Here is the original Python implementation found at https://en.wikipedia.org/wiki/Synthe...implementation
Code:
def extended_synthetic_division(dividend, divisor):
    '''Fast polynomial division by using Extended Synthetic Division. Also works with non-monic polynomials.'''
    # dividend and divisor are both polynomials, which are here simply lists of coefficients. Eg: x^2 + 3x + 5 will be represented as [1, 3, 5]

    out = list(dividend) # Copy the dividend
    normalizer = divisor[0]
    for i in xrange(len(dividend)-(len(divisor)-1)):
        out[i] /= normalizer # for general polynomial division (when polynomials are non-monic),
                                 # we need to normalize by dividing the coefficient with the divisor's first coefficient
        coef = out[i]
        if coef != 0: # useless to multiply if coef is 0
            for j in xrange(1, len(divisor)): # in synthetic division, we always skip the first coefficient of the divisor,
                                              # because it is only used to normalize the dividend coefficients
                out[i + j] += -divisor[j] * coef

    # The resulting out contains both the quotient and the remainder, the remainder being the size of the divisor (the remainder
    # has necessarily the same degree as the divisor since it is what we couldn't divide from the dividend), so we compute the index
    # where this separation is, and return the quotient and remainder.
    separator = -(len(divisor)-1)
    return out[:separator], out[separator:] # return quotient, remainder.
And here is my JavaScript adaptation:
Code:
function syntheticDivision(dividend, divisor) {
var out = dividend;
var normalizer = divisor[0];
	var coef;
	for (var i = 0; i < dividend.length - (divisor.length - 1); i++) {
		out[i] /= normalizer;
		coef = out[i];
		if (coef !== 0) {
			for (var j = 1; j < divisor.length; j++) {
				out[i + j] += -divisor[j] * coef;
			}
		}
	}
	separator = out.length - (divisor.length - 1);
	return out.slice(0,separator).join(" ") + " Remainder: " + out.slice(separator).join(" ");
}
Now here are my questions:

1.) I want to use this in a program that factors polynomials. In my math class I learned how to use synthetic division to factor a polynomial, but this involves guessing each root of the polynomial. Is there any way to factor a polynomial efficiently without too much guessing?

2.) Are there any errors in either the Python or JavaScript algorithms?

Thanks for reading! Any help is greatly appreciated.
tsteele31415 is offline  
 
April 15th, 2016, 02:00 PM   #2
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 6,540
Thanks: 2146

Math Focus: Mainly analysis and algebra
For rational roots, there is the Rational Root Theorem, which allied to the Factor (oe Remainder) Theorem will give you a pretty efficient implementation, at least for small coefficients.

For irrational roots, you will likely have to approximate by algorithms such as Newton-Raphson.

Alternatively, on the assumption that all your coefficients are integers, you might be able two generalise the concepts of the Rational Root Tjeorem.
Thanks from tsteele31415
v8archie is offline  
April 16th, 2016, 03:45 PM   #3
Newbie
 
tsteele31415's Avatar
 
Joined: Apr 2016
From: America

Posts: 7
Thanks: 1

I've taken a slight detour and created two functions. One takes a polynomial in the form of a string (ex. "2x^3 + x + 5") and returns the same polynomial represented in a list. The other takes a polynomial in the form of a sequence (ex. [2,0,1,5]) and returns the same polynomial represented in a string.

These functions are a bit crude in my opinion, but they should suffice for a friendlier user interface. Here is the code as of now:
Code:
function PolyFromString(input) {
	var copy = input.replace(/\s/g, "");
	var parser = copy.split("x");
	var returnArray = [];
	for (var i = 0; i < parser.length; i++) {
		if (parser[i][0] === "^") {
			for (var j = 0; j < Number(parser[i].slice(1,parser[i].length - 1)); j++) {
				returnArray.push(0);
			}
			break;
		}
	}
	returnArray.push(0);
	for (var i = 0; i < parser.length; i++) {
		if (parser[i][parser[i].length - 1] === "+" || parser[i][parser[i].length - 1] === "-") {
			parser[i] = parser[i] + "1";
		}
	}
	for (var i = 0; i < parser.length; i++) {
		for (var j = 0; j < parser[i].length; j++) {
			if (parser[i][j] === "+") {
				parser[i] = parser[i].slice(0,j) + "+" + parser[i].slice(j);
				break;
			}
			if (parser[i][j] === "-") {
				parser[i] = parser[i].slice(0,j) + "-" + parser[i].slice(j);
				break;
			}
		}
	}
	for (var i = 0; i < parser.length; i++) {
		parser[i] = parser[i].replace("+", "_");
		parser[i] = parser[i].replace("-", "_");
		parser[i] = parser[i].split("_");
	}
	parser = [].concat.apply([], parser);
	for (var i = 0; i < parser.length; i++) {
		if (parser[i] === "") {
			parser[i] = "^1";
		}
	}
	for (var i = 0; i < parser.length; i++) {
		if (parser[i][0] === "^") {
			returnArray[Number(parser[i].slice(1))] = Number(parser[i-1]);
		}
		if (i === parser.length - 1 && parser[i][0] !== "^") {
			returnArray[0] = Number(parser[i]);
		}
	}
	for (var i = 0; i < returnArray.length; i++) {
		if (isNaN(returnArray[i]) && i === returnArray.length - 1) {
			returnArray[i] = 1;
		} else if (isNaN(returnArray[i])) {
			returnArray[i] = 0;
		}
	}
	return(returnArray.reverse());
}

function StringFromPoly(input) {
	var copy = input;
	var returnString = "";
	for (var i = 0; i < copy.length; i++) {
		if (copy[i] !== 0) {
		 returnString = returnString + "+" + (copy[i].toString() + "x^" + (copy.length - i - 1).toString());
		}
	}
	if (returnString[0] === "+") {
		returnString = returnString.slice(1);
	}
	returnString = returnString.replace(/\+\-/g, "-");
	returnString = returnString.split("-").join(" - ").split("+").join(" + ");
	returnString = returnString.replace("x^0", "").replace("^1", "");
	return returnString;
}

function synthDiv(dividend, divisor) {
	alert(dividend);
	alert(divisor);
	var out = dividend;
	var normalizer = divisor[0];
	var coef;
	for (var i = 0; i < dividend.length - (divisor.length - 1); i++) {
		out[i] /= normalizer;
		coef = out[i];
		if (coef !== 0) {
			for (var j = 1; j < divisor.length; j++) {
				out[i + j] += -divisor[j] * coef;
			}
		}
	}
	separator = out.length - (divisor.length - 1);
	if (StringFromPoly(out.slice(separator)) === "") {
		return StringFromPoly(out.slice(0,separator))
	} else {
	 return StringFromPoly(out.slice(0,separator)) + " Remainder: " + StringFromPoly(out.slice(separator));
	}
}

alert(synthDiv(PolyFromString(prompt("Enter the dividend")),PolyFromString(prompt("Enter the divisor"))));
(I apologize for the lack of comments in my code. I know they are important to helping others and myself understand the code, but I am simply too lazy to do it )
tsteele31415 is offline  
Reply

  My Math Forum > Science Forums > Computer Science

Tags
algorithm, division, python or javascript, synthetic



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Long Division and Synthetic Division DarkPassenger Algebra 1 June 22nd, 2015 12:07 AM
synthetic division oti5 Algebra 5 March 19th, 2012 07:40 AM
Synthetic Division Problem Kodwo Algebra 7 August 7th, 2011 04:01 PM
Synthetic Division symmetry Algebra 3 February 18th, 2007 07:02 PM
Synthetic Division Problem Kodwo Abstract Algebra 0 January 1st, 1970 12:00 AM





Copyright © 2017 My Math Forum. All rights reserved.