Parent Directory
| 
Revision Log
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 |