Parent Directory
| 
Revision Log
Fixed error concerning variable $string. Cleaned up how polynomials are displayed. Arnie
1 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 ## Version 1.1.2 ## 9 ########################################################## 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 ## ValidPoly 32 ## 33 sub ValidPoly { 34 my $xref = @_; 35 if (${$xref}[0] != 0) {return 1;} 36 else {return 0;} 37 } 38 39 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 55 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 ## @newPoly = PolyMult(~~@coefficientArray1,~~@coefficientArray2); 73 ## 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 ## 111 ## 112 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 my $string = ''; 209 foreach my $i (0..$#poly) { 210 my $j = $#poly-$i; 211 if ($j == $#poly) { 212 if ($poly[$i] >0) { 213 if ($poly[$i]!=1){ 214 $string = $string."$poly[$i] x^{$j}"; 215 } 216 else {$string=$string."x^{$j}";} 217 } 218 elsif ($poly[$i] == 0) {} 219 elsif ($poly[$i] == -1) {$string=$string."-x^{$j}";} 220 else {$string = $string."$poly[$i] x^{$j}";} 221 } 222 elsif ($j > 0 && $j!=1) { 223 if ($poly[$i] >0) { 224 if ($poly[$i]!=1){ 225 $string = $string."+$poly[$i] x^{$j}"; 226 } 227 else {$string = $string."+x^{$j}";}} 228 elsif ($poly[$i] == 0) {} 229 elsif ($poly[$i] == -1) {$string=$string."-x^{$j}";} 230 else {$string = $string."$poly[$i] x^{$j}";} 231 } 232 elsif ($j == 1) { 233 if ($poly[$i] > 0){ 234 if ($poly[$i]!=1){ 235 $string = $string."+$poly[$i] x"; 236 } 237 else {$string = $string."+x";} 238 } 239 elsif ($poly[$i] == 0) {} 240 elsif ($poly[$i] == -1){$string=$string."-x";} 241 else {$string=$string."$poly[$i] x";} 242 } 243 else { 244 if ($poly[$i] > 0){ 245 $string = $string."+$poly[$i] "; 246 } 247 elsif ($poly[$i] == 0) {} 248 else {$string=$string."$poly[$i] ";} 249 } 250 } 251 return $string; 252 } 253 254 255 sub PolyFunc { 256 my $temp = $_[0]; 257 my @poly = @{$temp}; 258 $func = ""; 259 foreach $i (0..$#poly) { 260 $j = $#poly-$i; 261 if ($poly[$i] > 0) {$func = $func."+$poly[$i]*x**($j)";} 262 else {$func = $func."$poly[$i]*x**($j)";} 263 } 264 return $func; 265 } 266 267 ## 268 ## ($maxpos,$maxneg) = Descartes(~~@poly); 269 ## 270 ## accepts an array containing the coefficients, in descending order, of a 271 ## polynomial 272 ## returns the maximum number of positive and negative roots according to 273 ## Descartes Rule of Signs 274 ## 275 ## IMPORTANT NOTE: this function currently does not accept coefficients of 276 ## zero. 277 ## 278 279 sub Descartes { 280 my $temp = $_[0]; 281 my @poly = @{$temp}; 282 my $pos = 0; my $neg = 0; 283 foreach $i (1..$#poly) { 284 if (sgn($poly[$i])*sgn($poly[$i-1]) == -1) {$pos++;} 285 elsif (sgn($poly[$i])*sgn($poly[$i-1]) == 1) {$neg++;} 286 } 287 return ($pos,$neg); 288 } 289 290 291 292 293 294 295 296 297 298 299 1;
| aubreyja at gmail dot com | ViewVC Help |
| Powered by ViewVC 1.0.9 |