1 
  2 
  3 /**
  4 	Constructs a polynomial, simply a set of terms
  5 	@class
  6 	@constructor
  7 	@param {Term[]} terms An array of Term objects
  8 **/
  9 function Polynomial(terms) {
 10 	this.terms = terms;
 11 }
 12 /**
 13 	A static constant to help with de/serialization
 14 	@constant
 15 	@static
 16 **/
 17 Polynomial.serializeName = 'Polynomial';
 18 
 19 /**
 20 	Custom JSON representation to handle passing to web workers
 21 	@return {Object} For JSON.stringify
 22 **/
 23 Polynomial.prototype.toWebWorker = function() {
 24 	
 25 	var serializedterms = new Array(this.terms.length); 
 26 	for(var i=0;i<this.terms.length; i++) {
 27 		serializedterms[i] = this.terms[i].toWebWorker(); 
 28 	}
 29 	return {
 30 		"serializeName": Polynomial.serializeName,
 31 		"terms":serializedterms	
 32 	};
 33 };
 34 
 35 /**
 36 	Finish reconstituting a Polynomial after passing to a web worker
 37 	@static
 38 	@param {Object} that A polynomial stripped of methods
 39 **/
 40 Polynomial.fromWebWorker = function(that) {
 41 	reattachMethods(that,Polynomial);
 42 	for(var i =0; i < that.terms.length; i++) 
 43 	{
 44 		Term.fromWebWorker(that.terms[i]);
 45 	}
 46 };
 47 
 48 /**
 49 	Provides the Polynomials degree
 50 
 51 **/
 52 Polynomial.prototype.degree = function() {
 53 	var degrees = [];
 54 	for(var i=0; i < this.terms.length; i++) {
 55 		degrees.push(this.terms[i].degree());
 56 	}
 57 	return Math.max.apply(null, degrees);
 58 }
 59 
 60 /**
 61 	Evaluates the polynomial for value value
 62 	@param {double | object} value The value to be applied to the function/polynomial
 63 	@return {double | object} the result 
 64 **/
 65 Polynomial.prototype.resolve = function(value) { 
 66 	var sumofterms = 0; 
 67 	for (var i=0;i<this.terms.length;i++)
 68 	{
 69 		var termvalue = this.terms[i].resolve(value);
 70 		if(termvalue instanceof Term || termvalue instanceof Polynomial) {
 71 			if(sumofterms instanceof Term || sumofterms instanceof Polynomial) {
 72 				sumofterms = sumofterms.add(termvalue);
 73 			}else{
 74 				sumofterms = termvalue.add(sumofterms);
 75 			}
 76 		}else{
 77 			if(sumofterms instanceof Term || sumofterms instanceof Polynomial) {
 78 				sumofterms = sumofterms.add(termvalue);
 79 			}else{
 80 				sumofterms += termvalue; 
 81 			}
 82 		}
 83 	}
 84 	return sumofterms;
 85 };
 86 
 87 /**
 88 	Generates a string representation of the Polynomial
 89 	@return {string} The string representation
 90 **/
 91 Polynomial.prototype.toString = function() {
 92 	var retstring = "";
 93 	for(var i=0; i < this.terms.length; i++)
 94 	{
 95 		if(i!= this.terms.length-1)
 96 		{
 97 			retstring += this.terms[i].toString();
 98 			if(this.terms[i+1].coefficient >= 0)
 99 			{
100 				retstring += "+";
101 			}
102 		}else{
103 			retstring += this.terms[i].toString();
104 		}
105 	}
106 	return retstring;
107 };
108 
109 /**
110 	Generates an array of serialized terms 
111 	@return {String[]} The array of serialized terms
112 **/
113 Polynomial.prototype.serialize = function() {
114 	var serialterms = [];
115 	for(var i=0; i < this.terms.length; i++)
116 	{
117 		serialterms[i] = this.terms[i].serialize();
118 	}
119 	return serialterms;
120 };
121 
122 /**
123 	Adds one of several object to a polynomial
124 	@param {Term|Polynomial|number} summand A Term, or Polynomial, or number to be added
125 	@return {Polynomial} The sum
126 */
127 Polynomial.prototype.add = function(summand) {
128 	if(summand instanceof Polynomial)
129 	{
130 		var temppolynomial = new Polynomial(this.terms.concat(summand.terms));
131 		temppolynomial.simplify();
132 		temppolynomial.sort();
133 		return temppolynomial;
134 	}else if(summand instanceof Term) {
135 		var matchingpower = false;
136 		//var temppolynomial = this;
137 		var temppolynomial = new Polynomial(this.terms.slice()); 
138 		temppolynomial.terms.push(summand);
139 		temppolynomial.simplify();
140 		temppolynomial.sort();
141 		return temppolynomial;
142 	}else if(typeof summand === "number") {
143 		var temppolynomial = new Polynomial(this.terms.slice());
144 		var variable = 'x';
145 		if(this.terms !== undefined)
146 		{
147 			variable = this.terms[0].variable;
148 		}
149 		var tempterm = new Term(summand,0, variable);
150 		temppolynomial.terms.push(tempterm);
151 		temppolynomial.simplify();
152 		return temppolynomial;	
153 	}
154 
155 };
156 
157 /**
158 	Subtract one of several object to a polynomial
159 	@param {Term|Polynomial|number} subtrahend A Term, or Polynomial, or number to be added
160 	@return {Polynomial} The difference
161 */
162 Polynomial.prototype.subtract = function(subtrahend) {
163 	if(subtrahend instanceof Polynomial)
164 	{
165 		var sbt = subtrahend.terms.slice();
166 		for(var i = 0; i < sbt.length; i++) {
167 			sbt[i] = sbt[i].neg();
168 		}
169 		var temppolynomial = new Polynomial(this.terms.concat(sbt));
170 		temppolynomial.simplify();
171 		temppolynomial.sort();
172 		return temppolynomial;
173 	}else if(subtrahend instanceof Term) {
174 		var matchingpower = false;
175 		var temppolynomial = new Polynomial(this.terms.slice()); 
176 		temppolynomial.terms.push(subtrahend.neg());
177 		temppolynomial.simplify();
178 		temppolynomial.sort();
179 		return temppolynomial;
180 	}else if(typeof subtrahend === "number") {
181 		var temppolynomial = new Polynomial(this.terms.slice());
182 		var variable = 'x';
183 		if(this.terms !== undefined)
184 		{
185 			variable = this.terms[0].variable;
186 		}
187 		var tempterm = new Term(0-subtrahend,0, variable);
188 		temppolynomial.terms.push(tempterm);
189 		temppolynomial.simplify();
190 		return temppolynomial;	
191 	}
192 
193 };
194 
195 /**
196 	Multiply a polynomial by something
197 	@param {Polynomial|Term|number} multiplicand The item to be multiplied by
198 	@return {Polynomial} The product
199 **/
200 Polynomial.prototype.multiply = function(multiplicand) {
201 	var productterms = [];
202 	if(multiplicand instanceof Polynomial) {
203 		for(var i =0; i < this.terms.length;i++)
204 		{
205 			for(var j =0; j < multiplicand.terms.length;j++)
206 			{
207 				
208 				productterms.push(this.terms[i].multiply(multiplicand.terms[j]));
209 			}
210 		}
211 	}else if(multiplicand instanceof Term || typeof multiplicand === "number" ) {
212 		for(var i =0; i < this.terms.length;i++)
213 		{
214 			productterms.push(this.terms[i].multiply(multiplicand));
215 		}
216 	}
217 	var temppolynomial = new Polynomial(productterms);
218 	return temppolynomial;
219 };
220 
221 /***
222 	Division of a Polynomial by a number or term. Division by a polynomial is a much 
223 	more complicated case and so is not handled here because it isn't needed in this program.
224 	@param {Term|number} denominator The denominator
225 	@return {Polynomial} The quotient	
226 **/
227 Polynomial.prototype.divide = function(denominator) {
228 	var divisionterms = this.terms.slice();
229 	if(typeof denominator === "number" || denominator instanceof Term)
230 	{
231 		for(var i=0; i < divisionterms.length; i ++)
232 		{
233 			divisionterms[i] = divisionterms[i].divide(denominator);
234 		}
235 	}
236 	return new Polynomial(divisionterms);
237 };
238 
239 /**
240 	Produce powers of polynomials, only works with integers currently
241 	@param {Integer} exponent the power to be raised by
242 	@return {Polynomial} The resulting polynomial
243 **/
244 Polynomial.prototype.exponentiate = function(exponent) {
245 	var memoizedpowers = {};
246 	var originalterm = this;
247 	return (function exponentBySquares(value,exp) {
248 		if(exp == 0) {
249 			var singlevar;
250 			for(var k in value.terms[0].variable)
251 			{
252 				singlevar = k;
253 				break;
254 			}
255 			return new Term(1,0,singlevar);	
256 		}else if(exp == 1) {
257 			return value;
258 		}else if(exp%2 ==1) {
259 			var temp =originalterm.multiply(exponentBySquares(value.multiply(value),(exp-1)/2));
260 			temp.simplify();
261 			temp.sort();
262 			return temp; 
263 		}else{
264 			var temp =exponentBySquares(value.multiply(value),(exp)/2); 
265 			temp.simplify();
266 			temp.sort();
267 			return temp;
268 		}
269 	})(this,exponent);
270 };
271 
272 /**
273 	Due to the implmentation of some of the mathematical operations they generate
274 	unsimplified polynomials. This corrects that.
275 **/
276 
277 Polynomial.prototype.simplify = function() {
278 	var  powers = {}; //a dictionary of variable groupings each a dictionary of powers 
279 	var  constants = 0;
280 	for(var i =0; i < this.terms.length; i++) //for every term
281 	{
282 		var termvarsobj = this.terms[i].variable;
283 		var termvarsordering = [];
284 		for(var v in termvarsobj) { //get variables from hash
285 			termvarsordering.push(v);
286 		}
287 		termvarsordering.sort(); //get rid of zero powers
288 		
289 		var varnames = termvarsordering.join('_'); //join the sorted variables as a string
290 		if(!powers.hasOwnProperty(varnames)) //create hash bucket for variables
291 		{
292 			powers[varnames] = {}; 
293 		}
294 		var sortedpower = [];
295 		var allzeroes = true;
296 		for(var v in termvarsordering) { //for each variable
297 			var sp = this.terms[i].power[this.terms[i].variable[termvarsordering[v]]];//find the variables power
298 			sortedpower.push(sp);
299 			if(sp !== 0) { allzeroes = false;
300 			}
301 		}
302 		var p = sortedpower.join('_');
303 		var zeropower;
304 		if(allzeroes) //create has bucket for powers
305 		{
306 			constants += this.terms[i].coefficient;	
307 		}else if(!powers[varnames].hasOwnProperty(p)) { //put term in bucket
308 			powers[varnames][p] = this.terms[i];
309 		}else{ //add together if matching
310 			powers[varnames][p] = this.terms[i].add(powers[varnames][p]);
311 		}
312 	}
313 	this.terms = [];
314 	if(constants !== 0) {
315 		this.terms.push(new Term(constants,0,'x'));
316 	}
317 	for(var variable in powers) 
318 	{
319 		for(var power in powers[variable]) 
320 		{
321 			if(powers[variable][power].coefficient !== 0) {
322 				this.terms.push(powers[variable][power]);
323 			}
324 		}
325 	}
326 };
327 /**
328 	Due to the implmentation of the mathematical operations terms are  not in 
329 	any sorted order. This sorts them.
330 **/
331 Polynomial.prototype.sort = function() {
332 	var addfn = function(a,b) {return a+b;};
333 	this.terms.sort(function(a,b) {
334 		var left = parseFloat(a.power.reduce(addfn,0));
335 		var right = parseFloat(b.power.reduce(addfn,0))
336 		if(left > right)
337 			return -1;
338 		if(left < right)
339 			return 1;
340 		return 0;	
341 	});
342 };
343 
344 /**
345 	Generate orthogonal polynomials to assist least square methods
346 	@param {Number[]} points The x values of data to be interpolated
347 	@param {Integer} power The highest power of orthogonal polynomial desired
348 	@return {Polynomial[]} The orthogonal functions
349 **/
350 Polynomial.prototype.orthogonalPolynomials = function(points, power) {
351 	if((typeof points[0]) != "number")
352 	{
353 		throw new Error("Array of numbers expected.");
354 	}
355 
356 	if(power < 1) 
357 	{
358 		throw new Error("Power is expected to be");
359 	}
360 	var q = [new Polynomial([new Term(1,0,'x')])]; //q is the name of the basis function set
361 	var xvals = points.slice();
362 	/*for(var i = 0; i < points.length; i++) {
363 		xvals.push(points[i].x);
364 	}*/
365 
366 	function innerProduct(fofx, gofx, xvalues) {
367 		var fgofx = fofx.multiply(gofx);
368 		var result = 0;
369 		for(var i = 0; i < xvalues.length; i++) {
370 			result += fgofx.resolve(xvalues[i]); 
371 		}
372 		return result;
373 	}
374 	var alphazero = innerProduct((new Term(1,1,'x')).multiply(q[0]),q[0],xvals)/innerProduct(q[0],q[0],xvals); 
375 	q[1] = (new Term(1,1,'x')).subtract(alphazero);
376 	for(var i=2; i <= power; i++) {
377 		var n = i-1;
378 		var alphan = innerProduct((new Term(1,1,'x')).multiply(q[n]),q[n],xvals)/innerProduct(q[n],q[n],xvals);
379 		var betan = innerProduct((new Term(1,1,'x')).multiply(q[n]),q[n-1],xvals)/innerProduct(q[n-1],q[n-1],xvals);
380 		q[i] = (new Term(1,1,'x')).multiply(q[n]).subtract(q[n].multiply(alphan)).subtract(q[n-1].multiply(betan));
381 	}
382 	for(var i=0; i < q.length; i++)  {
383 		q[i].simplify();
384 		q[i].sort();
385 	}
386 	return q;
387 };
388 
389 /**
390 	Generate a function of least squares for given data points and given basis functions
391 	@param {Point[]} points A sorted array of points
392 	@param {Polynomial[]} bases The basis functions
393 	@return {Polynomial} The method of least square distance from all of the points
394 **/
395 Polynomial.prototype.leastSquare =  function(points, bases) {
396 	var sortedpoints = points.slice();
397 	sortedpoints.sort(function(a,b) {
398 		if(a.x < b.x) {
399 			return -1;
400 		}else if(a.x > b.x) {
401 			return 1;
402 		}else{
403 			return 0;
404 		}
405 
406 	});
407 	function innerProduct(fofx, gofx, xvalues) {
408 		var fgofx = fofx.multiply(gofx);
409 		var result = 0;
410 		for(var i = 0; i < xvalues.length; i++) {
411 			result += fgofx.resolve(xvalues[i]); 
412 		}
413 		return result;
414 	}
415 	var normalequations = [];
416 	var normalsums = [];
417 	var n = bases.length;
418 	for( var i =0; i < n; i++) {
419 		normalequations.push([]);
420 		for( var j = 0; j < n; j++) {
421 			var sum = innerProduct(bases[i],bases[j],points);
422 			normalequations[i][j] = sum;
423 		}
424 		normalsums.push(innerProduct(bases[i],new Term(1,1,'y'),points));
425 	}
426 	var normalmatrix = new Matrix(n,n,normalequations);
427 	var basisconstants = normalmatrix.scaledPartialPivotGaussian(Matrix.columnVector(normalsums));
428 
429 	/*console.log(normalmatrix.toString());
430 	console.log(normalsums);
431 	console.log(Matrix.prototype.columnVector(normalsums).toString());
432 	console.log(basisconstants.toString());*/
433 	var result = bases[0].multiply(basisconstants.values[0][0]);
434 	for(var i =1; i < n; i++) {
435 		result = result.add(bases[i].multiply(basisconstants.values[i][0]));
436 	}
437 	result.sort();
438 	return result;
439 };
440 
441 /**
442 	Generates a polynomial given an array of points using the Lagrange Interpolation Method
443 	@param {Point[]} points The points to be interpolated
444 	@return {Polynomial} The function interpolating the points.
445 **/
446 Polynomial.prototype.LagrangeInterpolation = function(points)
447 {
448 	var interpolated;
449 	var x = new Term(1,1,'x');
450 	for(var i=0; i <points.length; i++)
451 	{
452 		var ix = points[i].x;
453 		var li;
454 		for(var j=0; j<points.length; j++)
455 		{
456 			if(i !== j)
457 			{
458 				var pointpoly =x.subtract(points[j].x).divide(ix-points[j].x); 
459 				if(li == undefined)
460 				{
461 					li = pointpoly;
462 				}else{
463 					li = li.multiply(pointpoly);
464 				}
465 			}
466 		}
467 		//console.log(""+li);
468 		li = li.multiply(points[i].y);
469 		if(interpolated === undefined)
470 		{
471 			interpolated = li;
472 		}else{
473 			interpolated = interpolated.add(li);
474 		}
475 		li = null;
476 	}
477 	interpolated.simplify();
478 	interpolated.sort();
479 	return interpolated;
480 };
481 
482 /**
483 	Returns the coefficient of the polynomial of the first term of degree n
484 	@param {integer} n 
485 	@return {double}
486 **/
487 Polynomial.prototype.degreeCoeff = function(n) {
488 	for(var i =0; i < this.terms.length; i++) {
489 		if(this.terms[i].degree() ===  n) {
490 			return this.terms[i].coefficient;
491 		}
492 	}
493 	return 0;
494 }
495