Parent Directory
| 
Revision Log
moved PG modules and macro files from webwork-modperl to pg -sam
1 #!/usr/local/bin/webwork-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 ## 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 $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 else {$string = $string."+x^{$j}";}} 220 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 else {$string = $string."+x";}} 229 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 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 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 |