[system] / trunk / pg / macros / PGpolynomialmacros.pl Repository:
ViewVC logotype

View of /trunk/pg/macros/PGpolynomialmacros.pl

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4997 - (download) (as text) (annotate)
Mon Jun 11 18:16:40 2007 UTC (12 years, 7 months ago) by gage
File size: 8246 byte(s)
Fixing docementation so that it can be read from the web.

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

aubreyja at gmail dot com
ViewVC Help
Powered by ViewVC 1.0.9