 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 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; 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,690 Thanks: 2669 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] === "^") { 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] === "^") { returnArray[Number(parser[i].slice(1))] = Number(parser[i-1]); } if (i === parser.length - 1 && parser[i] !== "^") { returnArray = 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 === "+") { 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; 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 ) Tags algorithm, division, python or javascript, synthetic Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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      