[system] / trunk / webwork / system / courseScripts / PGpolynomialmacros.pl Repository:
ViewVC logotype

View of /trunk/webwork/system/courseScripts/PGpolynomialmacros.pl

Parent Directory Parent Directory | Revision Log Revision Log


Revision 293 - (download) (as text) (annotate)
Thu May 23 13:52:02 2002 UTC (17 years, 6 months ago) by gage
File size: 7800 byte(s)
Adding documentation

    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