My Math Forum [Python/JavaScript] Synthetic Division Algorithm
 User Name Remember Me? Password

 Computer Science Computer Science Forum

 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 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.
 April 15th, 2016, 02:00 PM #2 Math Team   Joined: Dec 2013 From: Colombia Posts: 7,660 Thanks: 2635 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
 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[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 )

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post DarkPassenger Algebra 1 June 22nd, 2015 12:07 AM oti5 Algebra 5 March 19th, 2012 07:40 AM Kodwo Algebra 7 August 7th, 2011 04:01 PM symmetry Algebra 3 February 18th, 2007 06:02 PM Kodwo Abstract Algebra 0 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top