1 
  2 /**
  3 	Polynomial interpolation demo
  4 	@authors - Aaron R Elligsen
  5 	UNIVERSITY OF OREGON
  6 	MATH 351 - FALL 2012
  7 **/
  8 "use strict";
  9 /**
 10 	A pseudo-constructor which reatttaches methods to an object which has been 
 11 	passed through JSON serialization
 12 	@param {Object} serialized A 'class' object but without the attached methods
 13 **/
 14 function reattachMethods(serialized,originalclass) {
 15 	if(serialized.hasOwnProperty("__proto__")) {
 16 		serialized.__proto__ = originalclass.prototype;
 17 	}else{
 18 		for(var property in originalclass.prototype) {
 19 			serialized[property] = originalclass.prototype[property];
 20 		}
 21 		serialized.constructor = originalclass;
 22 	}
 23 }
 24 
 25 /**
 26 	Constructor for a term of a polynomial
 27 	@class
 28 	@constructor
 29 	@param {double} coefficient The coefficient of the term.
 30 	@param {double|double[]} power The power of the variable in the term.
 31 	@param {string|string[]} variable The name of the variable involved in the term
 32 	@todo: convert all power and variable code to work with objects
 33 		then implement the Term contructor to generate the correct structure using exiting code
 34 		implement isMatchingVariable
 35 		immplement isMathchingPowers
 36 		fix the resolve functions to yield partial functions
 37 **/
 38 function Term(coefficient, power, variable)
 39 {
 40 	if(variable === undefined || power === undefined || coefficient === undefined) {
 41 		throw new Error("Cofficient, power, and variable expected in parameters.");
 42 	}
 43 	this.coefficient = coefficient;
 44 	if(power instanceof Array) {
 45 		this.power = power;
 46 	}else{
 47 		this.power =[power];
 48 	}
 49 
 50 	if(variable instanceof Array)
 51 	{
 52 		var varobj = {};
 53 		for(var i =0; i < variable.length; i++) {
 54 			varobj[variable[i]] = i;
 55 		}
 56 		this.variable = varobj;
 57 	}else if(typeof variable == "string") {
 58 		this.variable ={};
 59 		this.variable[variable] = 0;
 60 	}else{
 61 		this.variable = variable;
 62 	}
 63 
 64 }
 65 
 66 /**
 67 	A static constant to help with de/serialization
 68 	@constant
 69 	@static
 70 **/
 71 Term.serializeName = 'Term';
 72 
 73 /**
 74 	Stringify the object but with additional property to help deserialization
 75 	@return {Object} object to JSON stringify 
 76 **/
 77 Term.prototype.toWebWorker = function() {
 78 	this.serializeName = Term.serializeName;
 79 	return this;
 80 };
 81 
 82 /**
 83 	Reattaches class methods to destringified object
 84 	@param {Object} that A Term stripped of methods
 85 	@static
 86 **/
 87 Term.fromWebWorker = function(that) {
 88 	reattachMethods(that,Term);	
 89 };
 90 
 91 /**
 92 	Compare two terms if they have matching variable sets
 93 	@private 
 94 	@param {Term} that The term being compared
 95 	@return {Boolean}
 96 **/
 97 Term.prototype.isMatchingVariables = function(that) {
 98 	var leftcontained = true;
 99 	var rightcontained = true;
100 	for(var v in this.variable) {
101 		if(that.variable[v] === undefined) {
102 			leftcontained = false;
103 		}
104 	}
105 
106 	for(var v in that.variable) {
107 		if(this.variable[v] === undefined) {
108 			rightcontained = false;
109 		}
110 	}	
111 	return leftcontained && rightcontained;
112 };
113 
114 /**
115 	Compare if two terms have matching variables and powers
116 	@private
117 	@param {Term} that The term being compared
118 	@return {Boolean}
119 **/
120 Term.prototype.isMatchingPowers = function(that) {
121 	var matching = true;
122 	if(this.power.length != that.power.length) {
123 		return false;
124 	}else{
125 		for(var v in this.variable) {
126 			if(this.power[this.variable[v]] != that.power[that.variable[v]]) {
127 				matching = false;
128 			}
129 		}
130 	}
131 	return matching;
132 };
133 
134 /**
135 	Returns the additive invese of the term
136 	@return {Term}  
137 **/
138 Term.prototype.neg = function() {
139 	return new Term(0-this.coefficient,this.power,this.variable);
140 };
141 
142 
143 /**
144 	Adds a term,polynomial, or constant to an existing term
145 	@param {Term|Polynomial|double} summand The summad being added to the term
146 	@return {Term|Polynomial} The result of the summation
147 
148 **/
149 Term.prototype.add = function(summand) {
150 	if(summand instanceof Term)
151 	{
152 		if(this.isMatchingVariables(summand) )
153 		{
154 			if(this.isMatchingPowers(summand) )
155 			{
156 				var sumofterms = new Term(this.coefficient + summand.coefficient,this.power,this.variable);
157 				return sumofterms;
158 				
159 			}else{
160 				
161 				return new Polynomial([this,summand]);
162 			}
163 		}else{
164 			
165 			return new Polynomial([this,summand]);
166 		}
167 	}else if(summand instanceof Polynomial) {
168 		return summand.add(this);
169 	}else if(typeof summand === "number") {
170 		for(var k in this.variable) {
171 			break;
172 		}
173 		var constant = new Term(summand,0,k);
174 		var newpoly = new Polynomial([this,constant]);
175 		return newpoly; 
176 	}
177 };
178 
179 /**
180 	Subtract a term, or constant from an existing term
181 	@param {Term|double} summand The summand being subtract from the term
182 	@return {Term|Polynomial} The result of the summation
183 **/
184 Term.prototype.subtract = function(summand) {
185 	if(summand instanceof Term)
186 	{
187 		return this.add(summand.neg());
188 	}else if(summand instanceof Polynomial) {
189 		var newpoly = summand.terms.slice();
190 		for(var i=0; i< newpoly.length; i++) {
191 			newpoly[i] = newpoly[i].neg();
192 		}
193 		var difference = new Polynomial(newpoly);
194 		return difference.add(this);
195 	}else if(typeof summand === "number") {
196 		var constant = new Term(0-summand,0,'x');
197 		return new Polynomial([this,constant]);
198 	}
199 };
200 
201 /**
202 	Multiply a term, Polynomial, or constant to an existing term
203 	@param {Term|Polynomial|double} multiplicand The multiplicand in the product
204 	@return {Term|Polynomial} The product
205 **/
206 Term.prototype.multiply = function(multiplicand) {
207 	var newcoef;
208 	var newpowers = [];
209 	var newvars = {};
210 	if(multiplicand instanceof Term)
211 	{
212 		newcoef = this.coefficient*multiplicand.coefficient;
213 		var varcount = 0;
214 		for(var v in this.variable) {
215 			//if(newvars[v] == undefined) {
216 				newvars[v] = varcount;
217 				newpowers[varcount] = this.power[this.variable[v]];
218 				varcount++;
219 			//}
220 		}
221 		for(var v in multiplicand.variable) {
222 			if(newvars[v] === undefined) {
223 				newvars[v] = varcount;
224 				newpowers[varcount] = multiplicand.power[multiplicand.variable[v]];
225 				varcount++;
226 			}else{
227 				newpowers[newvars[v]] += multiplicand.power[multiplicand.variable[v]];
228 			}
229 		}
230 				
231 		
232 	}else if(multiplicand instanceof Polynomial) {
233 		return multiplicand.multiply(this);
234 	}else if(typeof multiplicand === "number") {
235 		
236 			newcoef = this.coefficient*multiplicand;
237 			newvars = this.variable;
238 			newpowers = this.power.slice();
239 	}
240 	var tempterm = new Term(newcoef,newpowers,newvars);
241 	return tempterm;
242 };
243 
244 /**
245 	Divide a term by another term or a constant
246 	@param {Term|double} denominator The denominator of the divisor 
247 	@return {Term|Polynomial} The quotient 
248 **/
249 Term.prototype.divide = function(denominator) {
250 	if(denominator instanceof Term)
251 	{
252 		var newcoef = this.coefficient/denominator.coefficient;
253 		var newpowers = [];
254 		var newvars = {};
255 		var varcount = 0;
256 		for(var v in this.variable) {
257 			//if(newvars[v] == undefined) {
258 				newvars[v] = varcount;
259 				newpowers[varcount] = this.power[this.variable[v]];
260 				varcount++;
261 			//}
262 		}
263 		for(var v in denominator.variable) {
264 			if(newvars[v] === undefined) {
265 				newvars[v] = varcount;
266 				newpowers[varcount] = 0-denominator.power[denominator.variable[v]];
267 				varcount++;
268 			}else{
269 				newpowers[newvars[v]] -= denominator.power[denominator.variable[v]];
270 			}
271 		}
272 		var tempterm = new Term(newcoef,newpowers,newvars);
273 		return tempterm;
274 	}else if(typeof denominator === "number") {
275 		
276 			var tempterm = new Term(this.coefficient/denominator,this.power,this.variable);
277 			return tempterm;
278 	}
279 };
280 
281 /**
282 	Produce powers of a Term 
283 	@param {Integer} exponent the power to be raised by
284 	@return {Term} the power of the input
285 **/
286 Term.prototype.exponentiate = function(exponent) {
287 	var newpowers = [];
288 	for(var i =0; i < this.power.length; i++ ) {
289 		newpowers[i] = this.power[i]*exponent;
290 	}
291 	return new Term(Math.pow(this.coefficient,exponent),newpowers,this.variable);
292 
293 };
294 
295 /**
296 	Generates a pretty printed version of the term.
297 	@return {String} Returns a string version of the term
298 **/
299 Term.prototype.toString = function () { 
300 	var retstring ="";
301 	if(this.coefficient === 0)
302 	{
303 		return "";
304 	}else if(this.coefficient === -1) {
305 		retstring += '-';
306 	}else if(this.coefficient !== 1) {
307 		retstring += this.coefficient;
308 	}
309 
310 	var isconstant = true;
311 	for(var i=0; i < this.power.length; i++) {
312 		if(this.power[i] !== 0) {
313 			isconstant = false;
314 		}
315 	}
316 	if(isconstant) {
317 		if(this.coefficient === 1 )
318 		{
319 			retstring += this.coefficient;
320 		} 
321 		if(this.coefficient === -1) {
322 			retstring += 1;
323 		}
324 	}
325 	var trouble; //hackery here to remove extraneous *'s from the toString
326 	for(var v in this.variable) {
327 		trouble = false;
328 		var thepower = this.power[this.variable[v]]; 
329 		if(thepower !== 0) 
330 		{
331 			if(thepower === 1)
332 			{
333 
334 				//retstring += this.variable
335 				retstring += v; 
336 			}else{
337 				retstring += v; 
338 				retstring +="^"+thepower+"*";
339 				trouble = true;
340 			}
341 		}
342 	}
343 	if(trouble) {
344 		retstring = retstring.slice(0,-1);
345 	}
346 	return retstring;
347 	
348 };
349 
350 /**
351 	Generate a formated string representing a term.
352 	@return {String} Return the term in formatted string
353 **/
354 Term.prototype.serialize = function() {
355 	var retstring =""+this.coefficient;
356 	for(var v in this.variable) {
357 		retstring += ""+v+"^"+this.power[this.variable[v]];
358 	}
359 	return retstring; 
360 };
361 
362 /**
363 	@param {double|Object} value Evaluate the term for the value
364 	@return {double|Term} The result of the function
365 **/
366 Term.prototype.resolve = function(value) {
367 	var isnomial = value instanceof Term || value instanceof Polynomial;
368 	if(this.power.length == 1 && typeof value == "number" ) {
369 		return this.coefficient * Math.pow(value,this.power);
370 	}else if(this.power.length == 1 && isnomial) {
371 		return value.exponentiate(this.power[0]).multiply(this.coefficient);
372 	}else{
373 		if(isnomial) {
374 			throw new Error("Tuple expected.");
375 		}
376 		var result;
377 		var coefficient = this.coefficient;
378 		var remainingvars = {};
379 		for(var v in this.variable) {
380 			remainingvars[v] = 0;
381 		}
382 		for(var v in value) {
383 			if(this.variable.hasOwnProperty(v))
384 			{
385 				if(typeof value[v] === "number") {
386 					coefficient *= Math.pow(value[v],this.power[this.variable[v]]);
387 				}else{
388 					if(result) {
389 
390 						result = result.multiply(value[v].exponentiate(this.power[this.variable[v]]));
391 					}else{
392 						result = value[v].exponentiate(this.power[this.variable[v]]);
393 					}
394 				}
395 			}
396 			
397 			delete remainingvars[v];
398 		}
399 		var varsleft = false;
400 		var remainingpowers = [];
401 		var rpcount = 0;
402 		for(var v in remainingvars) {
403 			varsleft = true;
404 			remainingpowers[rpcount] = this.power[this.variable[v]];
405 			remainingvars[v] = rpcount;
406 			rpcount++;
407 		}
408 		if(varsleft) {
409 			if(result) {	
410 				return result.multiply(new Term(coefficient,remainingpowers,remainingvars));
411 			}else{
412 				return new Term(coefficient,remainingpowers,remainingvars);
413 			}
414 		}else{
415 			if(result) {
416 				return result.multiply(coefficient);
417 			}else{
418 				return coefficient;
419 			}
420 		}
421 	}
422 };
423 
424 /**
425 	This is an alternate constructor to initialize Term objects.
426 	This is meant to be used in conjunction witht the serialize() method
427 	@deprecated
428 	@param {String} sterm A string of the form ax^b where a,b are floats, and x is any variable 
429 **/
430 Term.prototype.initTerm = function(sterm) {
431 	var termRe = /([-]*\d*(\.\d*)*)([a-zA-Z]+)\^([-]*\d+(\.\d*)*)+/;
432 	var termValues = termRe.exec(sterm);
433 
434 	this.coefficient = parseFloat(termValues[1]);
435 	this.power = parseFloat(termValues[4]);
436 	this.variable = termValues[3];
437 	//returnv 
438 };
439 
440 /**
441 	Returns the monomial's degree
442 **/	
443 Term.prototype.degree = function() {
444 	var degree = 0;
445 	for(var i =0; i < this.power.length; i++) {
446 		degree += this.power[i];
447 	}
448 	return degree;
449 }
450 
451 
452 /**
453 	A point object representing a point in a 2-d plane
454 	@class
455 	@constructor
456 	@param {Number} x The x value
457 	@param {Number} y The y value
458 **/
459 function Point(x,y)
460 {
461 		this.x = parseFloat(x);
462 		this.y = parseFloat(y);
463 }
464 
465 /**
466 	A method to convert a Point to a String
467 	@return {String} The point value in parens
468 **/
469 Point.prototype.toString = function()
470 {
471 		return "("+this.x+","+this.y+")";	
472 };
473 
474 /**
475 	A method to calculate the integral of a function fofx from a to b using 2^n divisions
476 	@param {Polynomial|Term} fofx The function to be integrated
477 	@param {Number} a The lower bound
478 	@param {Number} b The upper bound
479 	@param {Number} n The power of 2 used to partition the range  
480 **/
481 function RombergExtrapolation(fofx, a,b,n)
482 {
483 	var h = b-a;
484 	var r = new Array(n+1);
485 	for(var i=0; i <= n; i++)
486 	{
487 		r[i]= new Array(n+1);
488 	}
489 	r[0][0] = h*(fofx.resolve(a)+fofx.resolve(b))/2;
490 	for(var i=1; i <= n; i++)
491 	{
492 		var sum=0;
493 		h /=2;
494 		for(var k=1; k < Math.pow(2,i); k+=2)
495 		{
496 			//sum += fofx.resolve(a+((2*k-1)*h));
497 			sum += fofx.resolve(a+k*h);
498 		}
499 		r[i][0]=r[i-1][0]/2+sum*h;
500 		for(var j=1; j<=i;j++)
501 		{
502 			r[i][j] = r[i][j-1]+(r[i][j-1]-r[i-1][j-1])/(Math.pow(4,j)-1);
503 		}
504 	}
505 	return r;
506 
507 
508 }
509 
510 /**
511 	A method to calculate the integral of a function fofx from a to b using n divisions
512 	@param {Polynomial|Term} fofx The function to be integrated
513 	@param {Number} a The lower bound
514 	@param {Number} b The upper bound
515 	@param {Number} n The number of divisions used to partition the range  
516 **/
517 function TrapezoidRule(fofx, a, b, n)
518 {
519 	var x;
520 	var h = (b-a)/n;
521 	var sum =(fofx.resolve(a)+fofx.resolve(b))/2;
522 	for(var i=1; i< n; i++)
523 	{
524 		x = a+i*h;
525 		sum += fofx.resolve(x);
526 	}
527 	sum *=h;
528 	return sum;
529 
530 }
531 
532 /**
533 	A method to calculate the integral of a function fofx from a to b 
534 	@param {Polynomial|Term} fofx The function to be integrated
535 	@param {Number} a The lower bound
536 	@param {Number} b The upper bound
537 **/
538 function basicSimpsonsrule(fofx,a,b)
539 {
540 	var h=(b-a)/6;
541 	var sum =h*(fofx.resolve(a)+4*fofx.resolve((a+b)/2)+fofx.resolve(b));
542 
543 	return sum;
544 }
545 
546 
547 function bisection(fofx, a, b, depthmax, epsilon) 
548 {
549 	var left = fofx.resolve(a);
550 	var right = fofx.resolve(b);
551 	var center;
552 	if(left*right >0)
553 	{
554 		//throw error? "function has the same sign at a and b"
555 		return false;
556 	}
557 	var error = b-a;
558 	for(var i = 0; i <depthmax;i++)
559 	{
560 		error /=2;
561 		center = a + error;
562 		var fofc = fofx.resolve(center);
563 		if(Math.abs(error) < epsilon)
564 		{
565 			return center;
566 		}
567 		if(left*fofc <0)
568 		{
569 			b = center;
570 			right = fofc;
571 		}else{
572 			a = center;
573 			right = fofc;
574 		}
575 
576 	}
577 	//throw "Did not converge in $depthmax steps";
578 }
579