
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
April 15th, 2016, 01:30 PM  #1 
Newbie 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 nonmonic 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 nonmonic), # 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. 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(" "); } 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. 
April 15th, 2016, 02:00 PM  #2 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,622 Thanks: 2611 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 NewtonRaphson. Alternatively, on the assumption that all your coefficients are integers, you might be able two generalise the concepts of the Rational Root Tjeorem. 
April 16th, 2016, 03:45 PM  #3 
Newbie 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[i1]); } 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")))); 

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 06:02 PM 
Synthetic Division Problem  Kodwo  Abstract Algebra  0  December 31st, 1969 04:00 PM 