[system] / trunk / webwork / system / courseScripts / PGpolynomialmacros.pl Repository: Repository Listing bbplugincoursesdistsnplrochestersystemwww

# Annotation of /trunk/webwork/system/courseScripts/PGpolynomialmacros.pl

Revision 272 - (view) (download) (as text)

 1 : apizer 271 #!/usr/bin/perl 2 : ########################################################## 3 : ## This file is PGpolynomialmacros.pl ## 4 : ## It contains rountines used to create and manipulate ## 5 : ## polynomials for WeBWorK ## 6 : ## ## 7 : ## Copyright 2002 Mark Schmitt ## 8 : apizer 272 ## Version 1.1.2 ## 9 : apizer 271 ########################################################## 10 : 11 : ## In the current version, there is no attempt to verify that correct arrays are being passed to the routines. 12 : ## This ought to be changed in the next incarnation. 13 : ## It is assumed that arrays passed to the routines have no leading zeros, and represent the coefficients of 14 : ## a polynomial written in standard form using place-holding zeros. 15 : ## This means \$array[0] is the leading coefficient of the polynomial and \$array[\$#array] is the constant term. 16 : ## 17 : ## The routines were written based on the needs of my Honors Algebra 2 course. The following algorithms have been 18 : ## coded: 19 : ## Polynomial Multiplication 20 : ## Polynomial Long Division 21 : ## Polynomial Synthetic Division (mainly as a support routine for checking bounds on roots) 22 : ## Finding the least positive integral upper bounds for roots 23 : ## Finding the greatest negative integral lower bounds for roots 24 : ## Descartes' Rule of Signs for the maximum number of positive and negative roots 25 : ## Stringification : converting an array of coefficients into a properly formatted polynomial string 26 : ## Polynomial Addition 27 : ## Polynomial Subtraction 28 : 29 : 30 : ## 31 : apizer 272 ## ValidPoly 32 : apizer 271 ## 33 : apizer 272 sub ValidPoly { 34 : my \$xref = @_; 35 : if (\${\$xref}[0] != 0) {return 1;} 36 : else {return 0;} 37 : } 38 : 39 : apizer 271 sub PolyAdd{ 40 : my (\$xref,\$yref) = @_; 41 : @local_x = @{\$xref}; 42 : @local_y = @{\$yref}; 43 : if (\$#local_x < \$#local_y) { 44 : while (\$#local_x < \$#local_y) {unshift @local_x, 0;} 45 : } 46 : elsif (\$#local_y < \$#local_x) { 47 : while (\$#local_y < \$#local_x) {unshift @local_y, 0;} 48 : } 49 : foreach \$i (0..\$#local_x) { 50 : \$sum[\$i] = \$local_x[\$i] + \$local_y[\$i]; 51 : } 52 : return @sum; 53 : } 54 : apizer 272 55 : apizer 271 sub PolySub{ 56 : my (\$xref,\$yref) = @_; 57 : @local_x = @{\$xref}; 58 : @local_y = @{\$yref}; 59 : if (\$#local_x < \$#local_y) { 60 : while (\$#local_x < \$#local_y) {unshift @local_x, 0;} 61 : } 62 : elsif (\$#local_y < \$#local_x) { 63 : while (\$#local_y < \$#local_x) {unshift @local_y, 0;} 64 : } 65 : foreach \$i (0..\$#local_x) { 66 : \$diff[\$i] = \$local_x[\$i] - \$local_y[\$i]; 67 : } 68 : return @diff; 69 : } 70 : 71 : ## 72 : apizer 272 ## @newPoly = PolyMult(~~@coefficientArray1,~~@coefficientArray2); 73 : apizer 271 ## 74 : ## accepts two arrays containing coefficients in descending order 75 : ## returns an array with the coefficients of the product 76 : ## 77 : 78 : sub PolyMult{ 79 : my (\$xref,\$yref) = @_; 80 : @local_x = @{\$xref}; 81 : @local_y = @{\$yref}; 82 : foreach \$i (0..\$#local_x + \$#local_y) {\$result[\$i] = 0;} 83 : foreach \$i (0..\$#local_x) { 84 : foreach \$j (0..\$#local_y) { 85 : \$result[\$i+\$j] = \$result[\$i+\$j]+\$local_x[\$i]*\$local_y[\$j]; 86 : } 87 : } 88 : return @result; 89 : } 90 : 91 : ## 92 : ## (@quotient,\$remainder) = SynDiv(~~@dividend,~~@divisor); 93 : ## 94 : 95 : sub SynDiv{ 96 : my (\$dividendref,\$divisorref)=@_; 97 : my @dividend = @{\$dividendref}; 98 : my @divisor = @{\$divisorref}; 99 : my @quotient; 100 : \$quotient[0] = \$dividend[0]; 101 : foreach \$i (1..\$#dividend) { 102 : \$quotient[\$i] = \$dividend[\$i]-\$quotient[\$i-1]*\$divisor[1]; 103 : } 104 : return @quotient; 105 : } 106 : 107 : ## 108 : ## 109 : ## 110 : apizer 272 ## 111 : ## 112 : apizer 271 113 : sub LongDiv{ 114 : my (\$dividendref,\$divisorref)=@_; 115 : my @dividend = @{\$dividendref}; 116 : my @divisor = @{\$divisorref}; 117 : my @quotient; my @remainder; 118 : foreach \$i (0..\$#dividend-\$#divisor) { 119 : \$quotient[\$i] = \$dividend[\$i]/\$divisor[0]; 120 : foreach \$j (1..\$#divisor) { 121 : \$dividend[\$i+\$j] = \$dividend[\$i+\$j] - \$quotient[\$i]*\$divisor[\$j]; 122 : } 123 : } 124 : foreach \$i (\$#dividend-\$#divisor+1..\$#dividend) { 125 : \$remainder[\$i-(\$#dividend-\$#divisor+1)] = \$dividend[\$i]; 126 : } 127 : return (\@quotient,\@remainder); 128 : } 129 : 130 : 131 : 132 : ## 133 : ## \$upperBound = UpBound(~~@polynomial); 134 : ## 135 : ## accepts a reference to an array containing the coefficients, in descending 136 : ## order, of a polynomial. 137 : ## 138 : ## returns the lowest positive integral upper bound to the roots of the 139 : ## polynomial 140 : ## 141 : 142 : sub UpBound { 143 : my \$polyref=\$_[0]; 144 : my @poly = @{\$polyref}; 145 : my \$bound = 0; 146 : my \$test = 0; 147 : while (\$test < @poly) { 148 : \$bound++; 149 : \$test=0; 150 : @div = (1,-\$bound); 151 : @result = &SynDiv(\@poly,\@div); 152 : foreach \$i (0..\$#result) { 153 : if (sgn(\$result[\$i])==sgn(\$result[0]) || \$result[\$i]==0) { 154 : \$test++; 155 : } 156 : } 157 : } 158 : return \$bound; 159 : } 160 : 161 : 162 : ## 163 : ## \$lowerBound = LowBound(~~@polynomial); 164 : ## 165 : ## accepts a reference to an array containing the coefficients, in descending 166 : ## order, of a polynomial. 167 : ## 168 : ## returns the greatest negative integral lower bound to the roots of the 169 : ## polynomial 170 : ## 171 : 172 : sub LowBound { 173 : my \$polyref=\$_[0]; 174 : my @poly = @{\$polyref}; 175 : my \$bound = 0; 176 : my \$test = 0; 177 : while (\$test == 0) { 178 : \$test = 1; \$bound = \$bound-1; 179 : @div = (1,-\$bound); 180 : @res = &SynDiv(\@poly,\@div); 181 : foreach \$i (1..int((\$#res -1)/2)) { 182 : if (sgn(\$res[0])*sgn(\$res[2*\$i]) == -1) { 183 : \$test = 0;} 184 : } 185 : foreach \$i (1..int(\$#res/2)) { 186 : if (sgn(\$res[0])*sgn(\$res[2*\$i-1]) == 1) { 187 : \$test = 0;} 188 : } 189 : } 190 : return \$bound; 191 : } 192 : 193 : 194 : 195 : 196 : ## 197 : ## \$string = PolyString(~~@coefficientArray,x); 198 : ## 199 : ## accepts an array containing the coefficients of a polynomial 200 : ## in descending order 201 : ## returns a sting containing the polynomial with variable v 202 : ## default variable is x 203 : ## 204 : 205 : sub PolyString{ 206 : my \$temp = \$_[0]; 207 : my @poly = @{\$temp}; 208 : \$string = ""; 209 : foreach \$i (0..\$#poly) { 210 : \$j = \$#poly-\$i; 211 : if (\$j == \$#poly) {if (\$poly[\$i]!=1){ 212 : \$string = \$string."\$poly[\$i] x^{\$j}";} 213 : else {\$string=\$string."x^{\$j}";} 214 : } 215 : elsif (\$j > 0 && \$j!=1) { 216 : if (\$poly[\$i] >0) { 217 : if (\$poly[\$i]!=1){ 218 : \$string = \$string."+\$poly[\$i] x^{\$j}";} 219 : apizer 272 else {\$string = \$string."+x^{\$j}";}} 220 : apizer 271 elsif (\$poly[\$i] == 0) {} 221 : elsif (\$poly[\$i] == -1) {\$string=\$string."-x^{\$j}";} 222 : else {\$string = \$string."\$poly[\$i] x^{\$j}";} 223 : } 224 : elsif (\$j == 1) { 225 : if (\$poly[\$i] > 0){ 226 : if (\$poly[\$i]!=1){ 227 : \$string = \$string."+\$poly[\$i] x";} 228 : apizer 272 else {\$string = \$string."+x";}} 229 : apizer 271 elsif (\$poly[\$i] == 0) {} 230 : elsif (\$poly[\$i] == -1){\$string=\$string."-x";} 231 : else {\$string=\$string."\$poly[\$i] x";} 232 : } 233 : else { 234 : if (\$poly[\$i] > 0){ 235 : \$string = \$string."+\$poly[\$i] ";} 236 : elsif (\$poly[\$i] == 0) {} 237 : else {\$string=\$string."\$poly[\$i] ";} 238 : } 239 : } 240 : return \$string; 241 : } 242 : 243 : apizer 272 sub PolyFunc { 244 : my \$temp = \$_[0]; 245 : my @poly = @{\$temp}; 246 : \$func = ""; 247 : foreach \$i (0..\$#poly) { 248 : \$j = \$#poly-\$i; 249 : if (\$poly[\$i] > 0) {\$func = \$func."+\$poly[\$i]*x**(\$j)";} 250 : else {\$func = \$func."\$poly[\$i]*x**(\$j)";} 251 : } 252 : return \$func; 253 : } 254 : apizer 271 255 : ## 256 : ## (\$maxpos,\$maxneg) = Descartes(~~@poly); 257 : ## 258 : ## accepts an array containing the coefficients, in descending order, of a 259 : ## polynomial 260 : ## returns the maximum number of positive and negative roots according to 261 : ## Descartes Rule of Signs 262 : ## 263 : ## IMPORTANT NOTE: this function currently does not accept coefficients of 264 : ## zero. 265 : ## 266 : 267 : sub Descartes { 268 : my \$temp = \$_[0]; 269 : my @poly = @{\$temp}; 270 : my \$pos = 0; my \$neg = 0; 271 : foreach \$i (1..\$#poly) { 272 : if (sgn(\$poly[\$i])*sgn(\$poly[\$i-1]) == -1) {\$pos++;} 273 : elsif (sgn(\$poly[\$i])*sgn(\$poly[\$i-1]) == 1) {\$neg++;} 274 : } 275 : return (\$pos,\$neg); 276 : } 277 : 278 : 279 : 280 : 281 : 282 : 283 : 284 : 285 : 286 : 287 : 1;

 aubreyja at gmail dot com ViewVC Help Powered by ViewVC 1.0.9